【所用的树,队列,栈的基本操作详见上一节代码】
试题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