1、(1p->rchild(2p->lchild(3p->lchild(4ADDQ(Q,p->lchild(5ADDQ(Q,p->rchild
25.(1t->rchild!=null(2t->rchild!=null(3N0++(4count(t->lchild(5count(t->rchild
26..(1top++(2stack[top]=p->rchild(3top++(4stack[top]=p->lchild
27.(1*ppos//根结点（2）rpos=ipos(3rpos–ipos(4ipos(5ppos+1
2、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，„，Sm,后序序列是P1,P2,„，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，„，Si-1是左子树的中序序列，而Si+1,Si+2,„,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，„，Sm}和{P1，P2，„，Pm-1}可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，„，Sm-1}和{P1，P2，„，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1时，Si把中序序列分成{S1，S2，„，Si-1}和{Si+1,Si+2,„，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,„,Pi-1}和{Pi,Pi+1,„Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，„，Si-1}和{P1，P2，„，Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,„，Sm}和{Pi,Pi+1,„，Pm-1}可唯一确定二叉树的右子树。
3、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedefstruct
{intlvl;//层次序列指针，总是指向当前“根结点”在层次序列中的位置intl,h;//中序序列的下上界
intf;//层次序列中当前“根结点”的双亲结点的指针intlr;//1—双亲的左子树2—双亲的右子树}qnode;
BiTreeCreat(datatypein[],level[],intn
//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。n是二叉树的结点数{if(n<1{printf(“参数错误\n”;exit(0;}
qnodes,Q[];//Q是元素为qnode类型的队列，容量足够大init(Q;intR=0;//R是层次序列指针，指向当前待处理的结点BiTreep=(BiTreemalloc(sizeof(BiNode;//生成根结点
p->data=level[0];p->lchild=null;p->rchild=null;//填写该结点数据
for(i=0;i在中序序列中查找根结点，然后，左右子女信息入队列
