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

1、数据结构课程设计报告设计题目：二叉树的遍历姓名：陈雷学号：211001047专业：计算机科学与技术院系：计算机科学与技术班级：1002指导教师：吴克力2012 年 3 月 1 日摘要： 本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为 VC+除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCQ 问题的算法。关键字：二叉树遍历非递归 C+LCAAbstract:Thispapermainlydescribeshowtoimpl

2、ementbinarytreetraversal.Thebinarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC+,inadditiontotravers

3、aloperation,alsoincreasedforsolvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor(LCA)algorithm.Keywords:binarytreetraversalnon-recursiveC+LCA目录、问题描述 4.4.问题描述：创建二叉树并遍历 4基本要求：4二、需求分析 4.4.三、概要设计 4.4.1 . .创建二叉树 42 . .二叉树的非递归前序遍历示意图 43 .二叉树的后序非递归遍历示意图 5四、数据结构设计 5

4、.5.1.1.二叉树结点数据类型定义为：52.2.二叉树数据类型定义为：5五、算法设计 6.6.1 1、创建二叉树 62 2、非递归前序遍历 73 3、非递归后序遍历 74 4、求二叉树的高度 85、求二叉树每一层的结点数 96、求两节点最近共同祖先 96 6、算法流程图 10六、程序测试与实现 1.11.11 1、函数之间的调用关系 112 2、主程序 113 3、测试数据 134 4、测试结果 13七、调试分析 1414八、遇到的问题及解决办法 1515九、心得体会 1515十、参考文献 1515一、问题描述问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二叉树的先序和后

5、序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点 P 和结点 Q 的最近共同祖先二、需求分析1 .本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2 .程序运行后显现提示信息，等候用户输入 06 以进入相应的操作功能。3 .用户输入数据完毕，程序将输出运行结果。4 .测试数据应为字符型数据。三、概要设计1 1 . .创建二叉树输入数据不低于 15 个，用递归方法建立二叉树。2 2 . .二叉树的非递归前序遍历示意图图 3.23.2 二叉树前序遍历示意图3 3 . .二叉树的后序非递归遍

6、历示意图图 3.43.4 二叉树后序遍历示意图四、数据结构设计1 1 . .二叉树结点数据类型定义为：templatestructBiNode(BiNode*rchild,*lchild;/指向左右孩子的指针Tdata;/结点数据信息;2 2 . .二叉树数据类型定义为：templateclassBiTree(templatefriendostream&operator(ostream&os,BiTree&bt);public:BiTree();/无参构造函数BiTree(intm);/有参空构造函数BiTree(Tary,intnum,Tnone);/有参构造函数Bi

7、Tree();/析构函数voidpreorder();/递归前序遍历voidinorder();/递归中序遍历voidpostorder();/递归后续遍历voidlevelorder();/层序遍历 intcount();/计算二叉树的结点数intdepth();/计算二叉树的深度voiddisplay(ostream&os);打印二叉树，有层次voidLevelNum();/计算每一层结点数voidPreOrder();/非递归前序遍历voidPostOrder();/非递归后序遍历voidcreat();/创建二叉树TleastCommanAncestor(Tva,Tvb);/求

8、树中任意两结点最近共同祖先 protected:/以下函数供上面函数调用/对应相同功能voidcreat(BiNode*&root);创建voidrelease(BiNode*&root);/删除BiNode*Build(Tary,intnum,Tnone,intidx);用数组创建二叉树voidPreOrder(BiNode*root);/前序遍历voidPostOrder(BiNode*root);后续遍历voidLevelNum(BiNode*root);/层序遍历voidpreorder(BiNode*root);/递归前序遍历voidinorder(BiNode*ro

9、ot);递归中序遍历voidpostorder(BiNode*root);/递归后续遍历voidlevelorder(BiNode*root);/层序遍历intcount(BiNode*root);计算结点数intdepth(BiNode*root);计算深度voiddisplay(ostream&os,BiNode*root,intdep);打印staticboolleastCommanAncestor(BiNode*root,Tva,Tvb,BiNode*&result,BiNode*parrent);/求最近共同祖先 private:BiNode*rootptr;);五、

10、算法设计1、创建二叉树/实现外部递归调用voidBiTree:creat()(creat(rootptr);)/类体内递归创建二叉树templatevoidBiTree:creat(BiNode*&root)(Titem;cinitem;if(item=#)root=NULL;else(root=newBiNode;root-data=item;creat(root-lchild);creat(root-rchild);2、非递归前序遍历templatevoidBiTree:PreOrder()PreOrder(rootptr);templatevoidBiTree:PreOrder(

11、BiNode*root)stackBiNode*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、非递归后序遍历templatevoidBiTree:PostOrder()PostOrder(rootptr);templatevoidBiTree:PostOrder(BiNode*root)stackBiNode*s;/定义栈，节点类型为 TreeNodeBiNode*p=root;

12、BiNode*pre=NULL;/pre 表示最近一次访问的结点while(p|!s.empty()(/沿着左孩子方向走到最左下。while(p)(s.push(p);p=p-lchild;)/getthetopelementofthestackp=s.top();/如果 p 没有右孩子或者其右孩子刚刚被访问过 if(p-rchild=NULL|p-rchild=pre)(/visitthiselementandthenpopitcoutdata;s.pop();pre=p;p=NULL;)else(p=p-rchild;)/endofwhile(p|st.size()!=0)4、求二叉树的高

13、度templateintBiTree:depth()(returndepth(rootptr);templateintBiTree:depth(BiNode*root)(intrdep,ldep;if(root=NULL)return0;else(ldep=depth(root-lchild);rdep=depth(root-rchild);return(rdepldep?rdep:ldep)+1;5 5、求二叉树每一层的结点数templatevoidBiTree:LevelNum()(LevelNum(rootptr);templatevoidBiTree:LevelNum(BiNode*r

14、oot)(queueBiNode*q;intfront,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个结点 level+;last=rear;first=front;6 6、求两节点最近共同祖先templateTBiTree:lea

15、stCommanAncestor(Tn1,Tn2)returnleastCommanAncestor(rootptr,n1,n2);templateTBiTree:leastCommanAncestor(BiNode*root,Tn1,Tn2)if(root=NULL|root-data=n1|root-data=n2)return-1;rchild!=NULL)&(root-rchild-data=n1|root-rchild-data=n2)returnroot-data;if(root-lchild!=NULL)&(root-lchild-data=n1|root-lch

16、ild-data=n2)returnroot-data;if(root-datan1&root-datadata;if(root-datan1&root-datan2)returnleastCommanAncestor(root-lchild,n1,n2);if(root-datadatarchild,n1,n2);6、算法流程图六、程序测试与实现1、函数之间的调用关系2、主程序voidmain()(BiTreeTree(1);while(1)couttt 欢迎使用本系统！endl;couttt#endl;couttt#endl;couttt#1-创建一颗二叉树并显示#endl

17、;couttt#2-遍历二叉树#endl;couttt#3-查询二叉树的深度和结点数#endl;couttt#4-查询每层结点数#endl;couttt#5-查找两节点评 DQ 的最近共同祖先#endl;couttt#6-退出#endl;couttt#endl;couttt#endl;coutx;switch(x)case1:cout请输入二叉树的前序遍历：endl;cout(以#作为分支结尾，例如：AB#C#)endl;Tree.creat();coutTree;coutendl;break;case2:coutendl;cout前序遍历为：;Tree.PreOrder();coutendl

18、;cout中序遍历为：;Tree.inorder();coutendl;cout后序遍历为：;Tree.PostOrder();coutendl;cout层序遍历为：;Tree.levelorder();coutendl;coutendl;break;case3:cout树的深度为：Tree.depth()endl;cout树的结点数：Tree.count()endl;coutendl;break;case4:Tree.LevelNum();break;case5:charch1,ch2;coutch1;coutch2;coutch1和ch2的最近共同祖先是Tree.leastCommanAn

19、cestor(ch1,ch2)endl;break;case6:return;break;default:cout请输入正确的选择！endl;break;3、测试数据AB#CD#E#FGH#K#4、测试结果欢迎使用本系统I工一创健二颗二叉树并显示#2r通历二叉科 tt3鲁询二黑词的深度和结点数#4查询每层结点致#5查找两 T 点F和Q的最近共同祖先#6退出#正入你的选择.1二叉树的前序遍历：区+公土#主叱例如士ABNttCttNJ欢迎使用本系统！ttttIttttttttttfttttttHttttWtttttt#Itittttt1创建一颗二叉树并显示2遍历一艮呀m查询二叉时的深度和结点数4查

20、询每层结点教tt一查找两节点P和。的最近共同祖先#”一退出ttuttttflnttttttnitttiittUftNNUftitNtttttttinuttiiflUttHtiuttttMtttt2-nut为为为为为为历历为为历历历历历历遍遍遍遍遍遍遍遍ABCDEFGHKBDCAEHGKFDCBHKGFEAnBRCFDGHK欢迎使用本系统！I1一创建一颗二叉树并显示2遍历二X村m警询二复国的尊度和结点数4一查询每层菇点皱5善战商节点P而Q的最近共同祖先6退出ftntttfffttttttnunnttftttttttnnttnnnnnunHttttnnttnnttffntttt请施入他的选择,3和的馋度为：5树的碓点数；?欢迎使用本系统！ttNMtttttlttttnUttNnttttntttttlttttMttttNttttNtltttttlUttNttttNttttIttti一创建一颗二叉树并显示2一遍历二叉树5查找两节点P和Q的最近共同祖先6痕出ntt请输入你的选择:量工层有1个结点一之小结点塞2层有急层有;2个结点篁4层有2个结点第5层有2个结点ttitntt* *- -m-lm-l亳亳噫祖区蕾噫祖区蕾丘审数数丘审数数近近你你