35.树与二叉树练习（1）（王道第5章综合练习）

【所用的树，队列，栈的基本操作详见上一节代码】

试题1（王道5.3.3节第3题）：

编写后序遍历二叉树的非递归算法。

参考：34.二叉链树的C语言实现_北京地铁1号线的博客-CSDN博客https://blog.csdn.net/qq_54708219/article/details/133581706

试题2（王道5.3.3节第4题）：

给出二叉树自下而上，从右到左的层次遍历算法。

这道题很显然就是层次遍历算法调个个，加个栈即可实现：

//层次遍历（自下而上，从右到左）
void LevelOrder2(BiTree T){Queue q;InitQueue(q);Sqstack S;InitStack(S);BiTree p = T;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);InsertSqstack(S, p);if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}while(S.top != -1){p = DeleteSqstack(S, p);printf("%c", p->data);}
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
二叉树的层次遍历序列是：ABCDE
二叉树的层次遍历（自下而上，自右向左）序列是：EDCBA

试题3（王道5.3.3节第5题）：

设计非递归算法求二叉树的高度。

此题采用层次遍历，附设一个指针a：

//利用层次遍历实现非递归计算树的深度
int LevelOrderDepth(BiTree T){int Depth = 0;if(!T)return Depth;else{Queue q;InitQueue(q);BiTree p = T;InsertQueue(q, p);Depth = 1;int a = q.rear;  //指针a指向队尾，也就是这一层最后一个元素while(!IsQueueEmpty(q)){if(q.front==a){  //这个时候说明这一层出完了，此时rear就是下一行的末尾结点a = q.rear;Depth = Depth + 1;}p = DeleteQueue(q, p);if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}return Depth;}
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
二叉树的深度是（非递归算法）：3

试题4（王道5.3.3节第6题）：

设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存放在两个数组A和B中，试编写算法建立该二叉树的二叉链表。

仍需要采用递归操作，这里要想办法根据前序序列找到根结点，然后在中序序列找根结点，从而确定哪些结点属于左子树，哪些结点属于右子树。

//由先序序列和中序序列建立二叉树
BiTree CreateBiTreeviaOrders(char a[],char b[],int x1,int y1,int x2,int y2){//x1,y1工作在前序序列中，x2,y2工作在中序序列中BiTree T;T = (BiTree)malloc(sizeof(BiTNode));T->data = a[x1];  //前序序列的第一个结点就是根结点int llen, rlen;for (int i = x2; i <= y2; i++){  //在中序序列找根结点if(b[i] == a[x1]){llen = i - x2;  //左子树的序列长度（结点个数）rlen = y2 - i;  //右子树的序列长度（结点个数）}}if (llen == 0)T->lchild = NULL;elseT->lchild = CreateBiTreeviaOrders(a, b, x1 + 1, x1 + llen, x2, x2 + llen - 1);if (rlen == 0)T->rchild = NULL;elseT->rchild = CreateBiTreeviaOrders(a, b, y1 - rlen + 1, y1, y2 - rlen + 1, y2);return T;
}int main(){BiTree T;char a[6] = {'A', 'B', 'C', 'D', 'E', 'F'};  //先序序列char b[6] = {'C', 'B', 'A', 'E', 'D', 'F'};  //中序序列T = CreateBiTreeviaOrders(a, b, 0, 5, 0, 5);  //初始必须是0和数组长度减一printf("该二叉树的后序遍历序列是：");PostOrderTraverse(T);  //输出后序序列进行验证return 0;
}

这里以王道5.3.3节单选15题进行验证，输出结果就是A选项。

该二叉树的后序遍历序列是：CBEFDA

试题5（王道5.3.3节第7题）：

二叉树按二叉链表存储，写一个判别给定二叉树是否是完全二叉树的算法。

此题的思路是借助层次遍历和队列，当队列中输出空结点的时候，如果此时队列还有非空结点说明不是完全二叉树。注意这里输入和验证的都是扩展二叉树，所以去掉了层次遍历中的结点非空判断。

//判断是否是完全二叉树
bool IfCompleteTree(BiTree T){Queue q;InitQueue(q);BiTree p = T;if(!p)return true;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);if(p!=NULL){InsertQueue(q, p->lchild);InsertQueue(q, p->rchild);}else{int a = q.front;while(a!=q.rear){if(q.data[a]!=NULL)return false;a = (a + 1) % MAXSIZE;}return true;}   }
}int main(){BiTree T;printf("输入二叉树的前序序列，#代表空子树:\n");CreateBiTree(T);printf("二叉树创建成功！\n");printf("该二叉树是否是完全二叉树？%d", IfCompleteTree(T));return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
该二叉树是否是完全二叉树？1输入二叉树的前序序列，#代表空子树:
AB##CD##E##
二叉树创建成功！
该二叉树是否是完全二叉树？0

试题6（王道5.3.3节第8题）：

设二叉树采用二叉链表存储结构，设计算法计算给定二叉树的双分支结点个数。

递归算法：

//判断是否是完全二叉树
int TwobranchNodes(BiTree T){if(T==NULL)return 0;else if(T->lchild!=NULL&&T->rchild!=NULL)return TwobranchNodes(T->lchild) + TwobranchNodes(T->rchild) + 1;elsereturn TwobranchNodes(T->lchild) + TwobranchNodes(T->rchild);
}

非递归算法（层次遍历逐个结点检查）：

//判断是否是完全二叉树
int TwobranchNodes(BiTree T){int a = 0;Queue q;InitQueue(q);BiTree p = T;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);if(p->lchild!=NULL && p->rchild!=NULL)a = a + 1;if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}return a;
}

试题7（王道5.3.3节第9题）：

设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左右子树进行交换的函数。

此题同题6一样也可以用递归或层次遍历的方法，这里给出非递归的方法：

//把二叉树的左右子树交换
int ChangeTwobranch(BiTree &T){Queue q;InitQueue(q);BiTree p = T;BiTree r;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);if(p->lchild!=NULL || p->rchild!=NULL){r = p->lchild;p->lchild = p->rchild;p->rchild = r;}if (p->lchild != NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
该二叉树的层次遍历序列是：ACBED

试题8（王道5.3.3节第10题）：

假设二叉树采用二叉链存储结构存储，设计算法求先序遍历序列中第k个结点的值。

这里使用一个计数器即可：

//输出前序遍历的第x个元素
void PreOrderx(BiTree T,int x){int a = 0;BiTree p = T; //p是遍历指针Sqstack S;InitStack(S);while(p != NULL|| !IsStackEmpty(S)){if(p){a = a + 1;if(a == x){printf("第%d个元素是：%c", x, p->data);break;}  InsertSqstack(S, p);p = p->lchild;}else{p = DeleteSqstack(S, p);p = p->rchild;}}
}

当然也可以采用递归，注意这里的计数器必须写在全局变量里，否则每次调用递归都会从零开始：

//输出前序遍历的第x个元素
int a = 0;  //计数器
void PreOrderx(BiTree T,int x){if (T!=NULL){a = a + 1;if(a==x)printf("前序遍历序列的第%d个元素是：%c", x, T->data);PreOrderx(T->lchild,x);PreOrderx(T->rchild,x);}
}int main(){BiTree T;printf("输入二叉树的前序序列，#代表空子树:\n");CreateBiTree(T);printf("二叉树创建成功！\n");PreOrderx(T, 3);return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
前序遍历序列的第3个元素是：D

试题9（王道5.3.3节第11题）：

已知二叉树以二叉链表存储，编写算法完成：对于树中的每个值为x的结点，删去以它为根的子树，并释放相应空间。

仍然是与层次遍历结合：

//这个函数用来删除树T
void Free(BiTree &T){if(T!=NULL){Free(T->lchild);Free(T->rchild);free(T);}
}//对值为x的结点，删除以它为根的子树
void Freex(BiTree &T,char x){Queue q;InitQueue(q);BiTree p = T;InsertQueue(q, p);while(!IsQueueEmpty(q)){p = DeleteQueue(q, p);if(p->data == x){Free(p->lchild);  //这样写保留了当前结点Free(p->rchild);p->lchild = NULL;p->rchild = NULL;}if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}
}int main(){BiTree T;printf("输入二叉树的前序序列，#代表空子树:\n");CreateBiTree(T);printf("二叉树创建成功！\n");printf("当前二叉树的层次遍历序列是：");LevelOrder(T);printf("\n");Freex(T, 'B');  //删除以B为根结点的树printf("当前二叉树的层次遍历序列是：");LevelOrder(T);printf("\n");return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDE
当前二叉树的层次遍历序列是：ABC输入二叉树的前序序列，#代表空子树:
ABD###CE##F##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDEF
当前二叉树的层次遍历序列是：ABCEF

试题10（王道数据结构5.3.3节第12题）：

编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个。

此题的算法十分典型：它用的是非递归后序遍历算法，这种算法需要借助栈来实现，当访问到值为x的结点的时候，栈中所有元素就是该结点的祖先，依次打印输出即可。有关非递归后序遍历算法的代码在上一节。

//寻找给定结点的所有祖先结点，采用后续遍历的非递归算法
void FindParents(BiTree T,char x){Sqstack S;InitStack(S);BiTree p = T;BiTree r = NULL;  //r用来记录访问结点的前一个结点while(p||!IsStackEmpty(S)){if(p){InsertSqstack(S, p);p = p->lchild;}else{p = S.data[S.top];  //读栈顶元素（但不出栈）if(p->rchild&&p->rchild!=r){p = p->rchild;}else{p = DeleteSqstack(S, p);if(p->data == x){printf("%c", p->data);break;}r = p;p = NULL;}}}while(!IsStackEmpty(S)){  //这个时候栈里的元素全部是结点的祖先p = DeleteSqstack(S, p);printf("%c", p->data);}
}int main(){BiTree T;printf("输入二叉树的前序序列，#代表空子树:\n");CreateBiTree(T);printf("二叉树创建成功！\n");printf("当前二叉树的层次遍历序列是：");LevelOrder(T);printf("\n");printf("当前二叉树中结点E的祖先结点是：");FindParents(T, 'E');return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDE
当前二叉树中结点E的祖先结点是：EBA

试题11（王道数据结构5.3.3节第13题）：

给出二叉链树中两个结点的指针p和q，试编写算法求解p和q的公共祖先结点r。

此题和上一题很像，分别求出p和q的祖先然后比较即可。

//寻找给定结点的所有祖先结点，采用后续遍历的非递归算法，和上一题不同的是，本题以栈的形式返回
Sqstack FindParents(BiTree T,char x){Sqstack S;InitStack(S);BiTree p = T;BiTree r = NULL;  //r用来记录访问结点的前一个结点while(p||!IsStackEmpty(S)){if(p){InsertSqstack(S, p);p = p->lchild;}else{p = S.data[S.top];  //读栈顶元素（但不出栈）if(p->rchild&&p->rchild!=r){p = p->rchild;}else{p = S.data[S.top];if(p->data == x){break;}p = DeleteSqstack(S, p);r = p;p = NULL;}}}return S;
}
//有了两个栈我们就可以遍历然后找到祖先结点了
//注意这里最差也能返回整棵二叉树的根结点，或者返回其中一个结点时，代表一个结点就是另一个结点的祖先
BiTree FindSameParents(BiTree T,char a,char b){Sqstack S1 = FindParents(T, a);Sqstack S2 = FindParents(T, b);int same = -1;  //same用来遍历两个栈，并指向最后一个相同的祖先结点while(S1.data[same+1] == S2.data[same+1]){same = same + 1;}printf("%c", S1.data[same]->data);return S1.data[same];
}int main(){BiTree T;printf("输入二叉树的前序序列，#代表空子树:\n");CreateBiTree(T);printf("二叉树创建成功！\n");printf("当前二叉树的层次遍历序列是：");LevelOrder(T);printf("\n");printf("当前二叉树中结点E，F的祖先结点是：");FindSameParents(T, 'E', 'F');  //求E,F的祖先结点return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD###CE##F##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDEF
当前二叉树中结点E，F的祖先结点是：C

试题12（王道数据结构5.3.3节第14题）：

假设二叉树采用二叉链表存储，设计一个算法求非空二叉树的宽度（也就是结点数最多的那一层的结点个数）。

此题仍然可以利用层次遍历把每层的结点数输出，存在一个数组里面然后找出最大值：

//求非空二叉树的宽度，借助层次遍历把每层的结点数都求出来
int LevelOrderWidth(BiTree T){Queue q;InitQueue(q);BiTree p = T;InsertQueue(q, p);int a = q.front;  //a指针指向这一层的第一个结点int b = q.rear;  //b指针指向这一层的第一个结点int num = 1;     //输出这一层的结点个数int numarray[10];  //把各层的结点个数存在一个数组里int depth = 0;  //深度，实际深度是depth+1，因为numarray数组下标从0开始numarray[depth] = num;while(!IsQueueEmpty(q)){if(q.front == b){  //说明这一层出完了a = q.front;  //a指向下一层第一个结点b = q.rear;  //b指向下一层最后一个结点num = (b - a > 0) ? (b - a) : (b - a + MAXSIZE);  //循环队列三目运算符判断depth = depth + 1;numarray[depth] = num;}p = DeleteQueue(q, p);if(p->lchild!=NULL)InsertQueue(q, p->lchild);if(p->rchild!=NULL)InsertQueue(q, p->rchild);}//到此numarray存储了每层的结点数，接下来找其中的最大值输出num = 1;for (int i = 0; i <= depth;i++){printf("%d", numarray[i]);if(numarray[i] > num)num = numarray[i];}return num;
}int main(){BiTree T;printf("输入二叉树的前序序列，#代表空子树:\n");CreateBiTree(T);printf("二叉树创建成功！\n");printf("当前二叉树的层次遍历序列是：");LevelOrder(T);printf("\n");printf("各层的结点数是：");printf("二叉树的宽度是：%d",LevelOrderWidth(T));return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABDF##G##E##CH###
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDEHFG
各层的结点数是：1232二叉树的宽度是：3