实验二-根据二叉树的抽象数据类型的定义-使用二叉链表实现一个二叉树

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

2、1存储结构编码表存储结构：二叉树二叉链表示例如图：lrcdatrcahlrdatrclrdatrccahcahlrdatrclrdatrclrdatrccahcahcahlrdatrccah二叉树结点结构:template<class T>struct node/定义结点T data;/数据node<T>*lch;/node<T>*rch;/左孩子右孩子;2.2关键算法分析实现该项目需要有如下步骤：步骤一：创建二叉树步骤二：前序遍历步骤三：中序遍历步骤四：后序遍历步骤五：层序遍历步骤六：计算树的深度步骤七：求指定结点到根的路径步骤八：二叉树的销毁步骤一：根据

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

4、R 的 datacreat(R->lch, data, 2 * i, n);/递归，建立左子树creat(R->rch, data, 2 * i + 1, n);/递归，建立右子树else R = NULL;/如果不满足，则为空步骤二：由二叉树的前序遍历定义，结合递归，写出前序遍历的递归算法。template<class T>void preorder(node<T>*R)/前序遍历if (R != NULL)/如果 R 不为空，则执行以下操作cout << R->data;/preorder(R->lch);/preorder(R-

5、>rch);/输出 R 的数据遍历左子树遍历右子树步骤三：由二叉树的中序遍历定义，结合递归，写出中序遍历的递归算法。template<class T>void inorder(node<T>*R)/中序遍历if (R != NULL)/如果 R 不为空，则执行以下操作inorder(R->lch);/cout << R->data;/inorder(R->rch);/遍历左子树输出 R 的数据遍历右子树步骤四：由二叉树的后序遍历定义，结合递归，写出后序遍历的递归算法。template<class T>void postor

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

7、r(node<T>*R)/层序遍历node<T>*queue1000;int f = 0, r = 0;/初始化空队列if (R != NULL)queue+r = R;/根结点入队while (f != r)node<T>*p = queue+f;/队头元素出队cout << p->data;/输出队头元素if (p->lch != NULL)queue+r = p->lch;/ 如果左子树不为空，则将左子树元素入队 if (p->rch != NULL)queue+r = p->rch;/如果右子树不为空，则将右

8、子树元素入队步骤六：结合递归函数分别依次遍历左右子树， 并在每次某结点的左右孩子均为空时返回他的深度，然后进行左右子树的比较，选取大的那个数作为树的深度template<class T>int count(node<T>*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 中较大的树步骤七：通过递归判断寻找我们要找的那个数据

9、，找到后返回一个true ，并且输出该数据，由于要判断，所以要使用bool 函数template<class T>bool road(node<T> *R, T a)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 << R->data; /路径上的结点标识打印出来return true;return fa

10、lse;步骤八：二叉链表属于动态的存储分配，需要在析构函数中释放二叉链表的所有结点。为了防止内存泄露， 释放结点应该先释放该结点的左右子树， 左右子树全部释放完毕后再释放结点，采用后序遍历的方法t emplate<class T>void releae(node<T>*R)/销毁二叉树if (R != NULL)releae(R->lch);/递归左子树releae(R->rch);/递归右子树delete R;/delete掉结点时间复杂度：O（ n2 ）空间复杂度：O（ n2）2.3其他此实验主要是递归和队列的应用，在链表的基础上创建一棵二叉树并进行一系列操作。3. 程序运行结果开始创建二叉树计算树的深度前序遍历用户输入要找的数据中序遍历寻找数据并打