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

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

2、inarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC+,inadditiontotraversaloperation,alsoincreasedfors

3、olvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor(LCA)algorithm.Keywords:binarytreetraversalnon-recursiveC+LCATOC o 1-5 h z HYPERLINK l bookmark8 一、问题描述4问题描述：创建二叉树并遍历4基本要求：4 HYPERLINK l bookmark10 二、需求分析4三、概要设计4 HYPERLINK l bookmark12 1创建二叉树4 HYPERLINK l b

4、ookmark14 2二叉树的非递归前序遍历示意图43二叉树的后序非递归遍历示意图5数据结构设计 HYPERLINK l bookmark18 1二叉树结点数据类型定义为：5 HYPERLINK l bookmark20 2二叉树数据类型定义为：5 HYPERLINK l bookmark22 五、算法设计61、创建二叉树6 HYPERLINK l bookmark24 2、非递归前序遍历7 HYPERLINK l bookmark26 3、非递归后序遍历7 HYPERLINK l bookmark28 4、求二叉树的高度8 HYPERLINK l bookmark30 5、求二叉树每一层的结

5、点数9 HYPERLINK l bookmark32 6、求两节点最近共同祖先9 HYPERLINK l bookmark34 6、算法流程图1011六、程序测试与实现 HYPERLINK l bookmark38 1、函数之间的调用关系11 HYPERLINK l bookmark40 2、主程序11 HYPERLINK l bookmark42 3、测试数据13 HYPERLINK l bookmark44 4、测试结果13 HYPERLINK l bookmark48 七、调试分析14 HYPERLINK l bookmark50 八、遇到的问题及解决办法15 HYPERLINK l b

6、ookmark52 九、心得体会15 HYPERLINK l bookmark54 十、参考文献15一、问题描述问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点P和结点Q的最近共同祖先二、需求分析本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。用户输入数据完毕，程序将输出运行结果。测试数据应为字符型数据。概要设计1创建二叉树输入数据不低于15个

7、，用递归方法建立二叉树。2二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四、数据结构设计二叉树结点数据类型定义为：templatetypenameTstructBiNodeBiNodeT*rchild,*lchild;/指向左右孩子的指针Tdata;/结点数据信息;二叉树数据类型定义为：templatetypenameTclassBiTreetemplatetypenameTfriendostream&operator(ostream&os,BiTreeT&bt);public:BiTreeO;/无参构造函数BiTree(in

8、tm);/有参空构造函数BiTree(Tary,intnum,Tnone);/有参构造函数BiTree();/析构函数voidpreorder();/递归前序遍历voidinorder();/递归中序遍历voidpostorder();/递归后续遍历voidlevelorder();/层序遍历intcount();/计算二叉树的结点数intdepth();/计算二叉树的深度voiddisplay(ostream&os);/打印二叉树，有层次voidLevelNum();/计算每一层结点数voidPreOrder();/非递归前序遍历voidPostOrder();/非递归后序遍历voidcre

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

10、iNodeT*root);/递归前序遍历voidinorder(BiNodeT*root);/递归中序遍历voidpostorder(BiNodeT*root);/递归后续遍历voidlevelorder(BiNodeT*root);/层序遍历intcount(BiNodeT*root);/计算结点数intdepth(BiNodeT*root);/计算深度voiddisplay(ostream&os,BiNodeT*root,intdep);/打印staticboolleastCommanAncestor(BiNodeT*root,Tva,Tvb,BiNodeT*&result,BiNodeT

11、*parrent);/求最近共同祖先private:BiNodeT*rootptr;五、算法设计1、创建二叉树/实现外部递归调用voidBiTreeT:creat()creat(rootptr);/类体内递归创建二叉树templatetypenameTvoidBiTreeT:creat(BiNodeT*&root)Titem;cinitem;if(item=#)root=NULL;elseroot=newBiNode;root-data=item;creat(root-lchild);creat(root-rchild);2、非递归前序遍历templatevoidBiTree:PreOrder

12、()PreOrder(rootptr);templatevoidBiTree:PreOrder(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

13、)stackBiNodeT*s;/定义栈，节点类型为TreeNodeBiNode*p=root;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;elsep=p-rchil

14、d;/endofwhile(p|st.size()!=0)4、求二叉树的高度templateintBiTree:depth()returndepth(rootptr);templateintBiTree:depth(BiNode*root)intrdep,ldep;if(root=NULL)return0;elseldep=depth(root-lchild);rdep=depth(root-rchild);return(rdepldep?rdep:ldep)+1;5、求二叉树每一层的结点数templatevoidBiTree:LevelNum()LevelNum(rootptr);templ

15、atevoidBiTree:LevelNum(BiNode*root)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个结点endl;level+;last=rear;first=front;6、求

16、两节点最近共同祖先templateTBiTree:leastCommanAncestor(Tn1,Tn2)returnleastCommanAncestor(rootptr,n1,n2);templateTBiTree:leastCommanAncestor(BiNode*root,Tn1,Tn2)if(root=NULL|root-data=n1|root-data=n2)return-1;if(root-rchild!=NULL)&(root-rchild-data=n1|root-rchild-data=n2)returnroot-data;if(root-lchild!=NULL)&(

17、root-lchild-data=n1|root-lchild-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

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

19、outendl;cout中序遍历为：；Tree.inorder();coutendl;cout后序遍历为：；Tree.PostOrder();coutendl；cout层序遍历为：；Tree.levelorder()；coutendl；coutendl；break；case3:cout树的深度为：Treedepth()endl;coutch1；cout请输入Q数据信息：；cinch2；coutchl和ch2的最近共同祖先是Tree.leastCommanAncestor(ch1,ch2)endl；break；case6:return；break；default:cout请输入正确的选择endl

20、；break；3、测试数据ab#cd#e#fgh#k#4、测试结果欢迎使用本系统！TOC o 1-5 h z#fl-创建一颛二叉树开显示A-遍历二叉秋查词二叉吠的滾展和结氐数4_杳荷每豆古占举了查品蕎节点P粘的最近共辰祖先右-退曲H#fl请新入你的选择：1诡输入二叉恻贰前底遍历：了就排作为分支结尾，例如：AB#C#)FK*G欢迎使用本系统！TOC o 1-5 h z丄-划建一颗二殳树并显示#-區历二叉內#3查询二叉讨的探度和结点数tt4-車询鱼尼蛤点藪U弓-查找两节点p和Q的最近共司祖先#-退出B为为询为遍遍诟遍序前中后层请输入你的选择：2ABCDEFGHKBDCAEHGKFDCBHKGFEAABECFEGHK欢独使用本系统！nnnnnnnnnnnttnnffnnnffnnttnnniinnttnnnnnnttnffnnTOC o 1-5 h z创建颗二叉树并显示#A-遍历二叉桝#2查询二貝词的渓度和结点数it-查询笹层结点数_#吐-杳找两节点P和。的最诉共同祖托#石-退由#择59远；的为数你度点入塞制的请窗欢迎使用本系统II-创建题二叉树并显示-；匾历二叉眉查询-马拥的探度和结点数4一一杳i句事貝2吉占*&蚕屋聶宰責需;的最近共同