文档来源为:从网络收集整理.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版本可编辑.欢迎下载支持.