数据结构习题题目及答案_树和二叉树_参考答案(4)

{int num=0; ∥记叶子结点数 for(i=0;i

{if(BT[2*i]==0 && 2*i+1<=n && BT[2*i+1]==0) num++;} ∥若结点无孩子，则是叶子

else if(BT[i]!=0) num++; ∥存储在数组后一半的元素是叶子结点 }

return num; }∥结束Leaves

6.43已知二叉树以一维数组作为存储结构。试编写算法求下标为i和j的两个结点的最近共同祖先结点的值。

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

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

∥求顺序存储在bt[1..n]的二叉树中下标为i和j的两个结点的最近公共祖先结点

{if(i<1 || j<1) {printf(“参数错误\\n”);exit(0);}; if(i==j)

{if(i==1) {printf(“所查结点为根结点，无祖先\\n”);exit(0);}; else {printf (“结点的最近公共祖先是%d，值是%d”,i/2,A[i/2]);exit(0)} } while(i!=j)

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

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

6.44已知一棵完全二叉树顺序存储于向量s[1..n]中，试编写算法由此顺序存储结构建立该二叉树的二叉链表。 【算法6.44】

BiTree Creat(ElemType A[],int i)

∥n个结点的完全二叉树存于一维数组A中，本算法建立二叉链表表示的完全二叉树

{BiTree tree; if(i<=n)

{tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];

if(2*i>n) tree->lchild=null； else tree->lchild=Creat(A,2*i)； if(2*i+1>n) tree->rchild=null； else tree->rchild=Creat(A,2*i+1)； }

return (tree)； }∥Creat

【算法讨论】初始调用时,i=1。

6.45编写算法判别给定二叉树是否为完全二叉树。

【题目分析】判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。具体说，在层次遍历时，若碰到一个空指针后，在遍历结束前又碰到结点，则结论为该二叉树不是完全二叉树。 【算法6.45】

int JudgeComplete(BiTree bt)

∥判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; ∥出现空指针时，置tag=1

BiTree p=bt, Q[]; ∥ Q是队列，元素是二叉树结点指针，容量足够大

if(p==null) return (1);

QueueInit(Q); QueueIn(Q,p); ∥初始化队列，根结点指针入队 while(!QueueEmpty(Q))

{p=QueueOut(Q); ∥出队 if(p->lchild && !tag) QueueIn(Q,p->lchild);∥左子女入队

else if(p->lchild) return 0; ∥前边已有结点空，本结点不空

else tag=1; ∥首次出现结点为空 if(p->rchild && !tag) QueueIn(Q,p->rchild);∥右子女入队 else if(p->rchild) return 0; else tag=1; } ∥while

return 1; } ∥JudgeComplete

[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。

6.46设树以双亲表示法存储，编写计算树的深度的算法。

【题目分析】以双亲表示法作树的存储结构，对每一结点，找其双亲，双亲的双亲，直至（根）结点,就可求出每一结点的层次，取其结点的最大层次就是树的深度。 【算法6.46】

int Depth(Ptree t)

∥求以双亲表示法为存储结构的树的深度 {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

6.47已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

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

先设二叉树的结点结构为： typedef struct {BiTree t;

int tag; ∥tag=0表示结点的左子女已访问，tag=1为右子女已访问 }stack;

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

BiTree Ancestor(BiTree root, BiTree p, BiTree q, BiTree 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保存, top1记住栈顶 }

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(“共同的祖先已找到\\n”)； return (pp); }

｝

while(top!=0 && s[top].tag==1)

top--; ∥退栈 if(top!=0)｛