《二叉树的遍历课程设计.doc》由会员分享，可在线阅读，更多相关《二叉树的遍历课程设计.doc（16页珍藏版）》请在三一文库上搜索。
1、数据结构课程设计报告设计题目： 二叉树的遍历 姓 名： 陈 雷 学 号： 211001047 专 业： 计算机科学与技术 院 系： 计算机科学与技术 班 级： 1002 指导教师： 吴克力 2012年 3 月 1日 摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC+，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树 遍历 非递归 C+ LCA Abstract: This paper
2、 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 - r
3、ecursive 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二、需求分析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一、问题描述问题描述：创建二叉树并遍历
5、基本要求：1、 分别运用非递归的方式完成对二叉树的先序和后序遍历2、 输出二叉树的高度3、 输出每一层的结点数4、 查找结点P 和结点Q的最近共同祖先二、需求分析1 本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2 程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。3 用户输入数据完毕，程序将输出运行结果。4 测试数据应为字符型数据。三、概要设计1创建二叉树输入数据不低于15个，用递归方法建立二叉树。2二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3二叉树的后序非递归遍历示
6、意图图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();/析构函数v
7、oid 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);/求树
8、中任意两结点最近共同祖先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 inor
9、der(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);/求最近
10、共同祖先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(root
11、ptr);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) st
12、ackBiNode* 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 da
13、ta; 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、
14、求二叉树每一层的结点数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(
15、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; i
16、f(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(
17、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-创建一颗
18、二叉树并显示 # 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:cou
19、tendl;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;coutc
20、h1;coutch2;coutch1和ch2的最近共同祖先是Tree.leastCommanAncestor(ch1, ch2)endl; break;case 6:return;break;default: cout请输入正确的选择！endl;break;3、测试数据AB#CD#E#FGH#K#4、测试结果七、调试分析创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算法测试，调用相应函数进行测试，结果正确。求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。计算每层结点数：调用levelNum()函数，测试结果正确。求最近共同祖先：调用LC
21、A()函数，测试结果正确。八、遇到的问题及解决办法 调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。九、心得体会通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。十、参考文献C+程序设计（第二版） 吴乃陵 况迎辉数据结构C+版 王红梅