实验四 树和二叉树及其应用(I)
13页1、1姓名姓名学号学号实实验验项项目目树和二叉树及其应用(I)实实验验内内容容1建立二叉树的二叉链表存储结构,实现二叉树的前序、中序、后序递归遍历。 二叉链表存储结构定义参见教材第 127 页。 遍历算法参见教材第 128-129 页。 2编写递归算法,计算二叉树中叶子结点的数目。 (题集第 42 页 6.42) 3编写递归算法,计算二叉树的深度。 (题集第 43 页 6.44)算法设计与程序实现:算法设计与程序实现:算算法法分分析析本次实验主函数采用顺序结构,主函数调用自己编写的头文件DataStructure_BinaryTree.h中的相关功能函数,完成实验要求。程序实现: 1、二叉树的遍历:实验分别递归与非递归的方法分别进行了先序、中序、后 序和层序遍历。由于先序、中序、后序的递归遍历实现算法非常类似,所以以下的 算法具体实现只对递归的先序遍历和层序遍历以及非递归的先序遍历、后序遍历和 层序遍历作详细的分析说明。 2、二叉树的基本操作: (1) 求二叉树的深度; (2) 求二叉树中叶子结点的个数; (3) 先序交换二叉树; (4) 查找以指定元素值为的根节点的根子树; (5) 删除
2、以指定元素值为的根节点的根子树; (6) 判断二叉树是否为完全二叉树。以下分别以上的基本操作算法的具体实现作了详细的分析说明。1 1、二叉树的遍历、二叉树的遍历 递归先序遍历:先序遍历二叉树的原则是当二叉树不为空时,先访问根结点, 再次先序遍历左子树,最后先序遍历右子树,否则进行空操作(递归结束的条件) 。按照以上先序遍历的原则,采取递归的方法很容易完成程序的具体实现。 递归层序遍历:层序遍历顾名思义从根结点出发从左到右逐层进行访问,由此 可以通过控制层次数进而进行逐层遍历,当层次数不为零时,层次数递减递归 遍历左、右子树,当层次数为零时(递归结束条件),访问该节点。遍历时可不 比事先知道二叉树的深度(用于层次数递增边界控制),当当前层次数下访问失 败并返回,则当前层次数即为二叉树的深度。以上遍历中对每一层遍历都需从2根结点出发。 非递归先序遍历:在根指针不空的情况下,访问根结点,根指针域压栈,继续 遍历左子树,循环上诉操作,当左子树指针为空(循环结束条件,同时也是遍历 右子树的条件),此时表明根指针已空, 本左子树遍历完毕,然后退栈返回上 一层,弹出的指针即此时根结点指针,继续遍历右
3、子树未曾访问的结点。 非递归中序遍历:如同此法,中序与先序的不同是不能首先访问根结点,而是 要先访问作孩子节点,要使根结点能够被访问,就要求此时根结点的左孩子为 空,这样根结点就能访问了,故访问操作是在根指针退栈后进行访问的。 非递归后序遍历:后序遍历与上面的先序、中序遍历的不同是也访问根结点的 条件,即当根结点的右指针域为空或右孩子指针指向的节点已被访问过。由此 算法是只要根指针不空时,将根指针进栈,遍历左子树,当根指针为空(根节点 的左孩子指针为空,该指针并没有进栈),取出栈顶指针,判断右孩子指针是否 为空或已被访问过,如果上述条件成立则访问根结点,退栈并更新用于记录被 访问的指针。 非递归层序遍历:根据二叉树的特性,使用队列这种数据结构,出队列一个节 点指针,入队列两个节点指针,出队列指针结点的左右孩子指针即为入队列的 指针(当访问成功才入队列),通过上述操作即可实现层序遍历。 2 2、二叉树的基本操作、二叉树的基本操作 求二叉树的深度:求二叉树的深度即求得左右子树的深度(左右子树深度最大值) 加 1,当然求左右子树的深度即求左右子树的左右子树的深度加 1,由此递归下 去,当子树
4、为空时(递归结束条件),返回 0,然后逐层向上其的二叉树深度。 求二叉树中叶子结点的个数:叶子结点即左右子树皆为空的节点。由此选择递 归就很容易实现,从根结点开始进行遍历,判断当前结点的左右子树是否为空, 不为空则继续访问下一个节点,为空则使叶子结点数加 1,继续查找其他的节点。先序交换二叉树:当根指针不空时,交换左右子树指针,然后交换左子树的左 右孩子指针,如此递归操作,当当前的根指针为空时,返回,交换右子树,如 此就完成了二叉树的交换。 查找以指定元素值为的根节点的根子树:查找根遍历是相同的,只是把遍历的 具体应用函数改为判断访问的节点的数据是否等于指定的数据,当找到则返回 当前节点的根指针,若全部访问结束都还没栈顶则返回失败。 删除以指定元素值为的根节点的根子树:查找指定元素的操作可通过上诉函数 完成,至此只需要调用删除二叉树函数,至于删除二叉树的算法是当根指针不 空时,依次释放左右子树的内存,然后释放根结点,当然释放左右子树时又是 先释放左右子树的左右子树的内存,如此进行递归操作,当根指针为空时,返 回。 判断二叉树是否为完全二叉树:判断二叉树是否为完全二叉树可以转化为判断 二
《实验四 树和二叉树及其应用(I)》由会员飞***分享,可在线阅读,更多相关《实验四 树和二叉树及其应用(I)》请在金锄头文库上搜索。
人教版一年级下册数学第二单元20以内的退位减法测试卷精品【考试直接用】
人教版一年级下册数学第二单元20以内的退位减法测试卷(实用)word版
人教版一年级下册数学第二单元20以内的退位减法测试卷及答案(夺冠)
人教版一年级下册数学第二单元20以内的退位减法测试卷(典型题)
人教版一年级下册数学第二单元20以内的退位减法测试卷精品(a卷)
人教版一年级下册数学第二单元20以内的退位减法测试卷及答案【精品】
部编版二年级上册道德与法治期中测试卷 (考试直接用)
部编版二年级上册道德与法治期中测试卷 带答案(培优)
部编版二年级上册道德与法治期中测试卷 含答案(精练)
部编版二年级上册道德与法治期中测试卷 及答案【各地真题】
部编版二年级上册道德与法治期中测试卷 及完整答案【名校卷 】
部编版二年级上册道德与法治期中测试卷 【考点精练】
部编版三年级上册道德与法治期末测试卷 (重点)
部编版三年级上册道德与法治期末测试卷 (模拟题)word版
部编版三年级上册道德与法治期末测试卷 附答案(预热题)
部编版三年级上册道德与法治期末测试卷 附参考答案(b卷 )
部编版三年级上册道德与法治期末测试卷 答案下载
部编版三年级上册道德与法治期末测试卷 含答案【夺分金卷 】
部编版三年级上册道德与法治期末测试卷 含完整答案【网校专用】
部编版三年级上册道德与法治期末测试卷 及答案(最新)
2024-04-28 6页
2024-04-28 18页
2024-04-28 21页
2024-04-24 8页
2024-04-24 1页
2024-04-24 1页
2024-04-24 1页
2024-04-24 3页
2024-04-24 8页
2024-04-24 5页