遍历二叉树的遍历课程设计

《数据结构》课程设计报告设计题目 二叉树的遍历

姓名

___________学 号 211001047________专 业 计算机科学与技术院 系 计算机科学与技术班 级 1002_____________指导教师 吴克力___________

2012年3月1日摘要:本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括:前序遍历 中序遍历 后续遍历层序遍历。其中前序遍历和后续遍历采用非递归算法实现。 编程环境为VC++,除了遍历操作外还增加了求二叉树的深度总结点数每层结点数 以及最近共同祖先LCA问题的算法。关键字:二叉树遍历非递归C++LCA

Abstract:This paper mainly describes how to implement bin ary tree traversal Thebin ary tree traversal is based on bin ary tree binary storage structure.Traversalmethod in eludes:preorder traversaljnorder traversal,postorder traversal, levelordertraversal.The former preorder traversal and postorder use of non・ recursivealgorithm.Programming environment is VC++z in addition to traversal operation,also in creased for solving the bin ary tree depth、 summary points and each layer ofno des,as well as the most rece nt comm on ancestor(LCA)algorithm.

Keywords:binary tree traversal non-recursive C++LCA

目录

一. 问题描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

问题描述创建二叉树并遍历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

基本要求. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

二. 需求分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

三.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .概

要设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

1 ・创建二叉树. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .二叉

树的非递归的序遍历示意图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

3・二叉树的后序非递归遍历示意图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

四.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .数

1. 二叉树结点数据类型定义为:

据结构设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. 二叉树数据类型定义为. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

五.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .算

法设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2、非递归前序遍历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7

3、非递归后序遍历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7

4、求二叉树的高度. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8

5、 求二叉树每一层的结点数. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

6、求两节点最近共同祖先. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

6、算法流程图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

六、程序测试与实现. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1

1、 函数之间的调用关系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11

2、主程序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11

3、测试数据. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

4、测试结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

七、调试分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

八、遇到的问题及解决办法 • ••••••

九.心得体会 • ••••••

十.参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

一、 问题描述

问题描述创建二叉树并遍历

基本要求

1、 分别运用非递归的方式完成对二叉树的先序和后序遍历

2、 输出二叉树的高度

3、 输出每一层的结点数

4、 查找结点P和结点Q的最近共同祖先

二、需求分析

1. 本程序的功能包括二叉树的建立二叉树的递归颯历二叉树的非递归遍历查询二叉树的

深度查询每层的结点数查找两个结点的最近共同祖先二叉树的打印。

2. 程序运行后显现提示信息等候用户输入0—6以进入相应的操作功能。

3. 用户输入数据完毕程序将输出运行结果。

4. 测试数据应为字符型数据。

三、概要设计

1.创建二叉树

输入数据不低于15个用递归方法建立二叉树。

2.二叉树的非递归前序遍历示意图

图3.2二义树前序遍历示意图

3.二叉树的后序非递归遍历示意图

图3.4二义树后序遍历示意图

四. 数据结构设计

1. 二叉树结点数据类型定义为template<typename T>struct BiNode

{

BiNode<T>*rchild, *lch订d;//指向左右孩子的指针

T data; //结点数据信息

}

2. 二叉树数据类型定义为template<typename T>class BiTree

{template<typename T>friend ostream&operator«(ostream&os ,BiTree<T>&bt);public

B订ree();//无参构造函数

BiTree(int m) {} ;//有参空构造函数

BiTree(T ary[], int num,T none) ; //有参构造函数

"BiTree 0; 〃析构函数void preorder 0;7递归前序遍历void inorder() ;7递归中序遍历void postorder 0;//递归后续遍历void levelorder 0;//层序遍历int count()://讣算二叉树的结点数int depth();//ir算二叉树的深度void display(ostream&os);//打印二叉树,有层次void LevelNumO;//计算每一层结点数void PreOrder 0;//非递归前序遍历void PostOrder 0;//非递归后用遍历void creat ();//创建二叉树T leastCommanAncestor (T va,T vb); //求树中任意两结点最近共同祖先p r o te c te d

//以下函数供上而函数调用

//对应相同功能void creat(BiNode<T>*&root);//创建void release(BiNode<T>*&root) ;//删除

BiNode<T> *Bui Id (T ary[], int num, T none, int idx)数组创建二叉树void PreOrder(BiNode<T>* root) ;//前序遍历 void PostOrder (BiNode<T>* root) ;//后续遍历 voidLevelNum(BiNode<T>* root); //层序遍历void preorder (BiNode<T>* root) ; //递归前序遍历void inorder (BiNode<T>*root);//递中序遍历void postorder (BiNode<T>*root) ;//递归后续遍〃j void levelorder (BiNode<T>*root) ;//层序遍历int count (BiNode<T>* root) ;//il*算结点数intdepth(BiNode<T>*root);//讣算深度void display(os tream&os,BiNode<T>*root, int dep); //扌丁卬static boolleastCommanAncestor(BiNode<T>*root,T va,T vb,BiNode<T>*&result,BiNode<T>*parrent)  /7求最近共同祖先pri v ate

BiNode<T>*rootptr;

};

五、算法设计

1、创建二叉树

//实现外部递归调用void BiTree<T>: :creat() {c re at(ro otptr);

}

//类体内递归创建二叉树template<typename T>

void BiTree<T> :creat(BiNode<T>*&root){

T item;cin»item;if(item=='于)root=NULL;elseroot->data=item;cre at(ro ot->lchild);creat(root">rchil d);

}

}

2、非递归前序遍历template<typename T>void BiTree<T>: :PreOrder 0

{

P re Orde r(roo tptr);

}template<typename T>void BiTree<T> :PreOrder(BiNode<T>*root){stack<Bi No de<T>*>s;whi 1 e(root!=NULL: !s.empty())

{whi l e(ro o t)

{cout«root->data;s・pus h(ro ot);ro ot=:ro ot->lchild;

}i f(!s.e m pty0)

{root=s・ top();s・pop();root=root">rchild;

}

}

}

3、非递归后序遍历template<typename T>void BiTree<T>: :PostOrder()

{

P o stOrder(rootptr);

}template<typename T>

void BiTree<T> :PostOrder(BiNode<T>*root)

{stack<BiNo de<T>*>s;//定义栈.节点类型为Tre eXo deBiNode<T>*p=root;

BiNo de<T>*pre=NUL L;//pre.让近一次访问的