实验四 树和二叉树及其应用(I).pdf
版权申诉
187 浏览量
2022-11-12
11:45:19
上传
评论
收藏 594KB PDF 举报
姓名 学号
实
验
树和二叉树及其应用（I）
项
目
实
验
内
容
算法设计与程序实现：
算
法
分
析
本 次 实 验 主 函 数 采 用 顺 序 结 构 ， 主 函 数 调 用 自 己 编 写 的 头 文 件
DataStructure_BinaryTree.h
中的相关功能函数，完成实验要求。
程序实现：
1、二叉树的遍历：实验分别递归与非递归的方法分别进行了先序、中序、后
序和层序遍历。由于先序、中序、后序的递归遍历实现算法非常类似，所以以下的算
法具体实现只对递归的先序遍历和层序遍历以及非递归的先序遍历、后序遍历和层序
遍历作详细的分析说明。
2、二叉树的基本操作：
(1) 求二叉树的深度；
(2) 求二叉树中叶子结点的个数；
(3) 先序交换二叉树；
(4) 查找以指定元素值为的根节点的根子树；
(5) 删除以指定元素值为的根节点的根子树；
(6) 判断二叉树是否为完全二叉树。
以下分别以上的基本操作算法的具体实现作了详细的分析说明。
1、二叉树的遍历
递归先序遍历：先序遍历二叉树的原则是当二叉树不为空时，先访问根结点，再
次先序遍历左子树，最后先序遍历右子树，否则进行空操作(递归结束的条件)。
按照以上先序遍历的原则，采取递归的方法很容易完成程序的具体实现。
递归层序遍历：层序遍历顾名思义从根结点出发从左到右逐层进行访问，由此可
以通过控制层次数进而进行逐层遍历，当层次数不为零时，层次数递减递归遍历
左、右子树，当层次数为零时(递归结束条件)，访问该节点。遍历时可不比事先
知道二叉树的深度 (用于层次数递增边界控制 )，当当前层次数下访问失败并返
回，则当前层次数即为二叉树的深度。以上遍历中对每一层遍历都需从根结点出
1
1．建立二叉树的二叉链表存储结构，实现二叉树的前序、中序、后序递归遍历。
二叉链表存储结构定义参见教材第 127 页。
遍历算法参见教材第 128-129 页。
2．编写递归算法,计算二叉树中叶子结点的数目。（题集第 42 页 6.42）
3．编写递归算法，计算二叉树的深度。（题集第 43 页 6.44）
剩余12页未读，继续阅读
资源评论
