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

{Balance(bt->lchild); //后序遍历左子树 Balance(bt->rchild); //后序遍历右子树

hl=Height(bt->lchild); hr=Height(bt->rchild);//求左右子树的高度 bt->bf=hl-hr; //结点的平衡因子bf } }//算法结束

45.[题目分析]本题应采用层次遍历方式。若树不空，则二叉树根结点入队，然后当队列不空且队列长不超过n，重复如下操作：出队，若出队元素不为空，则记住其下标，且将其左右子女入队列；若出队元素为空，当作虚结点，也将其“虚子女”入队列。为节省空间，就用树T的顺序存储结构A[1..n]作队列，队头指针front，队尾指针rear，元素最大下标last.

void Traverse(BiTree bt ,int n)

// 求二叉树bt的顺序存储结构A[1..n]，下标超过n报错，给出实际的最大下标 {BiTree A[], p; if(bt!=null)

{int front=0,rear=1,last=1; A[1]=bt; while(front<=rear)

{p=A[++front]; if(p) last=front; // 出队;用last记住最后一个结点的下标

rear=2*front;//计算结点（包括虚结点）“左子女”下标 if (p) //二叉树的实际结点

{if(rear>n) printf(“%c结点无左子女”); else A[rear]=p->lchild; if(rear+1>n) printf(“%c结点无右子女”); else A[rear+1]=p->rchild; }

else //p是虚结点

{ if(rear<=n) A[rear]=null; if(rear+1<=n) A[rear+1]=null; } }// while(front<=rear)

printf(“实际的最大下标是%d”,last); }//if(bt!=null) }//Traverse

46. [题目分析]两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1);

else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild))

}//结束Similar

47.[题目分析] 根据树的双亲表示法创建树的孩子兄弟链表表示法,首先给出根结点在双亲表示法中的下标，但找根结点的子女要遍历双亲表示法的整个静态链表，根结点的第一个子女是孩子兄弟表示法中的孩子，其它子女结点作兄弟。对双亲表示法中的任一结点，均递归建立其孩子兄弟链表子树。

CSTree PtreeToCstree (PTree pt,int root)

//本算法将双亲表示法的树pt转为孩子兄弟链表表示的树，root是根结点在双亲表示法中的下标。

{CSTree child , sibling; int firstchild;

CSTree cst=(CSTree)malloc(sizeof(CSNode)); //申请结点空间

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

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

cst->data=pt.nodes[root].data; cst->firstchild=null; cst->nextsibling=null;//根结点

firstchild=1;

for(i=1;i<=pt.n;i++) //查找root的孩子 if(pt.nodes[i].parent==root) {child=PtreetoCstree(pt,i); if(firstchild) {cst->firstchild=child; firstchild=0;sibling=cst->firstchild;}

else //child不是root的第一个孩子，作兄弟处理

{sibling->nextsibling=child; sibling=sibling->nextsibling;}

}//if }//end for

return cst; }//结束PtreetoCstree

48.[题目分析] 删除以元素值x为根的子树，只要能删除其左右子树，就可以释放值为x的根结点，因此宜采用后序遍历。删除值为x结点，意味着应将其父结点的左(右)子女指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每一个元素值为 x的结点的子树，因此要遍历完整棵二叉树。

void DeleteXTree(BiTree bt) //删除以bt为根的子树 {DeleteXTree(bt->lchild); DeleteXTree(bt->rchild);//删除bt的左子树、右子树 free(bt); }// DeleteXTree //释放被删结点所占的存储空间

void Search(B:Tree bt,ElemType x)

//在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树 {BiTree Q[];//Q是存放二叉树结点指针的队列，容量足够大 if(bt)

{if(bt->data==x) {DeleteXTree(bt); exit(0);}//若根结点的值为x，则删除整棵树

{QueueInit(Q); QueueIn(Q,bt); while(!QueueEmpty(Q))

{p=QueueOut(Q);

if(p->lchild) // 若左子女非空

if(p->lchild->data==x) //左子女结点值为 x,应删除当前结点的左子树

{DeleteXTree(p->lchild); p->lchild=null;} //父结点的左子女置空

else Enqueue (Q,p->lchild);// 左子女入队列 if(p->rchild) // 若右子女非空

if(p->rchild->data==x) //右子女结点值为 x,应删除当前结点的右子树

{DeleteXTree(p->rchild); p->rchild=null;} //父结点的右子女置空

else Enqueue (Q,p->rchild);// 右子女入队列

}//while

}//if(bt) }//search

49.[题目分析]在二叉树上建立三叉链表，若二叉树已用二叉链表表示，则可象48题那样，给每个结点加上指向双亲的指针（根结点的双亲指针为空）。至于删除元素值为x的结点以

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

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

及以x为根的子树，与48题完全一样，请参照48题。下面给出建立用三叉链表表示的二叉树的算法。二叉树按完全二叉树格式输入，对非完全二叉树，要补上“虚结点”。按完全二叉树双亲和子女存储下标间的关系，完成双亲和子女间指针的链接。‘#’是输入结束标志，‘$’是虚结点标志。 BiTree creat()/ /生成三叉链表的二叉树（题目给出PASCAL定义，下面的用类C书写） {BiTree p,Q[]，root; //Q是二叉树结点指针的一维数组，容量足够大 char ch; int rear=0; //一维数组最后元素的下标 scanf(&ch);

while(ch!=‘#’) {p=null;

if(ch!=‘$’){p=(BiTree)malloc(sizeof(nodetp));

p->data=ch; p->lchild=p->rchild=null; }

Q[++rear]=p; //元素或虚结点

if(p){if(rear==1) {root=p;root->parent=null; } //根结点

else{Q[rear]->parent=Q[rear/2]; /双亲结点和子女结点用指针链上 if (rear%2==0) Q[rear/2]->lchild=Q[rear]; else Q[rear/2]->rchild=Q[rear];

}

scanf(“%c”,&ch); }//while

return(root); }//结束creat

50.int BTLC(BiTree T,int *c)//对二叉树T的结点计数

{if(T) {*c++;

BTLC(T->lchild,&c); //统计左子树结点 BTLC(T->rchild,&c); //统计右子树结点 } }//结束Count,调用时*c=0

51. int Count(CSTree t)//统计以孩子兄弟链表表示的树的叶子结点个数

{if(t==null) return(0);

else if(t->firstlchild==null) //左子女为空，结点必为叶子

return(1+Count(t->nextsibling))； //（叶子）+兄弟子树上的叶子结点 else return(Count(t->firstchild)+Count(t->nextsibling));//子女子树+兄弟子树

}//Count

52.void Count(BiTree bt,int *n0,*n) //统计二叉树bt上叶子结点数n0和非叶子结点数n

{if(bt)

{if (bt->lchild==null && bt->rchild==null) *n0++；//叶子结点 else *n++; //非叶结点 Count(bt->lchild,&n0,&n); Count(bt->rchild,&n0,&n); } }//结束 Count

53．int Count (BiTree bt) // 非递归遍历求二叉树上的叶子结点个数

{int num=0;

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

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

BiTree s[]; //s是栈，栈中元素是二叉树结点指针，栈容量足够大 whlie(bt!=null || top>0)

{while(bt!=null) {push(s,bt)；bt=bt->lchild；} //沿左分支向下

if(!StackEmpty(s))

{bt=pop(s)；if(bt->lchild==null && bt->rchild==null) num++；//叶子结点 bt=bt->rchild； }

} return(num);

}//结束Count

54.[题目分析]对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0);

BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数

int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数

while(front<=rear) {p=Q[++front];

if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队 if(p->rchild) Q[++rear]=p->rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel

55.[题目分析]按题目要求，每个结点的编号大于其左右孩子的编号，结点左孩子的编号小于右孩子的编号。由此看出，从小到大按“左右根”顺序，这正是后序遍序的顺序，故对二叉树进行后序遍历，在遍历中对结点进行编号，现将二叉树结点结构定义如下：

typedef struct node

{ElemType data; int num; struct node *lchild, *rchild; }Bnode,*Btree； void PostOrder(Btree t)

//对二叉树从1开始编号，结点编号大于其左右子女结点编号，结点的左子女编号小于其右子女编号

{typedef struct {Btree t; int tag; }node;

Btree p=t; node sn,s[]; //s为栈，容量足够大 int k=0,top=0; //k为结点编号，top为栈顶指针 while(p!=null || top>0)

{while(p) {sn.t=p; sn.tag=0; s[++top]=sn; p=p->lchild;} //沿左分枝向下 while(top>0 && s[top].tag==1){sn=s[top--];sn.t->num=++k;}//左右孩子已遍历,结点赋编号

if (top>0) {s[top].tag=1; p=s[top].t->rchild;} }//while(p!=null || top>0) }结束PostOrder

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

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

56. [题目分析]非递归算法参考上面第37题。下面给出递归算法。

void PreInCreat(BiTree root,ElemType pre[],in[],int l1,h1,l2,h2)

//根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。

{root=(BiTree)malloc(sizeof(BiNode)); //申请结点 root->data=pre[l1]; //pre[l1]是根

for(i=l2;i<=h2;i++) if(in[i]==pre[l1]) break; //在中序序列中，根结点将树分成左右子树

if(i==l2) root->lchild=null; //无左子树 else PreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)； //递归建立左子树

if(i==h2) root->rchild=null; //无右子树 else PreInCreat((root)->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) //递归建立右子树

}//结束PreInCreat

57（1）略 (2) 根据中序和后序序列，建立二叉树的递归算法见上面第30题，非递归算法见第38题。

58.[题目分析]采用后序非递归遍历二叉树，栈中保留从根结点到当前结点的路径上的所有

结点。

void PrintPath(BiTree bt,p) //打印从根结点bt到结点p之间路径上的所有结点 {BiTree q=bt,s[]; //s是元素为二叉树结点指针的栈，容量足够大

int top=0; tag[];//tag是数组，元素值为0或1，访问左、右子树的标志，tag和s同步

if (q==p) {printf(q->data); return;} //根结点就是所找结点 while(q!=null || top>0)

{while(q!=null) //左子女入栈，并置标记

if（q==p） //找到结点p，栈中元素均为结点p 的祖先 {printf(“从根结点到p结点的路径为\\n”);

for(i=1;i<=top;i++) printf(s[i]->data); printf(q->data); return; }

else {s[++top]=q; tag[top]=0; q=q—>lchild;} //沿左分支向下

while(top>0 && tag[top]==1)) top--；//本题不要求输出遍历序列，这里只退栈 if (top>0) {q=s[top]; q=q->rchild; tag[top]=1; } //沿右分支向下 }//while(q!=null || top>0) }//结束算法PrintPath

59.[题目分析]上题是打印从根结点到某结点p的路径上所有祖先结点，本题是打印由根结点到叶子结点的所有路径。只要在上题基础上把q是否等于p的判断改为q是否是叶子结点即可。其语句段如下：

if(q->lchild==null&&q->rchild==null) //q为叶子结点 {printf(“从根结点到p结点的路径为\\n”);

for(i=1;i<=top;i++) printf(s[i]->data);//输出从根到叶子路径上，叶子q的所有祖先

printf(q->data); }

60.[题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶

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