实验二 根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树(6页).doc

《实验二 根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树(6页).doc》由会员分享，可在线阅读，更多相关《实验二 根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树(6页).doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构实验报告实验名称： 实验二根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树学生姓名： 郭江枫班 级： 2017211125班内序号： 10学 号： 2017210722日 期： 2018年5月24日1实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树基本要求：根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析

2、2.1 存储结构 编码表存储结构：二叉树二叉链表示例如图：lrcdatarchlrcdatarchlrcdatarchlrcdatarchlrcdatarchlrcdatarchlrcdatarch二叉树结点结构: templatestruct node/定义结点T data;/数据node*lch;/左孩子node*rch;/右孩子;2.2 关键算法分析实现该项目需要有如下步骤：步骤一：创建二叉树步骤二：前序遍历步骤三：中序遍历步骤四：后序遍历步骤五：层序遍历步骤六：计算树的深度步骤七：求指定结点到根的路径步骤八：二叉树的销毁步骤一：根据顺序存储结构和性质5，可知如果当前节点的位置为i，则左

3、孩子位置为2i，右孩子为2i+1.所以，创建二叉树以顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法递归建立二叉链表的二叉树。templatevoid creat(node*&R, T data, int i, int n)/创建二叉树if (i = n&datai - 1)/如果n个数据没有存储完并且数据不为空R = new node;/定义一个新结点R-data = datai - 1;/将第i个数据赋给R的datacreat(R-lch, data, 2 * i, n);/递归，建立左子树creat(R-rch, data, 2 * i + 1, n);/递归，建立右子树els

4、e R = NULL;/如果不满足，则为空步骤二：由二叉树的前序遍历定义，结合递归，写出前序遍历的递归算法。templatevoid preorder(node*R)/前序遍历if (R != NULL)/如果R不为空，则执行以下操作cout data;/输出R的数据preorder(R-lch);/遍历左子树preorder(R-rch);/遍历右子树 步骤三：由二叉树的中序遍历定义，结合递归，写出中序遍历的递归算法。templatevoid inorder(node*R)/中序遍历if (R != NULL)/如果R不为空，则执行以下操作inorder(R-lch);/遍历左子树cout

5、data;/输出R的数据inorder(R-rch);/遍历右子树步骤四： 由二叉树的后序遍历定义，结合递归，写出后序遍历的递归算法。templatevoid postorder(node*R)/后序遍历if (R != NULL)/如果R不为空，则执行以下操作postorder(R-lch);/遍历左子树postorder(R-rch);/遍历右子树cout data;/输出R的数据步骤五：在进行层序遍历时，对某一层的结点访问完毕后，在按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先访问的结点其左右孩子也要先访问，这与队列的特性比较吻合。因此，我们可以利用队列来实现

6、二叉链表的层序遍历。templatevoid levelorder(node*R)/层序遍历node*queue1000;int f = 0, r = 0;/初始化空队列if (R != NULL)queue+r = R;/根结点入队while (f != r)node*p = queue+f;/队头元素出队cout data;/输出队头元素if (p-lch != NULL)queue+r = p-lch;/如果左子树不为空，则将左子树元素入队if (p-rch != NULL)queue+r = p-rch;/如果右子树不为空，则将右子树元素入队步骤六：结合递归函数分别依次遍历左右子树，并

7、在每次某结点的左右孩子均为空时返回他的深度，然后进行左右子树的比较，选取大的那个数作为树的深度templateint count(node*R)/计算树的深度if (R = NULL)return 0;/如果结点为空，则返回0elseint m = count(R-lch);/遍历左子树int n = count(R-rch);/遍历右子树return m = n ? m + 1 : n + 1;/返回m和n中较大的树步骤七：通过递归判断寻找我们要找的那个数据，找到后返回一个true，并且输出该数据，由于要判断，所以要使用bool函数templatebool road(node *R, T a

8、)if (R = NULL)/如果R为空，则返回falsereturn false;if (R-data = a | road(R-lch, a) | road(R-rch, a)/如果R的数据为a或者R的左子树有a或者R的右子树有a，则执行下一步cout data; /路径上的结点标识打印出来return true;return false;步骤八：二叉链表属于动态的存储分配，需要在析构函数中释放二叉链表的所有结点。为了防止内存泄露，释放结点应该先释放该结点的左右子树，左右子树全部释放完毕后再释放结点，采用后序遍历的方法templatevoid releae(node*R)/销毁二叉树if

9、(R != NULL)releae(R-lch);/递归左子树releae(R-rch);/递归右子树delete R;/delete掉结点时间复杂度：O（n） 空间复杂度：O（n2）2.3 其他此实验主要是递归和队列的应用，在链表的基础上创建一棵二叉树并进行一系列操作。开始3. 程序运行结果 创建二叉树计算树的深度用户输入要找的数据前序遍历中序遍历寻找数据并打印路径层序遍历销毁二叉树结束测试条件：任意输入一个存储好的数据本次实验树的形状：测试结果：4. 总结1.二叉树的主体是一个个结点组成的一个特殊的链表，可以用递归和队列的方式来实现二叉树的一些操作。2.bool函数在需要返回true和false的程序中很有用。3.可以定义两个参数来通过相互追逐的方法来完成层序遍历。-第 6 页-