二叉树操作报告解读.doc

上机实验报告 课程名称：数据结构A 实验题目：二叉树操作 专业班级： 学号： 姓名： 完成日期： 成绩： 实验题目：二叉树操作 实验内容 二叉树的建立和遍历。 实验目的 进一步掌握指针变量的使用。 掌握二叉树的结构特征以及各种存储结构的特点及使用范围。 掌握用指针类型描述、访问和处理二叉树的运算。 掌握栈或队列的使用。 实验题目 本实验要求实现以下功能： 按前序次序建立一棵二叉树，以‘＃’表示空。 中序、后序遍历该二叉树，输出遍历序列。 求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。 4. 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队辅助助存储结构实现二叉树的层次遍历算法 2. 程序中使用的数据结构及符号说明 本实验使用c++语言，运用节点类模板，队列以及二叉树类模板来实现实验要求。二叉树类函数中大多数用递归的运算 3.程序的主要功能函数及相关算法 在二叉链表类bintreelink中设计了create（）函数，采用递归的算法，即先建立根节点，然后建立左子树，最后建立右子树，如果输入的是#，就表示空。preorder（）函数与inorder（）函数、postorder（）函数也是采用递归的算法。以preorder（）为例，先访问根节点，然后访问左子树，最后访问右子树。对于层序遍历函数levelorder（）用到了之前的队列的知识，具体算法是：1、先创建一个队列queue，根节点入队；2、当队列非空时，取出队头节点r，转步骤三；如果队列为空，则结束遍历。3、访问节点r，如果该节点有左孩子，则将其左孩子入队列；如果该节点有右孩?子， 则将其右孩子入队列； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4、重复步骤二和三，直到队列为空。getdepth（）用来求得二叉树的深度，也是用来递归的思想，具体算法是：如果根节点不为空，先求它的左子树的深度，再求右子树的深度，比较一下大小，最后返回较大的那个+1；还有getleaf（）函数是用来求得叶子数的，具体算法是：定义了两个变量leftleaf和rightleaf，分别表示左子树的叶子数，右子树的叶子数，如果根节点为空，则返回0，如果左孩子指针与右孩子指针均为空，则返回1，否则求得它的左子树的叶子数，右子树的叶子数，最后返回leftleaf+rightleaf。 4.程序运行时的初值和运行结果 输入以下字符串，建立二叉树：ABC##DE#G##F### 输出中序遍历序列应为：CBEGDFA 输出后序遍历序列应为：CGEFDBA 输出二叉树的深度应为：5 输出二叉树的叶子数目应为：3 5.二叉树的形态： 6.程序的主要流程图 7收获及体会 二叉树类中的各个函数体中基本上都要用到递归的思想。所以本次实验可以让我更好地掌握递归的思想。此外更好地运用了节点类和队列类的使用。实践与所学知识需要更好地结合。8.源代码 #includeiostream using namespace std; class bintreenode //定义二叉树节点类 { public: char data; //定义数据域 bintreenode *leftchild; //定义左孩子指针 bintreenode *rightchild; //定义右孩子指针 bintreenode() //无参构造函数 { leftchild=rightchild=NULL; } bintreenode(char d,bintreenode *left,bintreenode *right) //有参构造函数 { data=d; leftchild=left; rightchild=right; } }; class bintreelink //定义二叉树链表 { public: bintreenode *root; //定义根指针 bintreelink() //构造空二叉树 { root=NULL; } void creat(bintreenode