数据结构课程设计二叉树遍历.doc

《数据结构》课程设计报告
题目:二叉树的遍历日期: 2009-12-22
年级: 班级:
姓名: 学号:

更好的了解二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现流程及操作步骤。加深理论知识,提高实践能力。

二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,建树的实现。


(前、中、后)

(前、中、后)

以选择面板开始,显得更为清晰。其中3,4,5,6,8为添加内容,有助于更好的了解二叉树。


(1)定义二叉树结点值的类型为字符型。
(2)结点个数不超过10个。
(3)按先序次序输入,构造二叉链表表示的二叉树T,空格表示空树。
(前、中、后)
DLR
(1)访问根结点。
(2)先序遍历根结点的左子数。
(3)先序遍历根结点的右子数。
LDR
(1)先序遍历根结点的左子数。
(2)访问根结点。
(3)先序遍历根结点的右子数。
LRD
(1)先序遍历根结点的左子数。
(2)先序遍历根结点的右子数。
(3)访问根结点。

(1)访问该元素所指结点。
(2)若该元素所指结点的左右孩子结点非空,则该元素所指结点的左孩子指针和右孩子指针顺序入队。
(前、中、后)
(1)非递归的先序遍历算法
。
。
。
。
(2)非递归的中序遍历算法
。
。
。
。
(3)非递归的后序遍历算法
bt是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法,结点入栈时,配一个标志tag一同入栈
(1:遍历左子树前的现场保护,2:遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈,遍历左子树;
返回后,修改栈顶tag为2,遍历右子树;最后访问根结点。


a
b
c
d
e
f
g

#include ""
#include ""
#include ""
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入,构造二叉链表表示的二叉树T,空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输