二叉树地遍历课程设计C++含源代码

1、标准文档南京理 工大学课程设计报告作者:相蒙蒙学 号： 054913221001054913221001教学点:苏州市职业大学专业:机电一体化题目:二叉树的遍历指导者：_尚鲜莲_评阅者：_2014年4月标准文档综合成绩:指导者评语:南京理工大学课程设计报告评语指导者（签字）：年 月 日标准文档课程设计报告摘要摘要：本文主要说明如何实现二义树的遍历。此次二义树的遍历基丁二义树的二 义链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC+除了遍历操作 外，还增加了求二义树的深度，总结点数，每层结点数，以及最近共同祖先（LCA问

2、题的算法。关键词：二义树遍历二义树遍历标准文档目录1问题描述 .51.1问题描述：创建二义树并遍历 .52、需求分析.53、概要设计.53.1.创建二义树 .53.2二义树的非递归前序遍历示意图 .53.3二义树的后序非递归遍历示意图 .64、数据结构设计.64.1二义树结点数据类型定义 .64.2二义树数据类型定义 .75、算法设计.85.1创建二义树.85.2非递归前序遍历.85.3非递归后序遍历.95.4求二义树的高度.105.5求二义树每一层的结点数 .105.6求两节点最近共同祖先 .115.7算法流程图.126、程序测试与调试.126.1函数之间的调用关系 .126.2主程序 .1

3、36.3测试数据 .1 46.4测试结果 .157、 调试分析.178、遇到的问题及解决办法 .179、心得体会.1710、 参考文献 .18标准文档1、问题描述1.1问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二义树的先序和后序遍历2、输出二义树的高度3、输出每一层的结点数4、 查找结点P和结点Q的最近共同祖先2、需求分析1、本程序的功能包括二义树的建立，二义树的递归遍历，二义树的非递归遍历，查 询二义树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二义树的打印2、程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。3、用户输入数据完毕，程序将输出运行

4、结果。4、测试数据应为字符型数据。3、概要设计3. 1创建二叉树输入数据不低丁15个，用递归方法建立二义树。3.2二叉树的非递归前序遍历示意图标准文档图3.2二义树前序遍历示意图3.3二叉树的后序非递归遍历示意图图3.4二义树后序遍历示意图4、数据结构设计4.1二叉树结点数据类型定义为:template struct BiNode(BiNode *rchild,*lchild;/指向左右孩子的指针标准文档T data;/结点数据信息；4.2二叉树数据类型定义为：template class BiTree(template friend ostream & operator (ostre

5、am &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)

6、;/打印二叉树，有层次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

7、 idx); /用数组创建二叉树voidPreOrder(BiNode* root);前序遍历void PostOrder(BiNode* root);后续遍历voidLevelNum(BiNode* root);/层序遍历voidpreorder(BiNode* root);/递归前序遍历void inorder(BiNode* root); /递归中序遍历void postorder(BiNode* root);递归后续遍历void levelorder(BiNode*root);/层序遍历int count(BiNode* root);计算结点数int depth(BiNode* roo

8、t);计算深度void display(ostream& os,BiNode* root, int dep); /打印static bool leastCommanAncestor(BiNode *root, T va, T vb, BiNode*&result, BiNode* parrent); /求最近共同祖先private :BiNode *rootptr;标准文档;5、算法设计5.1创建二叉树/实现外部递归调用void BiTree:creat()creat(rootptr);/类体内递归创建二叉树template void BiTree:creat(BiNode *

9、 & root) T item;cinitem;if (item= # ) root=NULL;elseroot= new BiNode; root-data=item; creat(root-lchild);creat(root-rchild);5.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

10、.push(root);root=root-lchild;)if (!s.empty()(root=s.top();s.pop();root=root-rchild;)标准文档)5.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.empt

11、y()(/沿着左孩子方向走到最左下。while (p)(s.push(p);p = p-lchild;)/get the top element of the stackp = s.top();/如果敬有右孩子或者其右孩子刚刚被访问过if (p-rchild= NULL| p-rchild = pre)(/visit this element and then pop itcout data;s.pop();pre = p;p = NULL;) else(p = p-rchild;) /end of while(p | st.size()!=0)5.4求二叉树的高度template int B

12、iTree: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.5求二叉树每一层的结点数template void BiTree:LevelNum() (LevelNum(rootptr);)template void BiTree:LevelNum(

13、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;标准文档5

14、.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-dat

15、a = 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);5.7算法流程图标准文档6、程序测试与实现6.

16、1函数之间的调用关系标准文档cout tt# cout tt# coutx;switch (x)(case 1:(cout 请输入二叉树的前序遍历：endl;cout (以#作为分支结尾，例如：A B # # C # # ) endl; Tree.creat();coutTree;coutendl; break ;case 2:(6.2主程序void main()BiTree Tree(1);while (1)(cout tt欢迎使用本系统！ ！endl;cout tt# endl;cout tt#endl;cout tt#1-创建一颗二叉树并显示endl;cout tt#2-遍历二叉树end

17、l;cout tt#3-查询二叉树的深度和结点数endl;cout tt#4-查询每层结点数endl;cout tt#5-查找两节点桥口Q勺最近共同祖先endl;cout tt#6-退出endl;endl;endl;标准文档coutendl;cout 前序遍历为：”；Tree.PreOrder();coutendl;cout 中序遍历为：；Tree.inorder();coutendl;cout ”后序遍历为：”；Tree.PostOrder();coutendl;cout 层序遍历为：”；Tree.levelorder();coutendl;coutendl; break ;case 3:

18、(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 ;case 6: return ; break ;default : cout请输入正确的选择！ ！ 层启层1212 3 3 4 4 5 5请 WWW 弟ttttttttttttttttttttttttttttttUtttttttttttttttttttttttttttttttttttttttttttttttttt4tttttt1创建一颗二叉树并显示2 -痕后_曳松二叉优的尊度和结点数 备层皓点致ftttft4一萱询母房结点教G一查找两节点p和Q的最近共同祖先6-退.出蚣蟹选择: 削入F数 以Q数祥最ifI口心：信息:标准文档7、调试分析创建