中南大学数据结构课程实验实验报告题 目 实验三 二叉树的基本操作 学生姓名 谭淇蔚 学生学号 3901130721 专业班级 1307 班 1 需求分析二叉树是一种重要的非线性结构。之所以做此实验，目的是：让我们掌握用指针类型描述、访问和处理二叉树的运算，并掌握二叉树的结构特征，以及各种存储结构的特点及适用范围，以及熟练掌握递归程序设计方法、以及栈的应用。输入形式：ABD#E#C#（没有提示，#表示表示前面的结点没有孩子，#表示空）输入值的范围：具体范围还没有测试输出的形式：“先序为：”“中序为：”“后序为：”“结点数为：.”“度为 1 的数有：”“度为 2 的数有：”“终端结点的个数为：”“此二叉树的数值最大是：.”“此二叉树的数值最小是：.”测试数据：输入：ABD#E#C#输出：先序为:ABDEC中序为：DBEAC后序为：DEBCA结点数为：5度为 1 的数有:0度为 2 的数有:2终端结点的个数为：3此二叉树的数值最大是：E.此二叉树的数值最小是：A2概要设计首先定义二叉树的结点结构体：struct BTNodechar data;struct BTNode *lchild, *rchild;/左、右孩子;创造树的函数：BTNode *CreateTree(BTNode *r)char ch;/字符输入cin ch;if (ch = #) return NULL;elser = new BTNode;/开创一个新结点r-data = ch;CountNum+;/计算结点数r-lchild = CreateTree(r-lchild);/创建左子树r-rchild = CreateTree(r-rchild);/创建右子树return r;/递归创造树利用递归创建树，效率不高，但是想法简单容易实现。先序递归算法函数：void PreOrder(BTNode *root)if (root != NULL)cout data lchild);/先序遍历 root 的左子树PreOrder(root-rchild); /先序遍历 root 的右子树/先序中序递归算法函数：void InOrder(BTNode *root)if (root != NULL)InOrder(root-lchild);/中序遍历 root 的左子树cout data rchild);/中序遍历 root 的右子树/中序后序递归算法函数：void PostOrder(BTNode *root)if (root != NULL)PostOrder(root-lchild);/后序遍历 root 的左子树PostOrder(root-rchild);/后序遍历 root 的右子树cout data lchild != NULL&r-rchild != NULL) & !(r-lchild = NULL&r-rchild = NULL)DuOne+;DuOneNumber(r-lchild, DuOne);DuOneNumber(r-rchild, DuOne);DuOneNumber(r-lchild, DuOne);DuOneNumber(r-rchild, DuOne);/计算度为 1 的结点数计算二叉树中最大最小值的递归函数：void Max(BTNode *T,char &ch)/求最大(递归算法）if (T != NULL)if (T-datach)ch = T-data;Max(T-lchild,ch);Max(T-rchild,ch);void Main(BTNode *T, char &ch)/求最小 (递归算法）if (T != NULL)if (T-data data;Main(T-lchild, ch);Main(T-rchild, ch);3.详细设计具体代码在第二部分以及第七部分，说思路即可。思路：首先先创造一个结点结构体。在创造树的过程中利用递归，一步步把树完整化。接着在主函数中创建一个 root 根指针结点，目的是利用这个 root 指针代表一棵树，root 被用来指针传递，目的是为了后面的函数的调用。在计算结点的部分，我利用全局变量 CountNum 来度量，因为在创造树的过程中，我们已经判定它是不是结点，所以没必要写一个函数，把所有的树的结点全部再次遍历一遍，这样做，节省了时间效率。其次在计算度为 1 的点的个数的时候，我们要知道，所谓的度为1，说明其只有一个孩子，所以在 if 条件句中说明了，其结点左右孩子即不全为空，也不全为满。计算度数为二的中，我们利用一个结点关系：N0 =N2 +1 以及 N=N1 +2 N2 +1 以及 N=N1 +N2 + N0所以很容易得到度数为二与总结点数和度为一的结点的个数的关系式，这样避免了一个个查证遍历，利用函数来计算的麻烦，时间复杂度上得以降低。同理也可以求出度为零的点（利用结点关系） 。4调试分析调试中，没发现什么问题，编译一次便过了，具体的先序和后序已经中序的代码也是参考了老师上课 PPT 讲的部分。5用户使用说明用户使用的过程中，注意输入格式需要规范即可。意思是，输入的每一个结点都要有说明结点是否还有左右孩子。6测试结果7.附录#include using namespace std;int CountNum = 0;/计算结点总数struct BTNodechar data;struct BTNode *lchild, *rchild;/左、右孩子;BTNode *CreateTree(BTNode *r)char ch;/字符输入cin ch;if (ch = #) return NULL;elser = new BTNode;r-data = ch;CountNum+;/计算结点数r-lchild = CreateTree(r-lchild);r-rchild = CreateTree(r-rchild);return r;/递归创造树void PostOrder(BTNode *root)if (root != NULL)PostOrder(root-lchild);/后序遍历 root 的左子树PostOrder(root-rchild);/后序遍历 root 的右子树cout data lchild);/中序遍历root 的左子树cout data rchild);/中序遍历root 的右子树/中序void PreOrder(BTNode *root)if (root != NULL)cout data lchild);/先序遍历root 的左子树PreOrder(root-rchild); /先序遍历 root 的右子树/先序void DuOneNumber(BTNode *r,int &DuOne)if (r != NULL)if (!(r-lchild != NULL&r-rchild != NULL) & !(r-lchild = NULL&r-rchild = NULL)DuOne+;DuOneNumber(r-lchild, DuOne);DuOneNumber(r-rchild, DuOne);DuOneNumber(r-lchild, DuOne);DuOneNumber(r-rchild, DuOne);/计算度为 1 的结点数void Max(BTNode *T,char &ch)/求最大(递归算法）if (T != NULL)if (T-datach)ch = T-data;Max(T-lchild,ch);Max(T-rchild,ch);void Main(BTNode *T, char &ch)/求最小(递归算法）if (T != NULL)if (T-data data;Main(T-lchild, ch);Main(T-rchild, ch);int main()BTNode *root = NULL;/创建头指针int Du1Num = 0;/计算度为 1 的点int DuTwoNum = 0;/计算度为 2的点char ch;root = CreateTree(root);ch = root-data;/初始化比较大小的 ch 值cout data;Main(root, ch);cout 此二叉树的数值最小是：n ch;system(pause);return 0;