文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

示法；根结点是父，根无右子女，左子女表示妻，妻的右子女（右子女的右子女等）均可看成兄弟（即父的所有儿子），兄弟结点又成为新的父，其左子女是兄弟（父的儿子）妻，妻的右子女（右子女的右子女等）又为儿子的儿子等等。首先递归查找某父亲结点，若查找成功，则其左子女是妻，妻的右子女及右子女的右子女等均为父亲的儿子。

BiTree Search(BiTree t,ElemType father)//在二叉树上查找值为father的结点 {if(t==null) return (null); //二叉树上无father结点 else if(t->data==father) return(t); //查找成功

p=Search(t->lchild,father); p=Search(t->rchild,father); } }//结束Search

void PrintSons(BiTree t,ElemType p) //在二叉树上查找结点值为p的所有的儿子 {p=Serach(t,p); //在二叉树t上查找父结点p if(p!=null) //存在父结点

{q=p->lchild; q=q->rchild; //先指向其妻结点，再找到第一个儿子 while(q!=null) {printf(q->data); q=q->rchild;} //输出父的所有儿子 }

}//结束PrintSons

18.[题目分析]后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。

void Search(BiTree bt,ElemType x) //在二叉树bt中，查找值为x的结点，并打印其所有祖先

{typedef struct

{BiTree t; int tag; }stack;//tag=0表示左子女被访问，tag=1表示右子女被访问 stack s[]; //栈容量足够大 top=0;

while(bt!=null||top>0)

{while(bt!=null && bt->data!=x) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

if(bt->data==x){ printf(“所查结点的所有祖先结点的值为:\\n”); //找到x

for(i=1;i<=top;i++) printf(s[i].t->data); return; } //输出祖先值后结束

while(top!=0 && s[top].tag==1) top--; //退栈（空遍历） if(top!=0) {s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历 }// while(bt!=null||top>0) }结束search

因为查找的过程就是后序遍历的过程，使用的栈的深度不超过树的深度，算法复杂度为O(logn)。

19.[题目分析] 先序遍历二叉树的非递归算法，要求进栈元素少，意味着空指针不进栈。 void PreOrder(Bitree bt)//对二叉数bt进行非递归遍历

{int top=0; Bitree s[]; //top是栈s的栈顶指针，栈中元素是树结点指针，栈容量足够大

while(bt!=null || top>0)

{while(bt!=null)

{printf(bt->data); //访问根结点

21文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

if(bt->rchlid) s[++top]=bt->rchild; //若有右子女，则右子女进栈 bt=bt->lchild; }

if (top>0) bt=s[top--]; }

本题中的二叉树中需进栈的元素有 C,H,K,F。

20.[题目分析]二叉树的顺序存储是按完全二叉树的顺序存储格式，双亲与子女结点下标间有确定关系。对顺序存储结构的二叉树进行遍历，与二叉链表类似。在顺序存储结构下，判二叉树为空时，用结点下标大于n（完全二叉树）或0（对一般二叉树的“虚结点”）。本题是完全二叉树。

void PreOrder(ElemType bt,int n)//对以顺序结构存储的完全二叉树bt进行前序遍历

{int top=0,s[]; //top是栈s的栈顶指针，栈容量足够大 while(i<=n||top>0) {while(i<=n)

{ printf(bt[i]); //访问根结点；

if (2*i+1<=n) s[++top]=2*i+1; //右子女的下标位置进栈 i=2*i; } //沿左子女向下 if(top>0) i=s[top--]; } //取出栈顶元素 }//结束PreOrder

21.[题目分析] 本题使用的存储结构是一种双亲表示法，对每个结点，直接给出其双亲（的下标），而且用正或负表示该结点是双亲的右子女或左子女。该类结构不适于直接进行前序遍历（即若直接前序遍历，算法要很复杂），较好的办法是将这类结构转为结点及其左右子女的顺序存储结构，即

Tree2=ARRAY[1..max] OF RECORD data: char; //结点数据

lc,rc: integer; END;//结点的左右子女在数组中的

下标

void Change (Tree t, Tree2 bt, int *root) //先将t转为如上定义类型的变量bt; {for(i=1;i<=max;i++) {bt[i].lc=bt[i].rc=0;} //先将结点的左右子女初始化为0 for(i=1;i<=max;i++) //填入结点数据，和结点左右子女的信息 {bt[i].data=t[i].data;

if(t[i].parent<0) bt[-t[i].parent].lc=i; //左子女 else if(t[i].parent>0) bt[t[i].parent].rc=i; //右子女 else *root=i; //root记住根结点 } }//change

void PreOrder(Tree2 bt) //对二叉树进行前序遍历 {int *root,top=0; int s[]; //s是栈 change(t,bt,root); int i=*root; while(i!=0||top>0) {while (i!=0)

{printf (bt[i].data)；if(bt[i].rc!=0) s[++top]=bt[i].rc; //右子女进栈 i=bt[i].lc;

}

if (top>0) i=s[top--];

} }//结束preorder

22文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

[算法讨论]本题的前序递归算法如下

void PreOrder(int root)//root是二叉树根结点在顺序存储中的下标，本算法前序遍历二叉树bt

{if(root!=0){printf(bt[root].data);//访问根结点

PreOrder(bt[root].lc);//前序遍历左子树 PreOrder(bt[root].rc);//前序遍历右子树

} }//结束preorder，初始调用时，root是根结点的下标

这类问题的求解方法值得注意。当给定数据存储结构不合适时，可由已给结构来构造好的数据结构，以便于运算。象上面第5题也是这样，先根据L和R数组，构造一个结点的双亲的数组T。

22．[题目分析]二叉树先序序列的最后一个结点，若二叉树有右子树，则是右子树中最右下的叶子结点；若无右子树，仅有左子树，则是左子树最右下的叶子结点；若二叉树无左右子树，则返回根结点。

BiTree LastNode(BiTree bt)//返回二叉树bt先序序列的最后一个结点的指针 {BiTree p=bt;

if(bt==null) return(null); else while(p)

if (p->rchild) p=p->rchild; //若右子树不空，沿右子树向下

else if (p->lchild) p=p->lchild; //右子树空，左子树不空，沿左子树向下

else return(p); //p即为所求

}//结束lastnode

K

23.[题目分析]高度为K的二叉树，按顺序方式存储，要占用2–1个存储单元，与实际结点个数n关系不大，对不是完全二叉树的二叉树，要增加“虚结点”，使其在形态上成为完全二叉树。

K

int m=2–1; //全局变量

void PreOrder(ElemType bt[],i )

//递归遍历以顺序方式存储的二叉树bt， i是根结点下标（初始调用时为1）。 {if (i<=m) //设虚结点以0表示 {printf(bt[i])； //访问根结点

if(2*i<=m && bt[2*i]!=0) PreOrder(bt,2*i); //先序遍历左子树 if(2*i+1<=m && bt[2*i+1]!=0) PreOrder(bt,2*i+1);// 先序遍历右子树 } }//结束PreOrder

二叉树中最大序号的叶子结点,是在顺序存储方式下编号最大的结点

void Ancesstor(ElemType bt[]) //打印最大序号叶子结点的全部祖先

{c=m; while(bt[c]==0) c--; //找最大序号叶子结点,该结点存储时在最后 f=c/2; //c的双亲结点f

while(f!=0) //从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点 {printf(bt[f]); f=f/2; }//逆序输出，最老的祖先最后输出 } //结束

24. void InOrder(BiTree bt)

{BiTree s[],p=bt; //s是元素为二叉树结点指针的栈，容量足够大

int top=0;

while(p || top>0)

{while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树

23文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树

} }

25.[题目分析] 二叉树用顺序方式存储，其遍历方法与用二叉链表方式存储类似。判空时，在二叉链表方式下用结点指针是否等于null，在顺序存储方式下， 一是下标是否是“虚结

H

点”，二是下标值是否超过最大值（高为H的二叉树要有2-1个存储单元，与实际结点个数关系不大）。当然，顺序存储方式下，要告诉根结点的下标。

void InOrder(int i) //对顺序存储的二叉树进行中序遍历，i是根结点的下标 {if(i!=0)

{InOrder(ar[i].Lc); //中序遍历左子树 printf(ar[i].data); //访问根结点

InOrder(ar[i].Rc); //中序遍历左子树 } } // 结束InOrder 26.[题目分析] 借助队列和栈，最后弹出栈中元素实现对二叉树按自下至上，自右至左的层次遍历

void InvertLevel(biTree bt) // 对二叉树按自下至上，自右至左的进行层次遍历 {if(bt!=null)

{StackInit(s); //栈初始化，栈中存放二叉树结点的指针 QueueInit(Q); //队列初始化。队列中存放二叉树结点的指针 QueueIn(Q,bt);

while(!QueueEmpty(Q)) //从上而下层次遍历 {p=QueueOut(Q); push(s,p); //出队, 入栈

if(p->lchild) QueueIn(Q,p->lchild); //若左子女不空，则入队列 if(p->rchild) QueueIn(Q,p->rchild);} //若右子女不空,则入队列

while(!StackEmpty(s)) {p=pop(s); printf(p->data);} //自下而上,从右到左的层次遍历

}//if(bt!=null)

} //结束InvertLevel

27. int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数

{int num=0; //num统计度为1的结点的个数

if(bt){QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q); printf(p->data); //出队,访问结点

if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为

1的结点

if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } }//if(bt)

return(num); }//返回度为1的结点的个数

28. void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换 {if(bt){BiTree s；

s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交换 exchange(bt->lchild); //交换左子树上所有结点的左右子树 exchange(bt->rchild); //交换右子树上所有结点的左右子树

24文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

} }

[算法讨论]将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。下面是本题（1）要求的非递归算法

（1）void exchange(BiTree t) //交换二叉树中各结点的左右孩子的非递归算法

{int top=0; BiTree s[],p; //s是二叉树的结点指针的栈，容量足够大 if(bt)

{s[++top]=t; while(top>0)

{t=s[top--];

if(t->lchild||t->rchild){p=t->lchild;t->lchild=t->rchild;t->rchild=p;}

//交换左右

if(t->lchild) s[++top]=t->lchild; //左子女入栈 if(t->rchild) s[++top]=t->rchild; //右子女入栈 }//while(top>0)

}//if(bt) }// 结束exchange

29.[题目分析]对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。

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

30.BiTree IntoPost(ElemType in[],post[],int l1,h1,l2,h2)

//in和post是二叉树的中序序列和后序序列,l1,h1,l2,h2分别是两序列第一和最后结点的下标

{BiTree bt=(BiTree)malloc(sizeof(BiNode));//申请结点

bt->data=post[h2];//后序遍历序列最后一个元素是根结点数据

for(i=l1;i<=h1;i++) if(in[i]==post[h2])break;//在中序序列中查找根结点 if(i==l1) bt->lchild=null; //处理左子树

else bt->lchild=IntoPost(in,post,l1,i-1,l2,l2+i-l1-1)； if(i==h1) bt->rchild=null; //处理右子树

else bt->rchild=IntoPost(in,post,i+1,h1,l2+i-l1,h2-1); return(bt); }

31.TYPE bitreptr=^binode;

binode=RECORD data:ElemType; lchild,rchlid:bitreptr END; PROC PreOrder(bt:bitreptr); //非递归前序遍列二叉树

25文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.