北邮数据结构第三次实验-二叉树(修改)

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验三题目1二叉树姓名： 班级： 班内序号：学号： 2013210465 1实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1 存储结构lch data rch使用二叉链表实现二叉树的存储，其示意图如下图所示： data rchlch data data data 2.2

2、关键算法分析前序遍历：访问根节点遍历左子树遍历右子树具体算法：templatevoid BiTree:PreOrder(BiNode* R)/前序遍历if(R!=NULL)coutdata; /访问结点PreOrder(R-lch); /遍历左子树PreOrder(R-rch); /遍历右子树中序遍历：templatevoid BiTree:Inorder(BiNode*R) if(R!=NULL) Inorder(R-lchild); /遍历左子树 coutdata; /访问结点 Inorder(R-rchild); /遍历右子树 后序遍历templatevoid BiTree:Postor

3、der(BiNode*R) if(R!=NULL) Postorder(R-lchild); /遍历左子树 Postorder(R-rchild); /遍历右子树 coutdata; /访问结点 层序遍历： templatevoid BiTree:LevelOrder(BiNode* R)/层序遍历BiNode* queue100; /创建队int f=0,r=0; /r为队尾指针，f为对头指针if(R!=NULL)queue+r=R; /头结点入队while(f!=r) /如果队不为空，做此循环BiNode* p=queue+f; /出队coutdata;if(p-lch!=NULL) /出

4、队结点若有左右孩子，则左右孩子依次入队queue+r=p-lch;if(p-rch!=NULL)queue+r=p-rch;求深度:template int BiTree:Depth(BiNode* R,int d) /求二叉树的深度 if (R=NULL) /如果二叉树为空，返回0return d; if (R-lch=NULL)&(R-rch=NULL) /如果二叉树没有孩子，返回二叉树深度return d+1; else /如果二叉树有孩子，做递归循环，并返回二叉树的最长路径，即二叉树深度 int m=GetDepth(R-lch,d+1); int n=GetDepth(R-rch,d

5、+1); return nm?n:m; 求路径：templatebool BiTree:Getpath(BiNode*R,int d) if(R=NULL)return false; if(R-data=d|Getpath(R-lchild,d)|Getpath(R-rchild,d) coutdata ; return true; 时间复杂度: 前序遍历：O（n） 层序遍历：O（n） 求二叉树深度：O（n)3. 程序运行结果3.1 测试主函数流程 开始创建字符数组创建二叉树前序遍历中序遍历后序遍历层序遍历求二叉树深度求指定结点到二叉树根节点路径结束 4. 总结该次试验中，二叉树的建立，前序遍

6、历，中序遍历，后序遍历，求二叉树的深度以及二叉树的销毁都涉及到递归函数的巧妙应用。二叉树的层序遍历则利用“队”的概念来实现根节点入队，出队，并让其孩子按顺序入队。个人觉得最难的部分莫过于求指定结点到根节点的路径。对于寻找指定结点到根节点的路径，首先觉得应该是一个一个节点地寻找，直到找到要求的结点，寻找过程即用到二叉树的遍历，比如该实验中用到的前序遍历；再者，关于路径，想到“迷宫问题”，即使用“栈”存储寻找到指定结点的正确路径，并一一出栈，就可得到指定结点到根节点的路径。对于编程，有些巧妙而经典的方法需要记忆，独自想出每种问题的算法比较困难，也浪费时间，而借鉴一些经典算法，有利于加快工作，也启迪

7、我们一些算法的创新。所以，我们需要记忆一些经典算法。源程序：#includeusing namespace std;templatestruct BiNodeT data;BiNode*lchild;BiNode*rchild;templateclass BiTreeprivate:void Create(BiNode*&R,T data,int i,int n);/创建二叉树void Release(BiNode*R);/释放二叉树public:BiNode*root; /根节点BiTree(T data,int n); /构造函数void Preorder(BiNode*R); /前序遍历

8、void Inorder(BiNode*R); /中序遍历void Postorder(BiNode*R); /后序遍历void Leveorder(BiNode*R); /层序遍历BiTree(); /析构函数 int Count(BiNode*R); /结点数bool Getpath(BiNode*R,int d); /路径int GetDepth(BiNode*R,int d); /深度;templatevoid BiTree:Create(BiNode*&R,T data,int i,int n) /表示位置，从开始，表示数组的长度if(i=n)R=new BiNode; /创建根节点

9、R-data=datai-1;Create(R-lchild,data,2*i,n); /创建左子树Create(R-rchild,data,2*i+1,n); /创建右子树else R=NULL;templateBiTree:BiTree(T data,int n)Create(root,data,1,n);/前序遍历templatevoid BiTree:Preorder(BiNode*R)if(R!=NULL)coutdata; /访问节点Preorder(R-lchild); /遍历左子树Preorder(R-rchild); /遍历右子树/中序遍历templatevoid BiTre

10、e:Inorder(BiNode*R)if(R!=NULL)Inorder(R-lchild); /遍历左子树coutdata; /访问结点Inorder(R-rchild); /遍历右子树/后序遍历templatevoid BiTree:Postorder(BiNode*R)if(R!=NULL)Postorder(R-lchild); /遍历左子树Postorder(R-rchild); /遍历右子树coutdata; /访问结点/层序遍历templatevoid BiTree:Leveorder(BiNode*R)BiNode*queue100;int f=0;int r=0; /初始化

11、空队列if(R!=NULL) queue+r=R; /根节点入队while(f!=r)BiNode*p=queue+f; /对头元素出队coutdata; /出队打印if(p-lchild!=NULL) queue+r=p-lchild; /左孩子入队if(p-rchild!=NULL) queue+r=p-rchild; /右孩子入队/析1函数templatevoid BiTree:Release(BiNode*R)if(R!=NULL)Release(R-lchild); 释放左子树Release(R-rchild); /释放右子树delete R; /释放根节点/释放二叉树templat

12、eBiTree:BiTree()Release(root);/求结点总数templateint BiTree:Count(BiNode *R)if(R=NULL)return 0;elseint m=Count(R-lchild);int n=Count(R-rchild);return m+n+1;/求深度templateint BiTree:GetDepth(BiNode *R,int d)if(R=NULL)return d;if(R-lchild=NULL)&(R-rchild=NULL)return d+1;elseint m=GetDepth(R-lchild,d+1);int n

13、=GetDepth(R-rchild,d+1);return nm?n:m; /查询结点路径? templatebool BiTree:Getpath(BiNode*R,int d) if(R=NULL)return false;if(R-data=d|Getpath(R-lchild,d)|Getpath(R-rchild,d)coutdata ;return true;void main() char data50=abcdefgh;BiTreetree(data,8);cout前序遍历为：;tree.Preorder(tree.root);coutendl;cout中序遍历为：;tree.Inorder(tree.root);coutendl;cout后序遍历为：;tree.Postorder(tree.root);coute