二叉树的储存和遍历

本文总阅读量次

情形1：输入不按层次遍历的普通二叉树

struct node{
	int data,l,r; //l左孩子位置  r右孩子位置
}tree[MAXN];   //MAXN表示节点个数

拆成数组：

int data[MAXN],l[MAXN],r[MAXN];

int tree[MAXN],n;
...
cin>>n;
for(int i = 1; i <= n; i++)
	cin>>tree[i];

只有按层次遍历的顺序给出完全二叉树或满二叉树可以用一维数组直接保存。

void dfs(int x) //x表示节点编号（位置）,也是子树的根
{
   if(tree[x].l) dfs(tree[x].l);
   cout<<x<<" ";
   if(tree[x].r) dfs(tree[x].r);
}

前序遍历和后序遍历只要调整访问根的顺序即可。

void dfs(int x) //x表示节点编号（位置）,也是子树的根
{
    if(2*x<=n) dfs(2*x);
    cout<<tree[x]<<" ";
    if(2*x+1<=n) dfs(2*x+1);
}