实验四 树和二叉树及其应用(I)

《实验四 树和二叉树及其应用(I)》由会员分享，可在线阅读，更多相关《实验四 树和二叉树及其应用(I)（13页珍藏版）》请在金锄头文库上搜索。

1、1姓名姓名学号学号实实验验项项目目树和二叉树及其应用（I）实实验验内内容容1建立二叉树的二叉链表存储结构，实现二叉树的前序、中序、后序递归遍历。 二叉链表存储结构定义参见教材第 127 页。 遍历算法参见教材第 128-129 页。 2编写递归算法,计算二叉树中叶子结点的数目。 （题集第 42 页 6.42） 3编写递归算法，计算二叉树的深度。 （题集第 43 页 6.44）算法设计与程序实现：算法设计与程序实现：算算法法分分析析本次实验主函数采用顺序结构，主函数调用自己编写的头文件DataStructure_BinaryTree.h中的相关功能函数，完成实验要求。程序实现： 1、二叉树的遍历

2、：实验分别递归与非递归的方法分别进行了先序、中序、后 序和层序遍历。由于先序、中序、后序的递归遍历实现算法非常类似，所以以下的 算法具体实现只对递归的先序遍历和层序遍历以及非递归的先序遍历、后序遍历和 层序遍历作详细的分析说明。 2、二叉树的基本操作： (1) 求二叉树的深度； (2) 求二叉树中叶子结点的个数； (3) 先序交换二叉树； (4) 查找以指定元素值为的根节点的根子树； (5) 删除以指定元素值为的根节点的根子树； (6) 判断二叉树是否为完全二叉树。以下分别以上的基本操作算法的具体实现作了详细的分析说明。1 1、二叉树的遍历、二叉树的遍历 递归先序遍历：先序遍历二叉树的原则是当

3、二叉树不为空时，先访问根结点， 再次先序遍历左子树，最后先序遍历右子树，否则进行空操作(递归结束的条件) 。按照以上先序遍历的原则，采取递归的方法很容易完成程序的具体实现。 递归层序遍历：层序遍历顾名思义从根结点出发从左到右逐层进行访问，由此 可以通过控制层次数进而进行逐层遍历，当层次数不为零时，层次数递减递归 遍历左、右子树，当层次数为零时(递归结束条件)，访问该节点。遍历时可不 比事先知道二叉树的深度(用于层次数递增边界控制)，当当前层次数下访问失 败并返回，则当前层次数即为二叉树的深度。以上遍历中对每一层遍历都需从2根结点出发。 非递归先序遍历：在根指针不空的情况下，访问根结点，根指针域

4、压栈，继续 遍历左子树，循环上诉操作，当左子树指针为空(循环结束条件，同时也是遍历 右子树的条件)，此时表明根指针已空， 本左子树遍历完毕，然后退栈返回上 一层，弹出的指针即此时根结点指针，继续遍历右子树未曾访问的结点。 非递归中序遍历：如同此法，中序与先序的不同是不能首先访问根结点，而是 要先访问作孩子节点，要使根结点能够被访问，就要求此时根结点的左孩子为 空，这样根结点就能访问了，故访问操作是在根指针退栈后进行访问的。 非递归后序遍历：后序遍历与上面的先序、中序遍历的不同是也访问根结点的 条件，即当根结点的右指针域为空或右孩子指针指向的节点已被访问过。由此 算法是只要根指针不空时，将根指针

5、进栈，遍历左子树，当根指针为空(根节点 的左孩子指针为空，该指针并没有进栈)，取出栈顶指针，判断右孩子指针是否 为空或已被访问过，如果上述条件成立则访问根结点，退栈并更新用于记录被 访问的指针。 非递归层序遍历：根据二叉树的特性，使用队列这种数据结构，出队列一个节 点指针，入队列两个节点指针，出队列指针结点的左右孩子指针即为入队列的 指针(当访问成功才入队列)，通过上述操作即可实现层序遍历。 2 2、二叉树的基本操作、二叉树的基本操作 求二叉树的深度：求二叉树的深度即求得左右子树的深度(左右子树深度最大值) 加 1，当然求左右子树的深度即求左右子树的左右子树的深度加 1，由此递归下 去，当子树

6、为空时(递归结束条件)，返回 0，然后逐层向上其的二叉树深度。 求二叉树中叶子结点的个数：叶子结点即左右子树皆为空的节点。由此选择递 归就很容易实现，从根结点开始进行遍历，判断当前结点的左右子树是否为空， 不为空则继续访问下一个节点，为空则使叶子结点数加 1，继续查找其他的节点。先序交换二叉树：当根指针不空时，交换左右子树指针，然后交换左子树的左 右孩子指针，如此递归操作，当当前的根指针为空时，返回，交换右子树，如 此就完成了二叉树的交换。 查找以指定元素值为的根节点的根子树：查找根遍历是相同的，只是把遍历的 具体应用函数改为判断访问的节点的数据是否等于指定的数据，当找到则返回 当前节点的根指

7、针，若全部访问结束都还没栈顶则返回失败。 删除以指定元素值为的根节点的根子树：查找指定元素的操作可通过上诉函数 完成，至此只需要调用删除二叉树函数，至于删除二叉树的算法是当根指针不 空时，依次释放左右子树的内存，然后释放根结点，当然释放左右子树时又是 先释放左右子树的左右子树的内存，如此进行递归操作，当根指针为空时，返 回。 判断二叉树是否为完全二叉树：判断二叉树是否为完全二叉树可以转化为判断 二叉树的左右子树的深度是否相等，当相等时，二叉树即为完全二叉树，不等 则不是完全二叉树。当然判断二叉树的深度是递归进行的，最终是判断二叉树 的最底层的左右子树深度是否为零。核核心心此程序中用到的自己编写

8、的头文件以在下面给出，而头文件的说明则在主函数 中文件包含部分的注释处，核心程序如下： 1.主函数如下：#include “iostream“ /标准输入输出流库文件3程程序序#include “windows.h“ /cmd窗口设置函数头文件#include “ADT.h“ /数据结构中相关结构体类型定义及相关数据类型定义#include “DataStructure_BinaryTree.h“ /数据结构第六章树与二叉树函数的定义及声明using namespace std;int main(void)system(“title 数据结构实验 实验四：树和二叉树及其应用（I） “); /设

9、置cmd窗口标题system(“color F1“); /设置控制台窗口的背景色和前景色system(“date /T“); /输出当前的日期print();cout 先序遍历：“;PreOrderTraverse(T, PrintElement); /先序遍历二叉树cout 中序遍历：“;InOrderTraverse(T, PrintElement); /中序遍历二叉树cout 后序遍历：“;PostOrderTraverse(T, PrintElement); /后序遍历二叉树cout 层序遍历：“ 先序遍历：“;PreOrderTraverseNonRec(T, PrintElemen

10、t); /先序遍历二叉树cout 中序遍历：“;InOrderTraverseNonRec(T, PrintElement); /中序遍历二叉树cout 后序遍历：“;PostOrderTraverseNonRec(T, PrintElement); /后序遍历二叉树cout 层序遍历：“;LevelOrderTraverseNonRec(T, PrintElement);/层序遍历二叉树print();cout 二叉树的深度：“ 二叉树中叶子结点的数目：“ 交换左右子树：“ 查找指定节点的根子树：“ x;PreOrderLocate(T, x, root); /先序查找以元素值为x的结点为子

11、树，并以root指向其根子树cout 查找指定节点的根子树的深度：“ 判断根子树是否为完全二叉树：“ 删除二叉树：“ #include #include “ADT.h“#include “DataStructure_StackQueue.h“ /数据结构第三章栈和队列相关函数的定义及声明/* 功 能 函 数 声 明 区*/Status GreateBiTree(BiTree /按先序输入二叉树中节点的值,#字符表示空树,构造二叉链表树TStatus PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /先序递归遍历二叉树TStatus

12、 InOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /中序递归遍历二叉树TStatus PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /递归后序遍历二叉树TStatus LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /递归层序遍历二叉树TStatus PreOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e); /先序非递归遍历二叉树TS

13、tatus InOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e); /中序非递归遍历二叉树TStatus PostOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e); /后序非递归遍历二叉树TStatus LevelOrderTraverseNonRec(BiTree T, Status(*Visit)(TElemType e);/层序非递归遍历二叉树Tint BiTDepth(BiTree /求二叉树的深度Status TraverseLevel(BiTree r

14、oot, int level,Status(*Visit)(TElemType e);/遍历以roo为根节点中的level层的所以节点（从左到右），成功返回1，失败返回0Status PreOrderLocate(BiTree /先序查找以元素值为e的结点为子树，并以T1指向其根子树Status ChildBiTreeDepth(BiTree /求以元素值x的节点的根子树的深度Status InitBiTree(BiTree /初始化二叉链表TStatus BiTreeEmpty(BiTree T); /判断二叉树是否为空，若为空则返回TRUE, 否则返回FALSEStatus DestoryBiTree(BiTree /销毁二叉树T Status DelBiTree(BiTree /删除二叉链表TStatus DelChildBiTree(BiTree /删除以元素值为e的结点为根子树Status CompleteBiTree(BiTree T); /判断二叉树是否为完全二叉树Status ExchangeBiTree(BiTree /先序交换二叉树的左右子树Status LeafTNodeNum(BiTree T, int /求二叉树的叶