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

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

试题1(王道5.3.3节第3题):

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

参考:34.二叉链树的C语言实现_北京地铁1号线的博客-CSDN博客icon-default.png?t=N7T8https://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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/153906.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用asp.net core web api创建web后台,并连接和使用Sql Server数据库

前言&#xff1a;因为要写一个安卓端app&#xff0c;实现从服务器中获取电影数据&#xff0c;所以需要搭建服务端代码&#xff0c;之前学过C#&#xff0c;所以想用C#实现服务器段代码用于测试&#xff0c;本文使用C#语言&#xff0c;使用asp.net core web api组件搭建服务器端&…

前端uniapp如何修改下拉框uni-data-select下面的uni-icons插件自带的图片【修改uniapp自带源码图片/图标】

目录 未改前图片未改前源码未改前通过top和bottom 和修改后图片转在线base64大功告成最后 未改前图片 未改前源码 然后注释掉插件带的代码&#xff0c;下面要的 未改前通过top和bottom 和修改后 找到uni-icons源码插件里面样式 图片转在线base64 地址 https://the-x.cn/b…

图像上传功能实现

一、后端 文件存放在images.path路径下 package com.like.common;import jakarta.servlet.ServletOutputStream; import jakarta.servlet.http.HttpServletResponse; import org.springframework.beans.factory.annotation.Value; import org.springframework.web.bind.annot…

大数据编程实验3 熟悉常用的HBase操作前期准备

一、实验目的 &#xff08;1&#xff09;理解HDFS在Hadoop体系结构中的角色&#xff1b; &#xff08;2&#xff09;熟练使用HDFS操作常用的Shell命令&#xff1b; &#xff08;3&#xff09;熟悉HDFS操作常用的Java API。 二、实验平台 1. 操作系统&#xff1a;Linux&#x…

【JavaEE】多线程进阶(一)饿汉模式和懒汉模式

多线程进阶&#xff08;一&#xff09; 文章目录 多线程进阶&#xff08;一&#xff09;单例模式饿汉模式懒汉模式 本篇主要引入多线程进阶的单例模式&#xff0c;为后面的大冰山做铺垫 代码案例介绍 单例模式 非常经典的设计模式 啥是设计模式 设计模式好比象棋中的 “棋谱”…

springboot项目中后台文件上传处理

参考地址:http://www.gxcode.top/code 文件上次核心处理代码: @Autowired private FileUpload fileUpload; //获取资源对象:file-upload-prod.properties@ApiOperation(value = "用户头像修改", notes = "用户头像修改", httpMethod =

Mall脚手架总结(三) —— MongoDB存储浏览数据

前言 通过Elasticsearch整合章节的学习&#xff0c;我们了解SpringData框架以及相应的衍生查询的方式操作数据读写的语法。MongoDB的相关操作也同样是借助Spring Data框架&#xff0c;因此这篇文章的内容比较简单&#xff0c;重点还是弄清楚MongoDB的使用场景以及如何通过Sprin…

相机坐标系之间的转换

一、坐标系之间的转换 一个有4个坐标系&#xff1a;图像坐标系、像素坐标系、相机坐标系、世界坐标系。 1.图像坐标系和像素坐标系之间的转换 图像坐标系和像素坐标系在同一个平面&#xff0c;利用平面坐标系之间的转换关系可以之知道两个坐标系变换的公式&#xff0c;并且该…

JRebel在IDEA中实现热部署 (JRebel实用版)

JRebel简介&#xff1a; JRebel是与应用程序服务器集成的JVM Java代理&#xff0c;可使用现有的类加载器重新加载类。只有更改的类会重新编译并立即重新加载到正在运行的应用程序中&#xff0c;JRebel特别不依赖任何IDE或开发工具&#xff08;除编译器外&#xff09;。但是&…

PlantUML 绘图

官网 https://plantuml.com/zh/ 示例 绘制时序图 USB 枚举过程 PlantUML 源码 startuml host <-- device : device insert host note right : step 1 host -> device : get speed, reset, speed check note right : step 2 host -> device …

数据结构 | (二) List

什么是 List 在集合框架中&#xff0c; List 是一个接口&#xff0c;继承自 Collection 。 Collection 也是一个接口 &#xff0c;该接口中规范了后序容器中常用的一些方法&#xff0c;具体如下所示&#xff1a; Iterable 也是一个接口&#xff0c;表示实现该接口的类是可以逐个…

博弈论——动态博弈

动态博弈 0 引言 前面一篇文章介绍了博弈过程中的三个分类&#xff1a;静态博弈、动态博弈、重复博弈。今天具体讲讲动态博弈的处理方法。 博弈论——博弈过程 1 概念 首先还是介绍一下动态博弈的概念&#xff0c;即博弈中各博弈方的选择和行动不仅有先后次序&#xff0c;而…

Cesium热力图

二、代码 <!doctype html> <html><head><meta charset"utf-8"><link rel"stylesheet" href"./css/common.css"><title>热力图</title><script src"./js/config.js"></script>…

使用python查找指定文件夹下所有xml文件中带有指定字符的xml文件

文件夹目录如下&#xff08;需要递归删除文件夹下的.DS_Store文件&#xff09;&#xff1a; labels文件夹下面是xml文件&#xff1a; import os import os.pathpath "name/labels" files os.listdir(path) # 得到文件夹下所有文件名称 s []for xmlFile in files:…

k8spod就绪检查失败

pod 一直未就绪 kube-system metrics-server-7764f6c67c-2kts9 0/1 Running 0 10m kubect describe 查看 就绪探针未通过 Normal Started 3m19s kubelet Started container metrics-server Warning Unhealthy 5s (x20 over 2m55s) kubelet Readiness probe failed: HTTP probe…

【MySQL】表的基础增删改查

前面我们已经知道怎么来创建表了&#xff0c;接下来就来对创建的表进行一些基本操作。 这里先将上次创建的表删除掉&#xff1a; mysql> use test; Database changedmysql> show tables; ---------------- | Tables_in_test | ---------------- | student | -----…

数据库sql查询成绩第二高

select * from propro; #查询成绩第二高 select max(id) from propro where id <(select max(id) from propro); #查询成绩第二高的第二种方式 select * from (select * from propro order by id desc limit 2) as b order by id asc limit 1;

postgresql中的近一周,近一月,近三月,近一年日期段拆分

统计中经常会遇到,近一周,近一月,近三月,近一年数据统计,下面提供了postgresql拆分日期段的sql -- 近一周,每一天起止时间 select generate_series startDate,generate_series interval 1 day endDate from generate_series( NOW()::date interval -6 day, now()::timest…

【开源电商网站】(2),使用docker-compose和dockerfile进行配置,设置自定义的镜像,安装插件,增加汉化包,支持中文界面汉化。

项目相关代代码地址 相关内容&#xff1a; https://blog.csdn.net/freewebsys/category_12461196.html 原文地址&#xff1a; https://blog.csdn.net/freewebsys/article/details/133666433 包括以下运行的详细代码&#xff1a; https://gitee.com/study-demo-all/oscommerc…

【Python】语言学习

之前总觉得python简单&#xff0c;不当回事&#xff0c;直到自己动手连输出都写不出来。。于是开一篇专门练python的博客。 输出 Python初相识 (educoder.net) 常规输出 print("向上&#xff1a;%.2f,向下&#xff1a;%.2f" %(pow(1.001, 365),pow(0.999, 365))) …