二叉树的遍历.doc
需积分: 0 41 浏览量
2009-08-11
00:53:06
上传
评论
收藏 191KB DOC 举报
题目：二叉树的遍历
班级：9451 姓名：康提 学号：052363 完成日期：2007-10-5
一、 需求分析：
1、 本程序的功能是对任意二叉树进行递归前序遍历、中序遍历和后序遍历，用栈实现无
递归的前序和中序遍历，并对二叉树进行线索化谦虚和中序遍历。
2、 本程序要求用户以字符输入，若要实现终端结点，则将其左右孩子的数据以空格输入 ，
最后以回车键建入数据。
3、 本程序的结果将依次打印出递归前序遍历、中序遍历和后序遍历，用栈实现无递归的
前序和中序遍历，和线索化谦虚和中序遍历的结果。
4、 演示程序以用户与计算机对话的方式进行,即在计算机终端上显示提示信息后,由用户在
键盘上输入演示程序中规定的命令,相应的输入数据和运算结果显示在其后。
5、 测试数据（附后）。
一、 概要设计：
1、 抽象数据类型定义如下：
ADT Stack{
数据对象：D={ai|ai∈Elemset,i=1,2,3…n,n>=0}
数据关系：Rl={<a(i-1),ai>|a(i-1),ai∈D,i=2,…n}
基本操作：
InitStack(&S)
操作结果：构造一个空栈。
Push(&S,&e)
初试条件：栈 S 已存在。
操作结果：插入元素 e 为新的栈顶元素。
Pop(&S,&e)
初始条件：栈 S 已存在且非空。
操作结果：删除 S 的栈顶元素，并用 e 返回其值。
}ADT Stack
}
2．抽象数据二叉树的定义如下：
ADT BinaryTree{
数据对象 D：D 是具有相同特性的数据元素集合。
数据关系 R：若 D=Ф，则 R=Ф，称 BinaryTree 为空二叉树；
若 D≠Ф，则 R={H}，H 是如下二元关系：
（1） 在 D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前驱；
（2） 如 D-{root}≠Ф,则存在 D-{root}={D
1
,D
r
},且 D
1
∩D
r
=Ф;
（3） 如 D
1
≠Ф,则 D1 中存在唯一元素 x
1
,<ROOT,X< SPAN>
1
>∈H,
且存在 D
1
上的关系 H
1
∈H；如 D
r
≠Ф，则 D
r
中存在唯一的元素
x
r
，<ROOT,X< SPAN>
r
>∈H,且存在 D
r
上的关系 Hr 包含于 H；
H={<ROOT,X< SPAN>
1
>,<ROOT,X< SPAN>
r
>,H
1
,H
r
}；
（4） (D1,{H1})是一棵符合本定义的二叉树，称为根的右子树。
基本操作 P：
InitBiTree(&T);
剩余12页未读，继续阅读
评论0
最新资源