《二叉树的遍历课程设计含源代码.docx》由会员分享，可在线阅读，更多相关《二叉树的遍历课程设计含源代码.docx（16页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计报告设计题二叉树的遍历名学 号专 业院系 班级计算机科学与技术计算机科学与技术1002指导教师2012年 3月 1日摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于 二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历， 后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。 编程环境为VC+，除了遍历操作外，还增加了求二叉树的深度，总 结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树遍历非递归C+ LCAAbstract: This paper mainly describes how to implement binary
2、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 environmen
3、t 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数据结构课程设计r-一、问述4问题描述：创建二叉树并遍历4基本要求：4二需求分析4三、概要设计41
4、. 创建二叉树42. 二叉树的非递归前序遍历示意图43. 二叉树的后序非递归遍历示意图51. 二叉树结点数据类型定义为： 52. 二叉树数据类型定义为： 5五、算法设计61、创建二叉树62、非递归前序遍历73、非递归后序遍历74、求二叉树的高度85、求二叉树每一层的结点数96、求两节点最近共同祖先96、算法流程图10111、函数之间的调用关系112、主程序113、测试数据134、测试结果13七、调试分析14八、遇到的问题及解决办法15九、心得体会15十、参考文献15一、问题描述问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每
5、一层的结点数4、查找结点P和结点Q的最近共同祖先二、需求分析1. 本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉 树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2. 程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。3. 用户输入数据完毕，程序将输出运行结果。4. 测试数据应为字符型数据。1 .创建二叉树输入数据不低于15个，用递归方法建立二叉树。2 .二叉树的非递归前序遍历示意图先序序列i： i E F GTTI图3.2二叉树前序遍历示意图3. 二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四、数据结构设计1. 二叉
6、树结点数据类型定义为：template struct BiNode BiNode *rchild,*lchild;/指 向左右孩子的指针T data;/结点数据信息;2. 二叉树数据类型定义为：template class BiTree template friend ostream & operator (ostream &os ,BiTree &bt); public:BiTree();/无参构造函数BiTree(int m);/有参空构造函数BiTree(T ary, int num,T none);/有参构造函数BiTree();/析构函数void preorder();/递归前序遍历
7、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
8、:/以下函数供上面函数调用/对应相同功能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);/递
9、归中序遍历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
10、*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 B
11、iTree: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;/定义栈，节点
12、类型为 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 stackp = 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;e
13、lsep = 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;elseldep=depth(root-lchild);rdep=depth(root-rchild);return (rdepldep?rdep:ldep)+1;5、求二叉树每一层的结点数template void BiTree:
14、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层有la
15、st-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!= NUL
16、L) &(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, n
17、1, n2);6、算法流程图六、程序测试与实现1、函数之间的调用关系2、主程序void main()BiTree Tree(1);while(1)coutttcouttt#欢迎使用本系统！#endl;# 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
18、 (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
19、树的深度为：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请输入正确的选择endl;break;数据结构课程设计3、测试数据AB#CD#E#FGH#K#4、测试结果欢诅使用本系统！ !ftHtt【一
20、创建一颗二叉利并垦示fl# 2一遍力二叉枕fl# 3查询二叉暨的浅度和结点数fl料4香询每W结点新H# S一查找两节点两Q的最近共同祖先flttG-退由fl# fl请输入你的选玲1请布入二叉例嵌前序遍厄7以林作为分支结尾，例如：AB#C#)FK*-一GHx EA*-一CDB欢迎使用本系统！ !ttflttttttttttttttttttttflttttttttttttttttttttfltttttttttttttttttttttttttttttttt1 一刘建一颗二艾树并显示2 遍历二叉杖3 查询二叉洞的探度和结点数4 查询每层结点薮S一查找两节点P.和Q的最近共司祖先#6-溟出B请输入你的选
21、择：2为为为为 遍遍诡遍 序前中后层ABCDEFGHKBDCAEHGKFDCBHKGFEAABECFEGHK欢迎使用本系统！ !nnannniinnnnnnnnnnnannniinniinnttiiiinnnnnnanntttt# 一创建颗二叉树计显示# 2遍历二叉村#tt3查询二叉M的深度和结点数it# 4查询每层站点数# 5-杳找两节任P南Q的爵斤具同祖先# 6iEti#ttttttttflttttttftttttttftttttttttttttttttttttttttttttfltttttttttttttttttttttttttttt择5 9 迄.: 的为数 你度点 入缮 谶的 WWW欢
22、迎使用本系统I I flffnnffffnffttffnffnnffttnnnnnffitnffttffnffnnffttnnffnniitti一可建颗二叉树并显示2遍历二叉节tta查询-列a的洋度和结点数4一查询母层结点薮5一香找两节点徐S的最近共同祖先6民出请输入你的选择:层有1个结点2层有2个结点 3层有胃个结点 4层有2个结点 S层看2个结占flttttttttffttttttttttttttttttttttttttttttttRttttttttttttttttttttttttttttttfltt 4欢迎使用本系统！ I ttttttttttttttflttttttflttttttfl
23、ttttttflttttttfltttttttttttttttttttttttttttttttt :1创建一颗二叉树并显示:# 2一谪历二叉树# 3一查诃二又两的探度和结点数# 4查诃每度吉点数#S一查找两普点F和。的最近共同祖冗4# 6退!Z)# # ttttttftttttttflttttttflttttttflttttttflttttttflttttttttttttttttltttttttlttttttt请稳入你的选择：5请骚入F数据信息：F请端入Q数寤信息：GF和G的最近共同祖井是计七、调试分析创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算法测
24、试，调用相应函数进行测试，结果正确。求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。计算每层结点数：调用levelNum()函数，测试结果正确。求最近共同祖先：调用LCA()函数，测试结果正确。八、遇到的问题及解决办法调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时， 容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各 个难题。九、心得体会通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上， 多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课 程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因为本学期所 学的就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到后 来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经过慢慢的调 试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我 的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据 结构更加了解。十、参考文献C+程序设计（第二版）吴乃陵 况迎辉数据结构C+版王红梅
