北京邮电大学数据结构实验报告与源代码实验三二叉树

北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验三树——题目一学生姓名：徐瑞强班级：2010211119班内序号：04学号：10210559日期：2011年11月25日1．实验要求掌握二叉树基本操作的实现方法根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2.程序分析2.1存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T类型的指针右孩子，示意图如图所示。北京邮电大学信息与通信工程学院第2页在对二叉树的关键算法的实现过程中，采用了队列的存储结构。队列的存储结构示意图如图所示：对于二叉树中每个结点的data域的赋值，我们事先把这些data储存在一个数组中，通过对数组元素的调用事先对二叉树中每个结点的data域的赋值。2.2关键算法分析一：二叉树的建立：A．自然语言描述：1首先判断调用的数组是否为空，如果为空，直接将一个已经初始化好的根节点置为空。2如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data域。3采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。完成对左右子树的赋值。B．代码详细分析：templateclassTvoidBiTreeT::Create(NodeT*&R,T*buf,inti){if(buf[i-1]==0)R=NULL;else{R=newNodeT;R-data=buf[i-1];lchdatarchlchdatarchlchdatarchlchdatarchlchdatarchlchdatarch北京邮电大学信息与通信工程学院第3页Create(R-lch,buf,2*i);Create(R-rch,buf,2*i+1);}}二：前序遍历二叉树：A.自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，则输出它的data域，并且是它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，并且指向根节点的指针指向它的右孩子B.代码详细分析：templateclassTvoidBiTreeT::Preorder(NodeT*R){StackNodeT*S;while(!S.IsEmpty()||(R!=NULL)){if(R!=NULL){Print(R-data);S.Push(R);R=R-lch;}else{R=S.Pop();R=R-rch;}}lchdatarchA[i-1]lchdatarchlchdatarchA[2*i]A[2*i+1]重复上述赋值过程，实现递归调用北京邮电大学信息与通信工程学院第4页}三：中序遍历二叉树：A.自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，将它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，输出该节点的data域，并且指向根节点的指针指向它的右孩子B.代码详细分析：templateclassTvoidBiTreeT::Inorder(NodeT*R){StackNodeT*S;while(!S.IsEmpty()||(R!=NULL)){if(R!=NULL){S.Push(R);R=R-lch;}else{R=S.Pop();Print(R-data);R=R-rch;}}北京邮电大学信息与通信工程学院第5页}四：后序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：递归调用后续遍历函数，函数的参数改为根节点的左孩子4：递归调用后续遍历函数，函数的参数改为根节点的右孩子5：输出根节点的data域B.代码详细分析：templateclassTvoidBiTreeT::Postorder(NodeT*R){if(R!=NULL){Postorder(R-lch);Postorder(R-rch);Print(R-data);}}123北京邮电大学信息与通信工程学院第6页五：层序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：输出根节点的data域4：递归调用层续遍历函数，函数的参数改为根节点的左孩子5：递归调用层序遍历函数，函数的参数改为跟结点的右孩子B.代码详细分析：templateclassTvoidBiTreeT::Levelorder(NodeT*R){QueueNodeT*Q;while(!Q.IsEmpty()||(R!=NULL)){if(R!=NULL){Print(R-data);Q.EnQueue(R-lch);Q.EnQueue(R-rch);}R=Q.DelQueue();}}六：求二叉树的深度：A.自然语言描述：1：判断根节点是否为空，如果根节点为空，返回02：如果根节点不为空但是根节点的左右孩子同时为空，返回13：如果以上两个条件都不成立4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为15：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为06：返回4与5步中得出深度较大的那个数作为二叉树的深度数B.代码详细分析：templateclassTintBiTreeT::GetDepth(NodeT*R,intd){123北京邮电大学信息与通信工程学院第7页if(R==NULL)returnd;if((R-lch==NULL)&&(R-rch==NULL))returnd+1;else{intm=GetDepth(R-lch,d+1);intn=GetDepth(R-rch,d+1);returnnm?n:m;}}七：二叉树的销毁：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：递归调用二叉树的销毁函数，参数改为根节点的左孩子4：递归调用二叉树的销毁函数，参数改为根节点的右孩子5：释放根节点指向的内存B.代码详细分析：templateclassTvoidBiTreeT::Destroy(NodeT*R){if(R!=NULL){Destroy(R-lch);Destroy(R-rch);deleteR;}}123123北京邮电大学信息与通信工程学院第8页八：求二叉树的叶子结点数：A.自然语言描述：1：判断根节点是否为空，如果为空，返回02：如果根节点不为空，切根节点的左右孩子同时为空，返回13：递归调用求二叉树的叶子节点数函数，参数改为根节点的左孩子4：递归调用求二叉树的叶子结点数函数，参数改为根节点的右孩子5：返回根节点的左右子树的叶子结点数之和B.代码详细分析：templateclassTintBiTreeT::LeafNodeCount(NodeT*R){if(R==NULL)return0;if((R-lch==NULL)&&(R-rch==NULL))return1;else{intn=LeafNodeCount(R-lch);intm=LeafNodeCount(R-rch);returnm+n;}}九：求二叉树的结点数：A.自然语言描述：1：判断根节点是否为空，如果为空，返回02：如果根节点不为空3：递归调用求二叉树的结点数的函数，参数改为根节点的左孩子4：递归调用求二叉树的结点数的函数，参数改为根节点的右孩子5：返回根节点的左右字数的结点数之和B.代码详细分析：templateclassTintBiTreeT::NodeCount(NodeT*R){if(R==NULL)return0;else{intm=NodeCount(R-lch);123北京邮电大学信息与通信工程学院第9页intn=NodeCount(R-rch);returnm+n+1;}}2.3其他对二叉树的操作上，前序遍历与中序遍历采用了非递归算法，后续遍历，层序遍历，求二叉树深度，求二叉树叶子结点数，求二叉树结点数等函数采用了递归算法。为了提高运算性能，可以将它们改为非递归算法来实现，例如，后续遍历的非递归算法如下：templateclassTvoidBiTreeeT::Postorder(NodeT*R){StackSNodeT*S;SNodeT*p;do{while(R!=NULL){p-ptr=R;p-tag=1；S.Push(p);R=R-lch;}while(!S.IsEmpty()&&S.GetTop()-tag==2){p=S.Pop();coutp-ptr-data;}if(!S.IsEmpty()){S.GetTop()-tag=2;R=S.GetTop()-ptr-rch;}}while(!S.IsEmpty())3.程序运行结果主函数流程图如下：123北京邮电大学信息与通信工程学院第10页结束开始初始化字符型数组，作为赋值准备初始化一个对象利用creat函数初始化一个二叉树，参数为初始化的字符型数组执行前序，后序，中序，层序遍历，输出遍历结果执行求结点数，叶子节点数，二叉树深度，路径函数执行查找数中结点元素函数北京邮电大学信息与通信工程学院第11页程序运行截图如下：4.总结对二叉树的操作上，前序遍历与中序遍历采用了非递归算法，后续遍历，层序遍历，求二叉树深度，求二叉树叶子结点数，求二叉树结点数等函数采用了递归算法。为了提高运算性能，可以将它们改为非递归算法来实现，对于比较复杂的算法，递归和非递归的运算时间复杂度差别较大，从性能考虑，应当优先采用非递归算法北京邮电大学信息与通信工程学院第12页源代码使用说明：新建头文件“Function.h”和代码文件“main.cpp”，将以下两部分代码复制到相应的头文件和代码文件后ctrl+F5运行即可Function.h:#includeiostreamusingnamespacestd;templateclassTclassNode{public:Tdata;NodeT*lch;NodeT*rch;intltag;intrtag;Node():lch(NULL),rch(NULL),ltag(0),rtag(0){}};templateclassTclassstacknode{public:NodeT*treenode;inttag;};templateclassTclassBiTree{public:NodeT*root;BiTree():root(NULL){}NodeT*&Root();voidCreate(NodeT*&R,T*buf,inti);voidDestroy(NodeT*R);voidPrint(Te);~BiTree();intSearch(NodeT*R,Te,NodeT*&p);北京邮电大学信息与通信工程学院第13页intLeafNodeCount(NodeT*R);intNodeCount(NodeT*R);intGetDepth(NodeT*R,intd);NodeT*GetRoot(){returnRoot;}voidGetPath(Tx,NodeT*R);voidLevelorder(NodeT*R);voidPreorder(NodeT*R);voidInorder(NodeT*R);voidPostorder(NodeT*R);voidCreate(Node