1、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)
//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)
{post[h2]=pre[l1]; //根结点
half=(h1-l1)/2; //左或右子树的结点数
PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost 32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt)
//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树
if(bt->lchild==null && bt->rchild==null) //叶子结点
if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 }
return(head); } //InOrder
时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)
2、设有一个数组中存放了一个无序的关键序列K1、K2、„、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。
3、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild
27. (1)*ppos // 根结点 （2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1 4、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.
typedef struct node
{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; }
26.树的先序非递归算法。 void example(b) btree *b;
{ btree *stack[20], *p； int top; if (b!=null)
{ top=1; stack[top]=b; while (top>0)
{ p=stack[top]; top--; printf(“%d”,p->data); if (p->rchild!=null) {(1)___; (2)___; }
if (p->lchild!=null) (3)___; (4)__; }}}}