《北邮数据结构第三次实验-二叉树(修改)》由会员分享，可在线阅读，更多相关《北邮数据结构第三次实验-二叉树(修改)（10页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学信息与通信工程学院第 1 页数据结构实验报告实验名称：实验三题目1 二叉树姓名：班级：班内序号：学号：2013210465 北京邮电大学信息与通信工程学院第 2 页1实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试 main() 函数测试线性表的正确性2. 程序分析2.1 存储结构 使用二叉链表实现二叉树的存储，其示意图如下图所示：2.2 关键算法分析前序遍历：访问根节点
2、遍历左子树遍历右子树具体算法：template void BiTree:PreOrder(BiNode* R)/前序遍历 if(R!=NULL) coutdata; /访问结点PreOrder(R-lch); /遍历左子树PreOrder(R-rch); /遍历右子树 中序遍历：template void BiTree:Inorder(BiNode*R) lch data rch datarch lch data data data 北京邮电大学信息与通信工程学院第 3 页if(R!=NULL) Inorder(R-lchild); /遍历左子树coutdata; /访问结点Inorder(R
3、-rchild); /遍历右子树 后序遍历template void BiTree:Postorder(BiNode*R) if(R!=NULL) Postorder(R-lchild); /遍历左子树Postorder(R-rchild); /遍历右子树coutdata; /访问结点 层序遍历：template void BiTree:LevelOrder(BiNode* R)/层序遍历 BiNode* queue100; /创建队int f=0,r=0; /r 为队尾指针， f 为对头指针if(R!=NULL) queue+r=R; /头结点入队while(f!=r) /如果队不为空，做此
4、循环 BiNode* p=queue+f; /出队coutdata; if(p-lch!=NULL) /出队结点若有左右孩子，则左右孩子依次入队queue+r=p-lch; if(p-rch!=NULL) queue+r=p-rch; 求深度 : template int BiTree:Depth(BiNode* R,int d)/求二叉树的深度 if (R=NULL) /如果二叉树为空，返回0 return d; if (R-lch=NULL) 北京邮电大学信息与通信工程学院第 4 页else /如果二叉树有孩子，做递归循环，并返回二叉树的最长路径，即二叉树深度 int m=GetDepth
5、(R-lch,d+1); int n=GetDepth(R-rch,d+1); return nm?n:m; 求路径：template bool BiTree:Getpath(BiNode*R,int d) if(R=NULL)return false; if(R-data=d|Getpath(R-lchild,d)|Getpath(R-rchild,d) coutdatausingnamespace std; templatestruct BiNode T data; BiNode*lchild; BiNode*rchild; ; templateclass BiTree private:
6、void Create(BiNode*/创建二叉树void Release(BiNode*R); /释放二叉树public : BiNode*root; /根节点BiTree(T data, int n); /构造函数void Preorder(BiNode*R); /前序遍历void Inorder(BiNode*R); /中序遍历void Postorder(BiNode*R); /后序遍历void Leveorder(BiNode*R); /层序遍历BiTree(); /析构函数int Count(BiNode*R); /结点数bool Getpath(BiNode*R, int d);
7、 /路径北京邮电大学信息与通信工程学院第 7 页int GetDepth(BiNode*R, int d); /深度; template void BiTree:Create(BiNode* /创建根节点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); /前序遍历template void BiTree:Preorder(Bi
8、Node*R) if(R!=NULL) coutdata; /访问节点Preorder(R-lchild); /遍历左子树Preorder(R-rchild); /遍历右子树 /中序遍历template void BiTree:Inorder(BiNode*R) if(R!=NULL) Inorder(R-lchild); /遍历左子树coutdata; /访问结点Inorder(R-rchild); /遍历右子树 /后序遍历template void BiTree:Postorder(BiNode*R) 北京邮电大学信息与通信工程学院第 8 页 if(R!=NULL) Postorder(R
9、-lchild); /遍历左子树Postorder(R-rchild); /遍历右子树coutdata; /访问结点 /层序遍历template void BiTree:Leveorder(BiNode*R) BiNode*queue100; int f=0; int r=0; /初始化空队列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=
10、p-rchild; /右孩子入队 /析1函数template void BiTree:Release(BiNode*R) if(R!=NULL) Release(R-lchild); 释放左子树Release(R-rchild); /释放右子树delete R; /释放根节点 /释放二叉树template BiTree:BiTree() Release(root); /求结点总数templateint BiTree:Count(BiNode *R) if(R=NULL) return 0; 北京邮电大学信息与通信工程学院第 9 页else int m=Count(R-lchild); int
11、n=Count(R-rchild); return m+n+1; /求深度template int BiTree:GetDepth(BiNode *R,int d) if(R=NULL) return d; if(R-lchild=NULL) else int m=GetDepth(R-lchild,d+1); int n=GetDepth(R-rchild,d+1); return nm?n:m; /查询结点路径? template bool BiTree:Getpath(BiNode*R,int d) if(R=NULL) returnfalse; if(R-data=d|Getpath(
12、R-lchild,d)|Getpath(R-rchild,d) coutdatatree(data,8); cout“前序遍历为：“; tree.Preorder(tree.root); coutendl; cout“中序遍历为：“; tree.Inorder(tree.root); coutendl; cout“后序遍历为：“; tree.Postorder(tree.root); 北京邮电大学信息与通信工程学院第 10 页coutendl; cout“层序遍历为：“; tree.Leveorder(tree.root); coutendl; cout“结点数为： “; couttree.Count(tree.root); coutendl; int depth=0; cout“深度为： “; couttree.GetDepth(tree.root,depth); coutendl; cout“指定结点 f,“ “则到 f的路径为： “; tree.Getpath(tree.root,f)
