《二叉树的遍历课程设计》由会员分享，可在线阅读，更多相关《二叉树的遍历课程设计（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计数据结构课程设计报告设计题目： 二叉树的遍历 姓 名： 陈 雷 学 号： 211001047 专 业： 计算机科学与技术 院 系： 计算机科学与技术 班 级： 1002 指导教师： 吴克力 2012年 3 月 1日 摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC+，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树 遍历 非递归 C+ LCA Abstract: Th
2、is paper 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
3、 non - recursive 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+
4、LCA目 录一、问题描述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(
7、);/析构函数void 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
8、 vb);/求树中任意两结点最近共同祖先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);/递归前序遍历v
9、oid inorder(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* parre
10、nt);/求最近共同祖先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()PreOr
11、der(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=s.top();s.pop();root=root-rchild;3、非递归后序遍历template void BiTree:PostOrder()PostOrder(rootptr);template void BiTree:PostOrder(BiNode *
12、root) stackBiNode* 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 data; 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
