二叉树的遍历课程设计.doc

数据结构课程设计数据结构课程设计报告设计题目： 二叉树的遍历 姓 名： 陈 雷 学 号： 211001047 专 业： 计算机科学与技术 院 系： 计算机科学与技术 班 级： 1002 指导教师： 吴克力 2012年 3 月 1日 摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC+，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树 遍历 非递归 C+ LCA Abstract: This paper mainly describes how to implement binary tree traversal. The binary tree traversal is based on binary tree binary storage structure. Traversal method includes: preorder traversal,inorder traversal, postorder traversal, levelorder traversal. The former preorder traversal and postorder use of non - recursive algorithm. Programming environment is VC + +, in addition to traversal operation, also increased for solving the binary tree depth 、 summary points and each layer of nodes, as well as the most recent common ancestor ( LCA ) algorithm.Keywords: binary tree traversal non-recursive C+ LCA目 录一、问题描述4问题描述：创建二叉树并遍历4基本要求：4二、需求分析4三、概要设计41创建二叉树42二叉树的非递归前序遍历示意图43二叉树的后序非递归遍历示意图5四、数据结构设计51二叉树结点数据类型定义为：52二叉树数据类型定义为：5五、算法设计61、创建二叉树62、非递归前序遍历73、非递归后序遍历74、求二叉树的高度85、求二叉树每一层的结点数96、求两节点最近共同祖先96、算法流程图10六、程序测试与实现111、函数之间的调用关系112、主程序113、测试数据134、测试结果13七、调试分析14八、遇到的问题及解决办法15九、心得体会15十、参考文献15一、问题描述问题描述：创建二叉树并遍历基本要求：1、 分别运用非递归的方式完成对二叉树的先序和后序遍历2、 输出二叉树的高度3、 输出每一层的结点数4、 查找结点P 和结点Q的最近共同祖先二、需求分析1 本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2 程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。3 用户输入数据完毕，程序将输出运行结果。4 测试数据应为字符型数据。三、概要设计1创建二叉树输入数据不低于15个，用递归方法建立二叉树。2二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四、数据结构设计1 二叉树结点数据类型定义为：template structBiNodeBiNode *rchild,*lchild;/指向左右孩子的指针T data; /结点数据信息;2 二叉树数据类型定义为：template class BiTreetemplate friend ostream & operator (ostream &os ,BiTree &bt);public:BiTree();/无参构造函数BiTree(int m);/有参空构造函数BiTree(T ary,int num,T none);/有参构造函数BiTree();/析构函数void preorder();/递归前序遍历void inorder();/递归中序遍历void postorder();/递归后续遍历void levelorder();/层序遍历int count();/计算二叉树的结点数int depth();/计算二叉树的深度void display(ostream &os);/打印二叉树，有层次void LevelNum();/计算每一层结点数void PreOrder();/非递归前序遍历void PostOrder();/非递归后序遍历void creat();/创建二叉树T leastCommanAncestor(T va, T vb);/求树中任意两结点最近共同祖先protected:/以下函数供上面函数调用/对应相同功能void creat(BiNode * &root);/创建void release(BiNode* &root);/删除BiNode * Build(T ary,int num,T none,int idx);/用数组创建二叉树void PreOrder(BiNode* root);/前序遍历void PostOrder(BiNode* root);/后续遍历void LevelNum(BiNode* root);/层序遍历void preorder(BiNode* root);/递归前序遍历void inorder(BiNode* root);/递归中序遍历void postorder(BiNode* root);/递归后续遍历void levelorder(BiNode*root);/层序遍历int count(BiNode* root);/计算结点数int depth(BiNode* root);/计算深度void display(ostream& os,BiNode* root,int dep);/打印static bool leastCommanAncestor(BiNode *root, T va, T vb, BiNode *&result, BiNode* parrent);/求最近共同祖先private:BiNode *rootptr;五、算法设计1、创建二叉树/实现外部递归调用void BiTree:creat()creat(rootptr);/类体内递归创建二叉树template void BiTree:creat(BiNode * & root)T item;cinitem;if(item=#) root=NULL;elseroot=new BiNode;root-data=item;creat(root-lchild);creat(root-rchild);2、非递归前序遍历template void BiTree:PreOrder()PreOrder(rootptr);template void BiTree:PreOrder(BiNode* root)stack BiNode * s;while(root!=NULL|!s.empty()while(root)coutdata;s.push(root);root=root-lchild;if(!s.empty()root=s.top();s.pop();root=root-rchild;3、非递归后序遍历template void BiTree:PostOrder()PostOrder(rootptr);template void BiTree:PostOrder(BiNode *root) stackBiNode* s;/定义栈，节点类型为TreeNode BiNode *p = root; BiNode *pre = NULL;/pre表示最近一次访问的结点 while(p|!s.empty() /沿着左孩子方向走到最左下。 while(p) s.push(p); p = p-lchild; /get the top element of the stack p = s.top(); /如果p没有右孩子或者其右孩子刚刚被访问过 if(p-rchild= NULL| p-rchild = pre) /visit this element and then pop it cout data; s.pop(); pre = p; p = NULL; else p = p-rchild; /end of while(p | st.size()!=0)4、求二叉树的高度template int BiTree:depth()return depth(rootptr);template int BiTree:depth(BiNode *root)int rdep,ldep;if(root=NULL)return 0;else ldep=depth(root-lchild);rdep=depth(root-rchild);return (rdepldep?rdep:ldep)+1;5、求二叉树每一层的结点数template void BiTree:LevelNum()LevelNum(rootptr);template void BiTree:LevelNum(BiNode * root)queue BiNode * q;int front,rear,first,last,level;front=rear=first=0;last=level=1;if(root)q.push(root);rear+;while(frontlchild)q.push(root-lchild);rear+;if(root-rchild)q.push(root-rchild);rear+;if(front=last)cout第level层有last-first个结点endl;level+;last=rear;first=front;6、求两节点最近共同祖先template T BiTree:leastCommanAncestor(T n1, T n2)return leastCommanAncestor(rootptr,n1,n2);template T BiTree:leastCommanAncestor(BiNode * root, T n1, T n2) if(root = NULL | root-data = n1 | root-data = n2) return -1; if(root-rchild!= NULL) & (root-rchild-data = n1 | root-rchild-data = n2) return root-data; if(root-lchild != NULL) & (root-lchild-data = n1 | root-lchild-data = n2) return root-data; if(root-data n1 & root-data data; if(root-data n1 & root-data n2) return leastCommanAncestor(root-lchild, n1, n2); if(root-data data rchild, n1, n2); 6、算法流程图程序初始化用户交互用户输入选择求共同祖先求每层结点数求深度遍历二叉树创建二叉树结束处理并输出结果六、程序测试与实现1、函数之间的调用关系main()每层结点数求LCA求节点数深度遍历创建LCA()Levelnum()Creat()Count()Depth()Inorder()Postorder()Preorder()2、主程序void main()BiTree Tree(1);while(1)couttt 欢迎使用本系统！ endl;couttt# endl;couttt# # endl;couttt# 1-创建一颗二叉树并显示 # endl;couttt# 2-遍历二叉树 # endl;couttt# 3-查询二叉树的深度和结点数 # endl;couttt# 4-查询每层结点数 # endl;couttt# 5-查找两节点P和Q的最近共同祖先 # endl;couttt# 6-退出 # endl;couttt# # endl;couttt# endl;coutx;switch(x)case 1:cout请输入二叉树的前序遍历：endl;cout（以#作为分支结尾，例如：A B # # C # #）endl;Tree.creat();coutTree;coutendl; break;case 2:coutendl;cout前序遍历为：;Tree.PreOrder();coutendl;cout中序遍历为：;Tree.inorder();coutendl;cout后序遍历为：;Tree.PostOrder();coutendl;cout层序遍历为：;Tree.levelorder();coutendl;coutendl; break;case 3: cout树的深度为：Tree.depth()endl;cout树的结点数：Tree.count()endl;coutendl;break;case 4:Tree.LevelNum(); break;case 5:char ch1,ch2;coutch1;coutch2;coutch1和ch2的最近共同祖先是Tree.leastCommanAncestor(ch1, ch2)endl; break