PTA 树的遍历

扫码查看
 
用数组模拟二叉树,设根结点为n,左孩子编号为2n,右孩子编号为2n+1,以这种方式存储二叉树 按顺序输出则为层序遍历。下面就定义一个数组,然后不断在子递归中查找根结点,将根结点存入相应的数组位置中。
 
 1 //下标从0开始
 2 //post[]为已知的后序遍历元素,in[]为已知的中序遍历元素
 3 //len-1为传进的post[]的根结点下标,len为在子递归函数(即左右子树)中的元素个数
 4 //p为根在num[]中的存储位置,即左右孩子结点成为子递归的根
 5 //p的起始位置是1
 6 void Levelorder(int post[],int in[],int len,int p)
 7 {
 8     if(len < 1)    //当子树没有元素时,返回
 9     {
10         num[p] = -1;
11         return;
12     }
13
14     int i = 0;
15     //len-1 为此次递归函数中 要存储在num[]数组中的根结点下标
16     //在中序遍历元素中,找到该根结点位置i,则左边为左子树,右边为右子树
17     while(post[len-1] != in[i])   i ++;
18
19     num[p] = post[len-1];
20
21     Levelorder(post,in,len,i,2*p);    //遍历左子树
22     Levelorder(post+i,in+i+1,len-i-1,2*p+1);//遍历右子树
23 }
12-27 22:34
查看更多