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

1、实用文档南京理 工大学课程设计报告者作相蒙蒙学 号：054913221001教学占八、:苏州市职业大学专业:机电一体化题目:二叉树的遍历指导者：尚鲜莲评阅者：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主程序 136.3测试数据 146.4测试结果157、调试分析17&遇到的问题及解决办法

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

4、2二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3二叉树的后序非递归遍历示意图4、数据结构设计4.1二叉树结点数据类型定义为:template < type name T> struct BiNodeBiNode<T> *rchild,*lchild;指向左右孩子的指针T data;/结点数据信息；4.2二叉树数据类型定义为：template < type name T>class BiTreetemplate <type name T>friend ostream & operator <<(ostream &

5、amp;os ,BiTree<T> &bt);public :BiTree(); /无参构造函数BiTree( int m); /有参空构造函数BiTree(T ary, int num,T none);/ 有参构造函数BiTree(); /析构函数void preorder(); /递归前序遍历void inorder();/递归中序遍历void postorder(); /递归后续遍历void levelorder(); / 层序遍历int count();II计算二叉树的结点数int depth();II计算二叉树的深度void display(ostream &am

6、p;os); II 打印二叉树，有层次void LevelNum(); II计算每一层结点数void PreOrder(); II非递归前序遍历void PostOrder(); II非递归后序遍历void creat(); II 创建二叉树T leastCommanAncestor(T va, T vb);II求树中任意两结点最近共同祖先protected :II以下函数供上面函数调用II对应相同功能void creat(BiNode <T>* &root);II 创建void release(BiNode<T>* &root);II 删除BiNode

7、<T> * Build(T ary, int num,T none, int idx); II 用数组创建二叉树 voidPreOrder(BiNode<T>* root);II前序遍历void PostOrder(BiNode<T>* root); II 后续遍历 voidLevelNum(BiNode<T>* root);II层序遍历voidpreorder(BiNode<T>* root);II递归前序遍历void inorder(BiNode<T>* root); II 递归中序遍历 void postorder(

8、BiNode<T>* root);II 递归后续遍历void levelorder(BiNode<T>*root);II 层序遍历int count(BiNode<T>* root);II 计算结点数int depth(BiNode<T>* root);II 计算深度void display(ostream& os,BiNode<T>* root,int dep); II 打印static bool leastCommanAncestor(BiNode<T> *root, T va, T vb, BiNode<

9、;T>*&result, BiNode<T>* parrent); / 求最近共同祖先 private :BiNode<T> *rootptr;5、算法设计5.1创建二叉树/实现外部递归调用void BiTree<T>:creat()creat(rootptr);/类体内递归创建二叉树template < typename T>void BiTree<T>:creat(BiNode<T> * & root) T item;cin>>item;if (item= # ) root=NULL;

10、elseroot= new BiNode<T> root->data=item; creat(root->lchild); creat(root->rchild);5.2非递归前序遍历template < typename T>void BiTree<T>:PreOrder()PreOrder(rootptr);template < typename T>void BiTree<T>:PreOrder(BiNode<T>* root) stack <BiNode<T> *> s;w

11、hile (root!=NULL|!s.empty()while (root)cout<vroot->data;s.push(root); root=root->lchild;if (!s.empty()root=s.top();s.pop();root=root->rchild;5.3非递归后序遍历template < typename T>void BiTree<T>:PostOrder()PostOrder(rootptr);template < typename T>void BiTree<T>:PostOrder

12、(BiNode<T> *root)stack<BiNode<T>*> s; / 定义栈，节点类型为 TreeNode BiNode<T> *p = root;BiNode<T> *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

13、= NULL| p->rchild = pre)/visit this element and then pop itcout <<p->data;s.pop();pre = p;p = NULL;elsep = p->rchild; /end of while(p | st.size()!=0)5.4求二叉树的高度template < typename T>int BiTree<T>:depth()return depth(rootptr);template < typename T>int BiTree<T>:d

14、epth(BiNode<T> *root)int rdep,ldep;if (root=NULL)return 0;elseldep=depth(root->lchild); rdep=depth(root->rchild);return (rdep>ldep?rdep:ldep)+1;5.5求二叉树每一层的结点数template < typename T>void BiTree<T>:LevelNum()LevelNum(rootptr);template < typename T>void BiTree<T>:L

15、evelNum(BiNode<T> * root)queue <BiNode<T> *> q;int front,rear,first,last,level;front=rear=first=0;last=level=1;if (root)q.push(root);rear+;while (frontvrear)root=q.front();q.pop()；front+;if (root->lchild)q.push(root->lchild);rear+;if (root->rchild)q.push(root->rchild);r

16、ear+;if (front=last)cout<< "第"vvlevelvv "层有"wlast-firstw"个结点"<<endl;level+;last=rear;first=front;5.6求两节点最近共同祖先template v typename T>T BiTreevT>:leastCommanAncestor(T n1, T n2)return leastCommanAncestor(rootptr,n1,n2);template v typename T>T BiTreevT

17、>:leastCommanAncestor(BiNodevT> * 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->data = n2) return root->data;if (root->lchild != NULL) &&(root->l

18、child->data = n1 | root->lchild->data = n2) return root->data;if (root->data > n1 && root->data < n2)return root->data;if (root->data > n1 && root->data > n2)return leastCommanAncestor(root->lchild, n1, n2); if (root->data < n1 &&am

19、p; root->data < n2)return leastCommanAncestor(root->rchild, n1, n2);5.7算法流程图6、程序测试与实现6.1函数之间的调用关系创建遍历求节点数深度每层结点数求LCACreat()Depth()LCA()Preorder()Ino rder()LJPostorder()LJ6.2主程序void main()BiTreev char > Tree(1);while (1)coutvv "tt欢迎使用本系统！vvendl;coutvv "tt# " vvendl;coutvv &

20、quot;tt#vvendl;coutvv "tt#1-创建一颗二叉树并显示vvendl;coutvv "tt#2-遍历二叉树vvendl;coutvv "tt#3-查询二叉树的深度和结点数vvendl;coutvv "tt#4-查询每层结点数vvendl;coutvv "tt#5-查找两节点P和Q的最近共同祖先vvendl;coutvv "tt#6-退出vvendl;vvendl;vvendl;coutvv "tt# coutvv "tt# " coutvv "请输入你的选择: int x;c

21、in»x;switch (x)case 1:coutvv "请输入二叉树的前序遍历："vvendl;coutvv "(以#作为分支结尾，例如：A B # # C # # )"vvendl;Tree.creat();coutvvTree;coutvvendl; break ;case 2:coutvvendl;coutvv "前序遍历为：”；Tree.PreOrder();coutvvendl;cout< v"中序遍历为："；Tree.inorder();coutvvendl;coutvv "后序遍历

22、为：”；Tree.PostOrder();coutvvendl;coutvv "层序遍历为：”；Tree .l evelorder();coutvvendl;coutvvendl; break ;case 3: coutvv "树的深度为："vvTree.depth()vvendl; coutvv "树的结点数："vvTree.count()vvendl; coutvvendl; break;case 4:Tree.LevelNum(); break ;case 5:char ch1,ch2;coutvv "请输入P数据信息：&quo

23、t;；cin»ch1;coutvv "请输入C数据信息：”；cin»ch2;"vvTree .l eastCommanAncestor(ch1,coutvvchlvv"和"vvch2vv"的最近共同祖先是ch2)vvendl; break ;case 6: return ; break ;default : coutvv "请输入正确的选择！ ！ "vvendl; break ; 6.3测试数据AB#CD#E#FGH#K#6.4测试结果欢迎使用本系统I !1- -创建一颗二叉树并显示2- m叉两3一-查i

24、i每层绪点数ft弓-查找两芳点p和Q的最近共同祖先.#的深度剂结点数入你的选怡1入二叉树的前序遍历：| （以林屜坷夯支结周 Mn： ABoc#*）AEttCDttttttEttFGHttttKtttttt*-F欢迎使用本系统I !ft1 一創建一颗二叉树并显示#«2遍历二支树# 3-承二叉硯的探度和结点数«tt百一查询每层给点藪# 5-查找两节点P和啲最近共同祖先#tt退岀ttuitnNtttttttinitttNnuttHMttAttMnttttiinttttNMUttNnttttttMtttt请输入你的选择 2为为为为 历历历历 遍遍遍遍 前中后层ABCDEFGHK B

25、DCAEHGKF DCBHKGFEA nBECFDGHJC欢迎使用本系统I IttHttttttNtttttlttttNttttHttttttttttttNttttHttttNttttNttttttNttttMtttttti-6'B二颗二叉树并显示玄一遍历二叉护ts查询二叉讨的琛度和结点数4一査询每层鉛点藪5 查找两节点P和Q的最近共同祖先6 iRtHtt#tt请樹入坐的选择* 3 度为：§ 關的密点数；?Itttft0fttttt tttt#1-lJ建一颗二叉树并显示2 -通历_支茯''二叉洞的稀度和结点数 症层拮点域G的请11Ftttttttt4欢迎使用本系统！ttttflttttMUttNttttNnttHNttttNttttNtttt