用数组模拟二叉树,设根结点为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 }