《二叉树操作报告》由会员分享，可在线阅读，更多相关《二叉树操作报告（10页珍藏版）》请在金锄头文库上搜索。
1、上机实验报告课程名称：数据结构A 实验题目：二叉树操作 专业班级： 学号： 姓名： 完成日期： 成绩： 1. 实验题目：二叉树操作（一） 实验内容二叉树的建立和遍历。（二） 实验目的1. 进一步掌握指针变量的使用。2. 掌握二叉树的结构特征以及各种存储结构的特点及使用范围。3. 掌握用指针类型描述、访问和处理二叉树的运算。4. 掌握栈或队列的使用。（三） 实验题目本实验要求实现以下功能：1. 按前序次序建立一棵二叉树，以表示空。2. 中序、后序遍历该二叉树，输出遍历序列。3. 求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。 4. 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队
2、辅助助存储结构实现二叉树的层次遍历算法2. 程序中使用的数据结构及符号说明 本实验使用c+语言，运用节点类模板，队列以及二叉树类模板来实现实验要求。二叉树类函数中大多数用递归的运算3.程序的主要功能函数及相关算法在二叉链表类bintreelink中设计了create（）函数，采用递归的算法，即先建立根节点，然后建立左子树，最后建立右子树，如果输入的是#，就表示空。preorder（）函数与inorder（）函数、postorder（）函数也是采用递归的算法。以preorder（）为例，先访问根节点，然后访问左子树，最后访问右子树。对于层序遍历函数levelorder（）用到了之前的队列的知识，
3、具体算法是：1、先创建一个队列queue，根节点入队；2、当队列非空时，取出队头节点r，转步骤三；如果队列为空，则结束遍历。3、访问节点r，如果该节点有左孩子，则将其左孩子入队列；如果该节点有右孩子， 则将其右孩子入队列； 4、重复步骤二和三，直到队列为空。getdepth（）用来求得二叉树的深度，也是用来递归的思想，具体算法是：如果根节点不为空，先求它的左子树的深度，再求右子树的深度，比较一下大小，最后返回较大的那个+1；还有getleaf（）函数是用来求得叶子数的，具体算法是：定义了两个变量leftleaf和rightleaf，分别表示左子树的叶子数，右子树的叶子数，如果根节点为空，则返回
4、0，如果左孩子指针与右孩子指针均为空，则返回1，否则求得它的左子树的叶子数，右子树的叶子数，最后返回leftleaf+rightleaf。4.程序运行时的初值和运行结果输入以下字符串，建立二叉树：ABC#DE#G#F#输出中序遍历序列应为：CBEGDFA输出后序遍历序列应为：CGEFDBA输出二叉树的深度应为：5输出二叉树的叶子数目应为：35.二叉树的形态： A B C D E FG 6.程序的主要流程图队列层序遍历树的叶子树的深度构造函数中序遍历、前序遍历前序创建二叉树析构函数析构函数构造函数入队、出队判断队空析构函数构造函数循环队列类二叉树队列类树节点类获取树根结点7收获及体会 二叉树类中
5、的各个函数体中基本上都要用到递归的思想。所以本次实验可以让我更好地掌握递归的思想。此外更好地运用了节点类和队列类的使用。实践与所学知识需要更好地结合。8.源代码#includeusing namespace std;class bintreenode /定义二叉树节点类public:char data; /定义数据域bintreenode *leftchild; /定义左孩子指针bintreenode *rightchild; /定义右孩子指针bintreenode() /无参构造函数leftchild=rightchild=NULL;bintreenode(char d,bintreenod
6、e *left,bintreenode *right) /有参构造函数data=d;leftchild=left;rightchild=right;class bintreelink /定义二叉树链表 public:bintreenode *root; /定义根指针bintreelink() /构造空二叉树root=NULL;void creat(bintreenode *&r) /创建二叉树char ch;cout请输入数据ch;if(ch=#)r=NULL;elser=new bintreenode;r-data=ch;creat(r-leftchild);creat(r-rightchi
7、ld);void preorder(bintreenode *r) /先序遍历if(r!=NULL)coutdataleftchild);preorder(r-rightchild);void inorder(bintreenode *r) /中序遍历if(r!=NULL)inorder(r-leftchild);coutdatarightchild);void postorder(bintreenode *r) /后序遍历if(r!=NULL)postorder(r-leftchild);postorder(r-rightchild);coutdata ;void levelorder(bi
8、ntreenode *r) /层次遍历bintreenode *queue100; /定义队列queuebintreenode *p;int front,rear;queue0=root;front=rear=0;while(front=rear)p=queuefront;front+; /出队coutdataleftchild!=NULL)queue+rear=p-leftchild; /入队if(p-rightchild!=NULL)queue+rear=p-rightchild;coutleftchild);rightdepth=getdepth(r-rightchild);return
9、 leftdepthrightdepth?leftdepth+1:rightdepth+1;int getleaf(bintreenode *r) /求叶子函数int leftleaf,rightleaf;if(r=NULL)return 0;else if(r-leftchild=NULL)&(r-rightchild=NULL)return 1;elseleftleaf=getleaf(r-leftchild);rightleaf=getleaf(r-rightchild);return leftleaf+rightleaf;int main() /主函数部分bintreelink lin
10、k; /定义二叉链表类的对象linklink.creat(link.root); /创建二叉树（即输入数据）cout先序遍历显示为： ;link.preorder(link.root); / 对二叉树实现先序遍历coutendlendlendl;cout中序遍历显示为： ;link.inorder(link.root); / 对二叉树实现中序遍历coutendlendlendl;cout后序遍历显示为： ;link.postorder(link.root); / 对二叉树实现后序遍历coutendlendlendl;cout层序遍历显示为： ;link.levelorder(link.root); / 对二叉树实现层次遍历coutendlendlendl;cout深度: link.getdepth(link.root)endlendlendl; /求出二叉树的深度cout叶子数 link.getleaf(link.root)endlendlendl; /求出二叉树的叶子数system(pause);return 0;
