内容发布更新时间 : 2024/12/22 16:52:21星期一 下面是文章的全部内容请认真阅读。

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

8. [题目分析]二叉树高度可递归计算如下：若二叉树为空，则高度为零，否则，二叉树的高度等于左右子树高度的大者加1。这里二叉树为空的标记不是null而是0。设根结点层号为1，则每个结点的层号等于其双亲层号加1。 现将二叉树的存储结构定义如下:

typedef struct node

{int L[];//编号为i的结点的左儿子 int R[];//编号为i的结点的右儿子 int D[];//编号为i的结点的层号 int i; //存储结点的顺序号（下标）

}tnode;

（1）int Height(tnode t,int i)//求二叉树高度，调用时i=1

{int lh,rh;

if (i==0) return (0);

else{lh=Height(t,t.L[i]); rh=Height(t,t.R[i]);

if(lh>rh) return(lh+1); else return(rh+1); }

}//结束Height

（2）int Level（tnode t）//求二叉树各结点的层号，已知编号为1的结点是根，且层号为1

{t.D[1]=1;

for(i=1;i<=n;i++) {depth=t.D[i]； //取出根结点层号 if(t.L[i]!=0) t.D[t.L[i]]=depth+1; //i结点左儿子层号 if(t.R[i]!=0) t.D[t.R[i]]=depth+1; }//i结点右儿子层号 }结束level

9.[题目分析]二叉树采用顺序存储结构（一维数组）是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。

typedef struct

{BiTree bt; //二叉树结点指针

int num; }tnode // num是结点在一维数组中的编号 tnode Q[maxsize]; //循环队列,容量足够大 void creat(BiTree T,ElemType BT[ ])

h

//深度h的二叉树存于一维数组BT[1:2-1]中，本算法生成该二叉树的二叉链表存储结构

{tnode tq; //tq是队列元素

h

int len=2-1; //数组长度

T=(BiTree)malloc(sizeof(BiNode)); //申请结点 T->data=BT[1]; //根结点数据 tq.bt=T; tq.num=1;

Q[1]=tq; //根入队列

front=0;rear=1; //循环队列头、尾指针 while(front!=rear) //当队列不空时循环 {front=(front+1) % maxsize ;

tq=Q[front] ; p=tq.bt; i=tq.num ; //出队，取出结点及编号

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

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

if (BT[2*i]==‘#’||2*i>len) p->lchild=null; //左子树为空，‘#’表示虚结点

else //建立左子女结点并入队列

{p->lchild=(BiTree) malloc(sizeof(BiNode)); //申请结点空间 p->lchild?data=BT[2*i]; // 左子女数据

tq.bt=p->lchild; tq.num=2*i; rear=(rear+1) % maxsize ;//计算队尾位置 Q[rear]=tq; //左子女结点及其编号入队 }

if(BT[2*i+1]==‘#’|| 2*i+1>len) p->rchild=null; //右子树为空 else //建立右子女结点并入队列

{p->rchild=(BiTree)malloc(sizeof (BiNode); //申请结点空间 p->rchild->data=BT[2*i+1]; tq.bt=p->rchild; tq.num=2*i+1;

rear=(rear+1)%maxsize; Q[rear]=tq; //计算队尾位置,右子女及其编号

入队

}

} //while }//结束creat

[算法讨论] 本题中的虚结点用‘#’表示。应根据二叉树的结点数据的类型而定。 10．[题目分析]本题静态链表中结点是按动态二叉链表的前序遍历顺序存放的。首先对动态二叉链表的二叉树进行前序遍历，填写静态链表的“下标”和data域，再对动态二叉链表的二叉树进行层次遍历，设队列Q，填写静态链表的lchild域和rchild域。

typedef struct node //静态链表结点结构 {ElemType data; //结点数据

int row,lchild,rchild ; //下标，左右子女 }component；

component st[]; //st容量足够大

struct node {BiTree t; int idx; }qbt; static int num=0;

void PreOrder(BiTree bt);

// 前序遍历二叉树，填写静态链表的“下标”和data域 {if (bt)

{st[++num].data=bt->data; st[num].row=num;

PreOrder(bt->lchild); PreOrder(bt->rchild);

} }

int Locate(ElemType x)

//在静态链表中查二叉树结点的下标

{for (i=1;i<=num;i++) if (st[i].data==x) return (i); }

void DynaToST (BiTree bt) //将二叉树的动态二叉链表结构转为静态链表结构 {int i=0; //i为静态链表st的下标 if (bt!=null)

{QueueInit(Q); //Q是队列，容量足够大，队列元素是qbt

qbt.t=bt; qbt.idx=1; QueueIn(Q,qbt); st[1].data=bt->data; while(!QueueEmpty(Q))

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

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

{qbt=QueueOut(Q); //出队列

p=qbt.t; i=qbt.idx; //二叉树结点及在静态链表中的下标

if (p->lchild!=null) //若左子女存在,查其在静态链表中的下标, 填lchild域值

{lch=Locate(p->lchild->data)；st[i].lchild=lch; qbt.t=p->lchild; qbt.idx=lch; QueueIn(Q,qbt); }

else st[i].lchild=0; //无左子女，其lchild域填0

if (p->rchild!=null) //若右子女存在,查其在静态链表中的下标，填rchild域值

{rch=Locate(p->->rchild->data)；st[i].rchild=rch; qbt.t=p->rchild; qbt.idx=rch; QueueIn(Q,qbt); }

else st[i].rchild=0; //无左子女，其lchild域填0 }//while

}//结束DynaToST

11. [题目分析] 由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。

int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材

{int maxdepth=0; for(i=1;i<=t.n;i++) {temp=0; f=i;

while(f>0) {temp++; f=t.nodes[f].parent; } // 深度加1,并取新的双亲

if(temp>maxdepth) maxdepth=temp; //最大深度更新 }

return(maxdepth);//返回树的深度 } //结束Depth

12. [题目分析] 二叉树是递归定义的，其运算最好采取递归方式 int Height(btre bt)//求二叉树bt的深度 {int hl,hr;

if (bt==null) return(0);

else {hl=Height(bt->lch); hr=Height(bt->rch);

if(hl>hr) return (hl+1); else return(hr+1); } }

13．[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else

{BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大

front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置

temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列

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

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

while(front<=last)

{p=Q[front++]; temp++; //同层元素数加1

if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队

if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear;

if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度

temp=0;

}//if }//while

return (maxw); }//结束width

14．[题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。

int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度 {int hc,hs;

if (bt==null) return (0);

else if (!bt->firstchild) return (1+height(bt->nextsibling);//子女空，查兄弟的深度

else // 结点既有第一子女又有兄弟，高度取子女高度+1和兄弟子树高度的大者

{hc=height(bt->firstchild)； //第一子女树高 hs=height(bt->nextsibling)；//兄弟树高

if(hc+1>hs)return(hc+1); else return (hs); }

}//结束height

int height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度 {if(t==null) return(0);

else{int front=1,rear=1; //front,rear是队头队尾元素的指针 int last=1,h=0; //last指向树中同层结点中最后一个结点，h是树的高度 Q[rear]=t; //Q是以树中结点为元素的队列

while(front<=last)

{t=Q[front++]; //队头出列 while(t!=null) //层次遍历

{if (t->firstchild) Q[++rear]=t->firstchild; //第一子女入队 t=t->nextsibling; //同层兄弟指针后移 }

if(front>last) //本层结束，深度加1（初始深度为0） {h++;last=rear;} //last再移到指向当前层最右一个结点 }//while(front<=last)

}//else }//Height

15.[题目分析]后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后

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

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

序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。 typedef struct

{BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack;

stack s[],s1[];//栈，容量够大

BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0)

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

if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点

{for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存

if(bt==q) //找到q 结点。

for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t;

for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝

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) return(null);//ｑ、p无公共祖先 ｝//结束Ancestor

16.[题目分析]二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。

void Ancestor(ElemType A[],int n,i,j)

//二叉树顺序存储在数组A[1..n]中，本算法求下标分别为i和j的结点的最近公共祖先结点的值。

{while(i!=j)

if(i>j) i=i/2; //下标为i的结点的双亲结点的下标 else j=j/2; //下标为j的结点的双亲结点的下标

printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,A[i]);//设元素类型整型。

}// Ancestor

17.[题目分析]用二叉树表示出父子，夫妻和兄弟三种关系，可以用根结点表示父（祖先），根结点的左子女表示妻，妻的右子女表示子。这种二叉树可以看成类似树的孩子兄弟链表表

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