1、二叉树地遍历课程设计C+含源代码南 京 理 工 大 学课程设计报告作 者: 相蒙蒙 学 号：054913221001教学点:苏州市职业大学专 业:机电一体化题 目:二叉树的遍历指导者： 尚鲜莲 评阅者： 2014 年 4 月南 京 理 工 大 学课程设计报告评语综合成绩： 指导者评语： 指导者(签字)： 年 月 日课 程 设 计 报 告 摘 要摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC+，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层
2、结点数，以及最近共同祖先（LCA）问题的算法。关键词：二叉树 遍历 二叉树遍历6、程序测试与调试.121、问题描述 1.1问题描述：创建二叉树并遍历 基本要求：1、 分别运用非递归的方式完成对二叉树的先序和后序遍历2、 输出二叉树的高度3、 输出每一层的结点数4、 查找结点P 和结点Q的最近共同祖先2、需求分析1、本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2、程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。3、用户输入数据完毕，程序将输出运行结果。4、测试数据应为字符型数据。3
3、、概要设计31创建二叉树输入数据不低于15个，用递归方法建立二叉树。3.2二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图4、数据结构设计4.1二叉树结点数据类型定义为：template struct BiNode BiNode *rchild,*lchild;/指向左右孩子的指针 T data; /结点数据信息;4.2二叉树数据类型定义为：template class BiTree template friend ostream & operator (ostream &os ,BiTree &bt);public: Bi
4、Tree();/无参构造函数 BiTree(int m);/有参空构造函数 BiTree(T ary,int num,T none);/有参构造函数 BiTree();/析构函数 void preorder();/递归前序遍历 void inorder();/递归中序遍历 void postorder();/递归后续遍历 void levelorder();/层序遍历 int count();/计算二叉树的结点数 int depth();/计算二叉树的深度 void display(ostream &os);/打印二叉树，有层次 void LevelNum();/计算每一层结点数 void P
5、reOrder();/非递归前序遍历 void PostOrder();/非递归后序遍历 void creat();/创建二叉树 T leastCommanAncestor(T va, T vb);/求树中任意两结点最近共同祖先protected: /以下函数供上面函数调用 /对应相同功能 void creat(BiNode * &root);/创建 void release(BiNode* &root);/删除 BiNode * Build(T ary,int num,T none,int idx);/用数组创建二叉树 void PreOrder(BiNode* root);/前序遍历 vo
6、id PostOrder(BiNode* root);/后续遍历 void LevelNum(BiNode* root);/层序遍历 void preorder(BiNode* root);/递归前序遍历 void inorder(BiNode* root);/递归中序遍历 void postorder(BiNode* root);/递归后续遍历 void levelorder(BiNode*root);/层序遍历 int count(BiNode* root);/计算结点数 int depth(BiNode* root);/计算深度 void display(ostream& os,BiNo
7、de* root,int dep);/打印static bool leastCommanAncestor(BiNode *root, T va, T vb, BiNode *&result, BiNode* parrent);/求最近共同祖先private: BiNode *rootptr;5、算法设计 5.1创建二叉树/实现外部递归调用void BiTree:creat() creat(rootptr);/类体内递归创建二叉树template void BiTree:creat(BiNode * & root) T item; cinitem; if(item=#) root=NULL; e
8、lse root=new BiNode; root-data=item; creat(root-lchild); creat(root-rchild); 5.2非递归前序遍历template void BiTree:PreOrder() PreOrder(rootptr);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=
9、s.top(); s.pop(); root=root-rchild; 5.3非递归后序遍历template void BiTree:PostOrder() PostOrder(rootptr);template void BiTree:PostOrder(BiNode *root) stackBiNode* s;/定义栈，节点类型为TreeNode BiNode *p = root; BiNode *pre = NULL;/pre表示最近一次访问的结点 while(p|!s.empty() /沿着左孩子方向走到最左下。 while(p) s.push(p); p = p-lchild; /g
10、et 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 data; s.pop(); pre = p; p = NULL; else p = p-rchild; /end of while(p | st.size()!=0)5.4求二叉树的高度template int BiTree:depth() return depth(rootptr);template int
11、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.5 求二叉树每一层的结点数template void BiTree:LevelNum() LevelNum(rootptr);template void BiTree:LevelNum(BiNode * root) queue BiNode * q; int front,rear,first
12、,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; 5.6求两节点最近共同祖先template T BiTree:leastCommanAncestor(T n
13、1, 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!= NULL) & (root-rchild-data = n1 | root-rchild-data = n2) return root-data; if(root-lchild != NULL) & (root-
14、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, n1, n2); 5.7算法流程图6、程序测试与实现6.1函数之间的调用关系6.2主程序void main() BiTree Tree(1); while(1) couttt 欢迎使用本系统！ en
15、dl; couttt# 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(x) case 1: cout请输入二叉树的前序遍历：endl; cout（以#作为分支结尾，例如：A B # #
16、 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树的深度为：Tree.depth()endl; cout树的结点数：Tree.co
17、unt()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; 6.3测试数据AB#CD#E#FGH#K#6.4测试结果7、调试分析 创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算
18、法测试，调用相应函数进行测试，结果正确。求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。计算每层结点数：调用levelNum()函数，测试结果正确。求最近共同祖先：调用LCA()函数，测试结果正确。8、遇到的问题及解决办法 调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。9、心得体会 通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经过慢慢的调试，最终测试成功。 这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。 总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。10、参考文献1崔俊凯. 计算机软件设计M.机械工业出版社,2007.92吴乃陵 ,况迎辉 .C+程序设计（第二版）. 高等教育出版社,2006.33王红梅 .数据结构C+版M.清华大学出版社，2011.6
