1、4、查找结点P 和结点Q的最近一路先人二、需求分析1本程序的功能包括二叉树的成立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近一路先人，二叉树的打印。2程序运行后显现提示信息，等候用户输入06以进入相应的操作功能。3用户输入数据完毕，程序将输出运行结果。4测试数据应为字符型数据。三、概要设计1创建二叉树输入数据不低于15个，用递归方式成立二叉树。2二叉树的非递归前序遍历示用意图二叉树前序遍历示用意3二叉树的后序非递归遍历示用意图二叉树后序遍历示用意四、数据结构设计1二叉树结点数据类型概念为：template struct BiNode BiNod
2、e *rchild,*lchild;/指向左右孩子的指针 T data; /结点数据信息;2二叉树数据类型概念为：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（）;/递归前序遍历 void inorder（）;/递归中序遍历 void postorder（）;/递归后续
3、遍历 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: /以下函数供上面函数挪用 /对应相同功能 void creat（Bi
4、Node * &root）;/创建 void release（BiNode/删除 * Build（T ary,int num,T none,int idx）;/用数组创建二叉树 void PreOrder（BiNode* root）;/前序遍历 void PostOrder（BiNode/后续遍历 void LevelNum（BiNode void preorder（BiNode void inorder（BiNode void postorder（BiNode void levelorder（BiNode*root）; int count（BiNode/计算结点数 int depth（BiN
5、ode/计算深度 void display（ostream& os,BiNode* root,int dep）;/打印static bool leastCommanAncestor（BiNode *root, T va, T vb, BiNode *&result, BiNode* parrent）;/求最近一路先人private: *rootptr;五、算法设计一、创建二叉树/实现外部递归挪用void BiTree:creat（） creat（rootptr）;/类体内递归创建二叉树creat（BiNodeitem; if（item=#） root=NULL; else root=new B
6、iNodedata=item; creat（root-lchild）;rchild）; 2、非递归前序遍历PreOrder（） PreOrder（rootptr）;PreOrder（BiNode* root） stack BiNode s; while（root!=NULL|!（） while（root） coutdata; （root）; root=root-lchild; if（! root=（）; （）;rchild;3、非递归后序遍历PostOrder（） PostOrder（rootptr）;PostOrder（BiNode *root） stack/概念栈，节点类型为TreeNod
7、e *p = root; *pre = NULL;/pre表示最近一次访问的结点 while（p|! /沿着左孩子方向走到最左下。 while（p） （p）; p = p- /get the top element of the stack p = （）; /若是p没有右孩子或其右孩子方才被访问过 if（p-rchild= NULL| p-rchild = pre） /visit this element and then pop it cout （）; pre = p; p = NULL; /end of while（p | （）!=0）4、求二叉树的高度int BiTreedepth（）
8、return depth（rootptr）;depth（BiNode rdep=depth（root- return （rdepldep?rdep:ldep）+1;5、 求二叉树每一层的结点数LevelNum（） LevelNum（rootptr）;LevelNum（BiNode * root） queue q; int front,rear,first,last,level; front=rear=first=0; last=level=1; if（root） （root）; rear+; while（frontlchild） （root- rear+; rchild） if（front=l
9、ast） cout第level层有last-first个结点endl; level+; last=rear; first=front;6、求两节点最近一路先人T BiTreeleastCommanAncestor（T n1, T n2） return leastCommanAncestor（rootptr,n1,n2）;leastCommanAncestor（BiNodedata = n1 | root-data = n2） return -1; if（root-rchild!= NULL） & （root-rchild-data = n2） return root-lchild !lchil
10、d- if（root-data n1 & root-data lchild, n1, n2）;rchild, n1, n2）; 6、算法流程图六、程序测试与实现一、函数之间的挪用关系二、主程序void main（） BiTree Tree（1）; while（1） coutx; switch（x） case 1: cout请输入二叉树的前序遍历：（以#作为分支结尾，例如：A B # # C # #） （）;Tree; break; case 2:前序遍历为：中序遍历为：后序遍历为：层序遍历为： case 3:树的深度为：（）ch1;请输入Q数据信息：ch2; coutch1和ch2的最近一路先
11、人是（ch1, ch2） case 6:return;break; default:请输入正确的选择！3、测试数据AB#CD#E#FGH#K#4、测试结果七、调试分析创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算法测试，挪用相应函数进行测试，结果正确。求二叉树深度和结点数：创建一个二叉树，挪用相关函数，测试结果正确。计算每层结点数：挪用levelNum（）函数，测试结果正确。求最近一路先人：挪用LCA（）函数，测试结果正确。八、碰到的问题及解决办法 调试时碰到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，通过查找资料、分步伐试
12、最终找到循环结束条件，顺利解决各个难题。九、心得体会通过本次课程设计，我发觉，有关一个课题的所有知识不单单是在讲义上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我熟悉到自己的缺点。本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以以为比较适合。刚开始以为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。通过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我加倍熟练的掌握各类方式。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构加倍了解。十、参考文献C+程序设计（第二版） 吴乃陵 况迎辉数据结构C+版 王红梅
