【王道数据结构课后习题练习完整版】5.3.3二叉树的遍历和线索二叉树
写在前面：以下为程序所用到的文件:
- function.h头文件
//
// Created by 斋心 on 2023/7/2.
//
#ifndef INC_5_3_3_7_FUNCTION_H
#define INC_5_3_3_7_FUNCTION_H
#include<stdio.h>
#include<stdlib.h>
//二叉树结点结构体类型申明
typedef char BiElemType;
typedef struct BiNode{
BiElemType c;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
typedef BiTree ElemType;
//创建二叉树辅助队列结构体类型申明
typedef struct tag{
ElemType p;
struct tag *pnext;
}tag_t,*ptag_t;
//层次遍历二叉树辅助队列结点结构体类型申明
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
//层次遍历辅助队列
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
//层次建树函数申明
BiTree CreateBiTree(BiTree &T);
//层次遍历辅助队列函数申明
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &m);
bool IsEmpty(LinkQueue Q);
//二叉树遍历函数申明
void PreOrder(BiTree T);
void InOrder(BiTree T);
void PostOrder(BiTree T);
void LevelOrder(BiTree T);
//辅助栈结构体类型申明
typedef struct stack{
ElemType data;
struct stack *next;
}stack,*Lstack;
//辅助栈函数申明
void InitStack(Lstack &S);
void Push(Lstack &S,ElemType x);
void Pop(Lstack &S,ElemType &m);
bool IsEmpty(Lstack S);
void GetTop(Lstack S,ElemType &s);
#endif //INC_5_3_3_7_FUNCTION_H
- CreateBiTree.cpp文件
//
// Created by 斋心 on 2023/7/2.
//
#include "function.h "
BiTree CreateBiTree(BiTree &T){
T=NULL;
BiElemType c;
BiTree pnew;
ptag_t phead=NULL,ptail=NULL,listnew,pcur;
int tag=0;//标志孩子结点是否已经插入，防止连续插入空结点的情形
while(scanf("%c",&c)){
if(c=='\n'){
break;
}
if(c=='0'){
pnew=NULL;
listnew=NULL;
}else{
pnew=(BiTree)calloc(1,sizeof(BiNode));
pnew->c=c;
listnew=(ptag_t)calloc(1,sizeof(tag_t));
listnew->p=pnew;
}
if(NULL==T){
phead=ptail=listnew;
pcur=listnew;
T=pnew;
}else{
if(listnew){
ptail->pnext=listnew;
ptail=listnew;
}
if(NULL==pcur->p->lchild&&tag!=1){
pcur->p->lchild=pnew;
tag=1;
}else{
pcur->p->rchild=pnew;
pcur=pcur->pnext;
tag=0;
}
}
}
return T;
}
- queue.cpp文件
//
// Created by 斋心 on 2023/7/2.
//
#include"function.h"
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode *)calloc(1,sizeof(LinkNode));
}
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)calloc(1,sizeof(LinkNode));
s->data=x;
Q.rear->next=s;
Q.rear=s;
}
bool DeQueue(LinkQueue &Q,ElemType &m){
if(Q.front==Q.rear){
return false;
}
LinkNode *q=Q.front->next;
m=q->data;
Q.front->next=q->next;
if(q==Q.rear){
Q.rear=Q.front;
}
free(q);
return true;
}
bool IsEmpty(LinkQueue Q){
return Q.rear==Q.front;
}
- order.cpp文件
//
// Created by 斋心 on 2023/7/2.
//
#include "function.h "
//前序遍历
void PreOrder(BiTree T){
if(T){
putchar(T->c);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree p){
if(p!=NULL){
InOrder(p->lchild);
printf("%c",p->c);
InOrder(p->rchild);
}
}
//后序遍历
void PostOrder(BiTree p){
if(p!=NULL){
PostOrder(p->lchild);
PostOrder(p->rchild);
printf("%c",p->c);
}
}
//层序遍历
void LevelOrder(BiTree T){
LinkQueue Q;//申请辅助队列
InitQueue(Q);
EnQueue(Q,T);//将树的根结点入队
BiTree p;//存储出队的结点
while(!IsEmpty(Q)){ //辅助队列非空，则将队头结点出队打印，并将其左孩子和右孩子依次入队
DeQueue(Q,p);
putchar(p->c);
if(p->lchild){
EnQueue(Q,p->lchild);
}
if(p->rchild){
EnQueue(Q,p->rchild);
}
}
}
- stack.cpp文件
//
// Created by 斋心 on 2023/7/2.
//
#include"function.h"
//带头结点的链栈初始化
void InitStack(Lstack &S){
S=(Lstack)calloc(1,sizeof(stack));
}
//进栈(头插法)
void Push(Lstack &S,ElemType x){
Lstack snew=(Lstack)calloc(1,sizeof(stack));
snew->data=x;
snew->next=S->next;
S->next=snew;
}
//出栈(从头出栈)
void Pop(Lstack &S,ElemType &m){
Lstack q=S->next;
m=q->data;
if(S->next!=NULL){ //栈不空，则出栈
S->next=q->next;
}
free(q);
}
//判断栈空
bool IsEmpty(Lstack S){
if(S->next==NULL){
return 1;
}
return 0;
}
//读取栈顶元素
void GetTop(Lstack S,ElemType &s){
if(S->next!=NULL){
s=S->next->data;
}
}
5.3.3-4 试给出二叉树自下而上，从右到左的层次遍历算法。
#include "function.h"
//5.3.3-4 试给出二叉树自下而上，从右到左的层次遍历算法。
//算法思想：二叉树层次遍历从上至下，从左到右依次访问结点，则将层次遍历输出的结点依次进栈，最后出栈，即可得到自下而上，自右向左的序列。
void RevLevelOrder(BiTree T){
LinkQueue Q;
InitQueue(Q);
LinkStack S;
InitStack(S);
EnQueue(Q,T);//先将根结点入队
while(!IsEmpty(Q)){ //队列非空，则将队头结点出队并入栈，然后如有左右孩子，则将左右孩子入队
DeQueue(Q,T);
Push(S,T);
if(T->lchild){
EnQueue(Q,T->lchild);
}
if(T->rchild){
EnQueue(Q,T->rchild);
}
}
while(!IsEmpty(S)){
Pop(S,T);
printf("%c",T->c);
}
}
int main() {
BiTree tree=NULL;
CreateBiTree(tree);
RevLevelOrder(tree);
return 0;
}
输出结果：
abc0def0g
gfedcba
进程已结束，退出代码为 0
5.3.3-5 假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
#include "function.h"
//5.3.3-5 假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
//算法思想：用last指针指向当前层的最后一个结点，初始时是树根结点入队后队尾指针指向的结点。
//当层次遍历出队元素等于last变量时，则层高变量level加1，
//且last移动到下一层的最后一个结点，即为辅助队列尾指针所指的结点。
//求二叉树高度----非递归
int BtDepth(BiTree T){
LinkQueue Q;
InitQueue(Q);
int level=0;//层高变量
EnQueue(Q,T);
BiTree last=Q.rear->data;//last初始值为树根结点
while(!IsEmpty(Q)){
DeQueue(Q,T);
if(T->lchild){
EnQueue(Q,T->lchild);
}
if(T->rchild){
EnQueue(Q,T->rchild);
}
if(T==last){ //当出队元素等于last时，队列尾指针所指结点即为下一层的最后一个结点
level++;
last=Q.rear->data;
}
}
return level;
}
//求二叉树高度---递归
int BtDepth2(BiTree T){
if(T==NULL){
return 0; //退出函数并返回0
}
int ldep=BtDepth2(T->lchild);
int rdep=BtDepth2(T->rchild);
if(ldep>rdep){
return ldep+1;
}else{
return rdep+1;
}
}
int main() {
BiTree tree=NULL;
CreateBiTree(tree);
int level1,level2;
level1=BtDepth(tree);
level2= BtDepth2(tree);
printf("the height of the bitree is:\n");
printf("%3d%3d",level1,level2);
return 0;
}
输出结果：
abcde
the height of the bitree is:
3 3
进程已结束，退出代码为 0
5.3.3-6 设一颗二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1…n]和B[1…n]中，试编写算法建立该二叉树的二叉链表。
#include <stdio.h>
#include<stdlib.h>
//设一颗二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。
//算法思想：先序序列和中序序列可以唯一确定一棵二叉树。① 根据先序序列确定树或子树的根结点；② 根据中序序列将树划分为左右子树。
// 采用递归算法，直到子树仅剩根结点为止。
typedef char BiElemType;
//二叉树结点的结构体类型申明
typedef struct BiNode{
BiElemType c;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
//先序和中序序列创建二叉树
BiTree PreInCreate(char pre[],char in[],int pre1,int pren,int in1,int inn){
//pre1和pren为先序序列的第一个和最后一个结点下标，in1和inn为中序序列的第一个和最后一个结点下标
BiTree T=(BiTree)calloc(1,sizeof(BiNode));//申请子树根结点
T->c=pre[pre1];//根结点为前序序列的第一个结点值
//划分左右子树
int i,llen,rlen;
for(i=in1;T->c!=in[i];i++); //返回根结点所在中序序列的下标值
llen=i-in1;//左子树中序序列长度
rlen=inn-i;//右子树中序序列长度
//递归创建左子树，退出接口左子树序列长为0
if(llen){
T->lchild=PreInCreate(pre,in,pre1+1,pre1+llen,in1,in1+llen-1);
}else{
T->lchild=NULL;
}
//递归创建右子树
if(rlen){
T->rchild= PreInCreate(pre,in,pren-rlen+1,pren,inn-rlen+1,inn);
}else{
T->rchild=NULL;
}
return T;
}
//先序遍历
void PreOrder(BiTree T){
if(T){
putchar(T->c);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T){
if(T){
InOrder(T->lchild);
putchar(T->c);
InOrder(T->rchild);
}
}
int main() {
char pre[6]="abdec";
char in[6]="dbeac";
BiTree T=PreInCreate(pre,in,0,4,0,4);
printf("\n-------PreOrder---------\n");
PreOrder(T);
printf("\n--------InOrder----------\n");
InOrder(T);
return 0;
}
输出结果：
-------PreOrder---------
abdec
--------InOrder----------
dbeac
进程已结束，退出代码为 0
5.3.3-7 二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。
#include "function.h"
//二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。
//算法思想：具有n个结点的完全二叉树，其1-n号结点与满二叉树一一对应。可采用层次遍历的算法，将所有结点（包括空结点）加入队列。当出队遇到空节点时，
// 判断其后是否有非空结点，如有，则不是完全二叉树。
//判断是否为完全二叉树
bool IsComolete(BiTree T){
LinkQueue Q;
InitQueue(Q);
EnQueue(Q,T);
while(!IsEmpty(Q)){
DeQueue(Q,T);
if(T){ //此处与层次遍历不同，可让空的孩子也入队
EnQueue(Q,T->lchild);
EnQueue(Q,T->rchild);
}else{
}
DeQueue(Q,T);
if(T){
return false;
}
}
return true;
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("\n-----LevelOrder----\n");
LevelOrder(tree);
bool ret= IsComolete(tree);
printf("the bitree is complete:%d",ret);
return 0;
}
输出结果：
abcd0e0
-----LevelOrder----
abcdethe bitree is complete:0
进程已结束，退出代码为 0
5.3.3-8 假设二叉树采用二叉链表存储结构存储，设计一个算法：计算一棵给定二叉树的所有双分支结点个数。
#include "function.h"
// 假设二叉树采用二叉链表存储结构存储，设计一个算法：计算一棵给定二叉树的所有双分支结点个数。
//算法思想：采用递归的思想。
//计算二叉树双分支结点数
int DouNode(BiTree T){
if(T==NULL){ //递归出口，如结点无左右孩子，则返回0
return 0;
}
if(T->lchild&&T->rchild){
return DouNode(T->lchild)+ DouNode(T->rchild)+1; //二分支结点加1，且继续计算左右子树的二分支结点
}else{
return DouNode(T->lchild)+ DouNode(T->rchild);//继续计算左右子树的二分支结点
}
}
int main() {
BiTree tree;
CreateBiTree(tree);
int num= DouNode(tree);
printf("the number of double node is:%d",num);
return 0;
}
输出结果：
abcdef0g0
the number of double node is:2
进程已结束，退出代码为 0
5.3.3-9 设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左右子树进行交换的函数。
#include "function.h"
// 设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左右子树进行交换的函数。
void swap(BiTree T){
if(T){
swap(T->lchild);
swap(T->rchild);
BiTree p;
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
}
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("\n the bitree's levelorder is:\n");
LevelOrder(tree);
swap(tree);
printf("\nthe swaped bitree's levelorder is:\n");
LevelOrder(tree);
return 0;
}
输出结果：
abcd0e0
the bitree's levelorder is:
abcde
the swaped bitree's levelorder is:
acbed
进程已结束，退出代码为 0
5.3.3-10 假设二叉树采用二叉链表存储结构存储，设计一个算法：求先序遍历序列中第k个结点的值。
#include "function.h"
// 假设二叉树采用二叉链表存储结构存储，设计一个算法：求先序遍历序列中第k个结点的值。
//算法思想一：采用先序遍历非递归算法，设置变量j记录输出的先序序列结点数。
BiElemType PreNode1(BiTree T,int k){
Lstack S;
InitStack(S);
BiTree p=T;
int j=0;//记录访问的结点数
while(p||!IsEmpty(S)){
if(p){
j++;
if(j==k){
return p->c;
}
Push(S,p);
p=p->lchild;
}else{
Pop(S,p);
if(p->rchild){
p=p->rchild;
}else{
p=NULL;
}
}
}
}
//算法思想二：采用递归算法。设置全局变量j表示遍历的前序序列结点数。按照前序递归遍历的思想：
// ①当结点为空时，返回特殊字符；
//② 当j==k时，返回结点值；
//③当k!=j时，则递归地在左子树和右子树中查找。
int j=1;//全局变量，前序遍历访问的结点数
BiElemType PreNode2(BiTree T,int k){
if(T==NULL){
return '#';
}
if(j==k){
return T->c;
}
j++;
BiElemType c= PreNode2(T->lchild,k);
if(c!='#'){ //如左子树遍历完，尚未返回第k个的值，则会返回'#'，需要在右子树继续遍历
return c;
}
c= PreNode2(T->rchild,k);
return c;
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("\n the bitree's preorder is:");
PreOrder(tree);
BiElemType c1=PreNode1(tree,4);
BiElemType c2= PreNode2(tree,4);
printf("\n the %dth preorder1 node is: %c,the preorder2 node is:%c\n",4,c1,c2);
return 0;
}
输出结果：
abcde00fg
the bitree's preorder is:abdecfg
the 4th preorder1 node is: e,the preorder2 node is:e
进程已结束，退出代码为 0
5.3.3-11 已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
#include "function.h"
//已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
//算法思想：本题分为两步：① 找到结点值为x的结点；② 递归地删除以x结点为根的子树。
//在查找结点x时，适合采用层次遍历算法；删除以x为结点的子树时，可采用后序遍历递归的思想。
//删除以T为根的子树
void DelTree(BiTree &T){ //沿着后序遍历的路径逐个删除子树结点
if(T){
DelTree(T->lchild);
DelTree(T->rchild);
free(T);
}
}
//查找值为x的结点，并删除该结点的子树
void SearDelXTree(BiTree &T,BiElemType x){
LinkQueue Q;
InitQueue(Q);
if(T->c==x){ //如树根结点的值为x，则直接删除整棵树
DelTree(T);
return;
}
EnQueue(Q,T);
BiTree p;//遍历结点
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p->lchild){
if(p->lchild->c==x){
DelTree(p->lchild);
p->lchild=NULL;//删除后，p的左孩子为空
}else{
EnQueue(Q,p->lchild);
}
if(p->rchild){
if(p->rchild->c==x){
DelTree(p->rchild);
p->rchild=NULL;
}else{
EnQueue(Q,p->rchild);
}
}
}
}
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("\n the tree's levelorder is:");
LevelOrder(tree);
SearDelXTree(tree,'a');
printf("\n the new tree's levelorder is:");
LevelOrder(tree);
return 0;
}
输出结果：
tbcaef0cg
the tree's levelorder is:tbcaefcg
the new tree's levelorder is:tbcef
进程已结束，退出代码为 0
5.3.3-12 在二叉树中查找值为x的结点，编写算法打印值为x的结点的所有祖先结点，假设值为x的结点不多于一个。
#include "function.h"
//在二叉树中查找值为x的结点，编写算法打印值为x的结点的所有祖先结点，假设值为x的结点不多于一个。
//算法思想：非递归后序遍历栈中存放了从根结点到任一结点的路径，即可找到任一结点的所有祖先结点。
//打印值为x的结点的所有祖先结点
void SearXTree(BiTree T,BiElemType x){
Lstack S;
InitStack(S);
BiTree p=T,r=NULL;
while(p||!IsEmpty(S)){
if(p){
Push(S,p);
p=p->lchild;
}else{
GetTop(S,p);
if(p->rchild&&p->rchild!=r){
p=p->rchild;
}else{
Pop(S,p);
if(p->c==x){
printf("the anscestors of %c node are:\n",x);
while(!IsEmpty(S)){
Pop(S,p);
printf("%c",p->c);
}
}
r=p;
p=NULL;
}
}
}
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("the tree's postorder is:\n");
PostOrder(tree);
printf("\n--------------------------\n");
SearXTree(tree,'f');
}
输出结果：
the tree's postorder is:
hdebfgca
--------------------------
the anscestors of f node are:
ca
进程已结束，退出代码为 0
5.3.3-14 假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树的宽度（即具有结点数最多的那一层的结点个数）。
#include "function.h"
//假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树的宽度（即具有结点数最多的那一层的结点个数）。
//算法思想：采用层次遍历的思想。用rear标志二叉树每一层的最后一个结点，当出队元素p==rear时，此时队列尾指针指向的元素恰好是下一层的最后一个结点。
int TreeWidth(BiTree T){
LinkQueue Q;
InitQueue(Q);
EnQueue(Q,T);
BiTree rear=Q.rear->data;//标志每一层最后一个结点的指针
BiTree p=NULL;//层次遍历指针
int i=0,n=0;
while(!IsEmpty(Q)){
while(p!=rear){ //当出队元素p!=rear时，则持续层次遍历，并用i记录出队的结点数；当p==rear时，i恰好是该层的结点数
DeQueue(Q,p);
i++; //记录每一层的结点数量
if(p->lchild){
EnQueue(Q,p->lchild);
}
if(p->rchild){
EnQueue(Q,p->rchild);
}
}
rear=Q.rear->data;//当p==rear时，rear更新为指向下一层的最后结点
if(n<=i){ //更新为结点数最多的那一层的结点个数
n=i;
}
i=0; //重置i，记录下一层的结点数
}
return n;
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("the tree's levelorder is:\n");
LevelOrder(tree);
int n= TreeWidth(tree);
printf("\nthe width of tree is:%d",n);
}
输出结果:
abcd0e0fghi
the tree's levelorder is:
abcdefghi
the width of tree is:4
进程已结束，退出代码为 0
5.3.3-15 设有一棵满二叉树（所有结点值均不同），已知其先序序列为pre,设计一个算法求其后序序列post。
#include "function.h"
//设有一棵满二叉树（所有结点值均不同），已知其先序序列为pre,设计一个算法求其后序序列post。
//对于一棵满二叉树，任意一个结点的左、右子树均含有相等的结点数。同时，先序序列的第一个结点作为后序序列的最后一个结点。采用递归算法。
//满二叉树前序序列转换为后序序列
void PrePost(BiElemType pre[],int pre1,int pren,BiElemType post[],int post1,int postn){
int half;
if(pren>=pre1){
post[postn]=pre[pre1];//后序序列的最后一个结点是先序序列的第一个结点
half=(pren-pre1)/2;
PrePost(pre,pre1+1,pre1+half,post,post1,post1+half-1);
PrePost(pre,pre1+half+1,pren,post,post1+half,postn-1);
}
}
int main() {
char pre[8]="abdecfg";
printf("pre is: %s\n",pre);
char post[8];
PrePost(pre,0,6,post,0,6);
printf("post is: %s\n",post);
}
输出结果：
pre is: abdecfg
post is: debfgca
进程已结束，退出代码为 0
5.3.3-16 设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head，二叉树按二叉链表形式存储，链接时用叶结点的右指针来存放单链表指针。
#include "function.h"
//设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head，二叉树按二叉链表形式存储，链接时用叶结点的右指针来存放单链表指针。
//算法思想：二叉树先序中序和后序遍历的算法，对于叶子结点的访问都是从左到右。此处采用先序遍历的算法。设置指针pre，标志叶子结点的前驱指针。
BiTree head,pre=NULL;
BiTree Link(BiTree T){
if(T){
if(T->lchild==NULL&&T->rchild==NULL){
if(pre==NULL){ //连接第一个叶子结点
head=T;
pre=T;
}else{ //其它叶子结点
pre->rchild=T;
pre=T;
}
}
Link(T->lchild);
Link(T->rchild);
pre->rchild=NULL;//处理最后一个结点
}
return head;
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("preorder:\n");
PreOrder(tree);
printf("\nlink is:\n");
Link(tree);
PreOrder(head);
}
输出结果：
abc000f
preorder:
abcf
link is:
bf
进程已结束，退出代码为 0
5.3.3-17 试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似，指的是T1和T2都是空的二叉树或都只有一个根结点；或T1的左子树和T2的右子树是相似的，且T1的右子树和T2的右子树是相似的。
#include "function.h"
//试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似，指的是T1和T2都是空的二叉树或都只有一个根结点；
// 或T1的左子树和T2的右子树是相似的，且T1的右子树和T2的右子树是相似的。
//算法思想：采用递归的思想。如T1和T2均是空，则是相似的；如T1或T2一个空，一个非空，则是非相似的。然后递归比较其左右子树。
//1和T2都只有一个根结点的情况，可以包括在本递归算法中。
bool similar(BiTree T1,BiTree T2){
bool retl,retr;
if(T1==NULL&&T2==NULL){
return true;
}else if(T1==NULL||T2==NULL){
return false;
}
retl=similar(T1->lchild,T2->lchild);
retr= similar(T1->rchild,T2->rchild);
return retl&&retr;
}
int main() {
BiTree T1,T2;
printf("input T1 nodes:\n");
CreateBiTree(T1);
printf("input T2 nodes:\n");
CreateBiTree(T2);
bool ret=similar(T1,T2);
if(ret){
printf("T1 and T2 is similar\n");
}else{
printf("T1 and T2 is not similar\n");
}
}
输出结果：
input T1 nodes:
abc
input T2 nodes:
defg
T1 and T2 is not similar
进程已结束，退出代码为 0
5.3.3-19 计算二叉树的带权路径长度（WPL）。
#include "function.h"
//5.3.3-19 计算二叉树的带权路径长度（WPL）。
//算法思想：利用层次遍历算法计算树的带权路径长度。层次遍历算法可以获得各个结点所在的层次，如为叶子结点，则计算其带权路径长度。
int WPL_levelorder(BiTree T){
LinkQueue Q;
InitQueue(Q);
EnQueue(Q,T);
BiTree p;//遍历指针
BiTree ptail=Q.rear->data;//每一层最后一个结点
int level=0,wpl=0;
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p->lchild){
EnQueue(Q,p->lchild);
}
if(p->rchild){
EnQueue(Q,p->rchild);
}
if(p->lchild==NULL&&p->rchild==NULL){ //如为叶子结点，则累加计算带权路径长度
wpl+=p->weight*level;
}
if(p==ptail){ //如结点为该层最后一个结点，则层数加1，并将指针指向下一层最后一个结点
level++;
ptail=Q.rear->data;
}
}
return wpl;
}
int main() {
BiTree tree;
CreateBiTree(tree);
WeightOfNode(tree);
printf("PreOrder:\n");
PreOrder(tree);
int wpl;
wpl= WPL_levelorder(tree);
printf("\nWPL of the tree is:%d",wpl);
}
输出结果：
abcd0ef
input weight:1
input weight:2
input weight:3
input weight:4
input weight:5
input weight:6
PreOrder:
a:1 b:2 d:3 c:4 e:5 f:6
WPL of the tree is:28
进程已结束，退出代码为 0
5.3.3-20 请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。
#include "function.h"
//请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。
//算法思想：中缀表达式由二叉树中序遍历得到，其中需要加上括号。
// 除根结点和叶子结点外，遍历到其它结点时，在遍历其左子树之前加上左括号，遍历完右子树加上右括号。
void TreeToExp(BiTree T,int deep){
if(T==NULL){ //遍历至空结点则返回
return;
}else if(T->lchild==NULL&&T->rchild==NULL){ //叶子结点则直接打印结点值
printf("%c",T->c);
}else{
if(deep>1){ //根结点不加括号
printf("(");
}
TreeToExp(T->lchild,deep+1);
printf("%c",T->c);
TreeToExp(T->rchild,deep+1);
if(deep>1){ //根结点不加括号
printf(")");
}
}
}
void TreeToE(BiTree T){
TreeToExp(T,1);
}
int main() {
BiTree tree;
CreateBiTree(tree);
printf("InOrder:\n");
InOrder(tree);
printf("\nExpression is:\n");
TreeToE(tree);
}
输出结果：
+*-ab0-0000cd
InOrder:
a*b+-c-d
Expression is:
(a*b)+(-(c-d))
进程已结束，退出代码为 0