《实验二 根据二叉树的抽象数据类型的定义使用二叉链表实现一个二叉树》由会员分享，可在线阅读，更多相关《实验二 根据二叉树的抽象数据类型的定义使用二叉链表实现一个二叉树（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验名称：实验二一一根据二叉树的抽象数据类型的定义，使用二叉链表实现 一个二叉树学生姓名：郭江枫班 级：2017211125班内序号：10学 号：2017210722日 期：2018年5月24日1 .实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树基本要求：根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1
2、存储结构编码表存储结构：二叉树二叉链表示例如图：Ircdata rchlrcdata rchlrclrcdata rchdata rch二叉树结点结构：templatestruct node/定 义结点T data;/ 数据node*lch;/ 左孩子node*rch;/右 孩子;2.2关键算法分析实现该项目需要有如下步骤：步骤一：创建二叉树步骤二：前序遍历步骤三：中序遍历步骤四：后序遍历步骤五：层序遍历步骤六：计算树的深度步骤七：求指定结点到根的路径步骤八：二叉树的销毁步骤一：根据顺序存储结构和性质5,可知如果当前节点的位置为i，则左孩子位置 为2i，右孩子为2i+1.所以，创建二叉树以顺序
3、存储结构为输入，采用先建立根结点，再建 立左右孩子的方法递归建立二叉链表的二叉树。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);/递归，建立右子树else R = NULL;/如果不满足，则为空
4、步骤二：由二叉树的前序遍历定义，结合递归，写出前序遍历的递归算法。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 data;/输出 R 的数据in
5、order(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)
9、/销毁二叉树if (R != NULL)releae(R-lch);/ 递归左子树releae(R-rch);/递归右子树delete R;/delete 掉结点时间复杂度：O(/) 空间复杂度：O (n2)2.3其他此实验主要是递归和队列的应用，在链表的基础上创建一棵二叉树并进行一系列操 作。3. 程序运行结果测试条件：任意输入一个存储好的数据 本次实验树的形状：测试结果:S3 C:VV IN DCLem 32cmd.exeBDEFGC DBFEGAC DFGEBCA ABCDEFG4FFEB”青按任意锤继绞.4.总结1. 二叉树的主体是一个个结点组成的一个特殊的链表，可以用递归和队列的方式来实现 二叉树的一些操作。2. bool函数在需要返回true和false的程序中很有用。3. 可以定义两个参数来通过相互追逐的方法来完成层序遍历。
