实现二叉树的各种遍历算法实验报告.pdfVIP

实现二叉树的各种遍历算法实验报告

一实验题目:实现二叉树的各种遍历算法

二实验要求:

2.1:（1）输出二叉树b

（2）输出H节点的左右孩子节点值

（3）输出二叉树b的深度

（4）输出二叉树b的宽度

（5）输出二叉树b的节点个数

（6）输出二叉树b的叶子节点个数

（7）释放二叉树b

2.2：（1）实现二叉树的先序遍历

（2）实现二叉树的中序遍历

（3）实现二叉树的后序遍历

三实验内容:

3.1树的抽象数据类型:

ADTTree{

数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D为空集，则称为空树；

若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下

二元关系：

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无

前驱；

(2)若D-{root}≠NULL，则存在D-{root}的一个划分

D1,D2,D3,„,Dm(m0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对

任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有root,xi∈H;

(3)对应于D-{root}的划分，H-{root,xi,„,root,xm}有唯一的

一个划分H1，H2,„,Hm(m0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，

且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义

的树，称为根root的子树。

基本操作P：

InitTree(T);

操作结果：构造空树T。DestroyTree(T);

初始条件：树T存在。操作结果：销毁树T。

CreateTree(T,definition);

初始条件：definition给出树T的定义。

操作结果：按definition构造树T。

ClearTree(T);

初始条件：树T存在。

操作结果：将树T清为空树。

TreeEmpty(T);

初始条件：树T存在。

操作结果：若T为空树，则返回TRUE，否则返回FALSE。

TreeDepth(T);

初始条件：树T存在。操作结果：返回Ｔ的深度。

Root(T);

初始条件：树T存在。操作结果：返回T的根。

Value(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：返回cur_e的值。

Assign(T,cur_e,value);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：结点cur_e赋值为value。

Parent(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函

数值为“空”。

LeftChild(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，

否则返回“空”。

RightSibling(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。

InsertChild(T,p,I,c);

初始条件：树Ｔ存在，ｐ指向Ｔ中某个结点，1≤i≤p指结点的

度＋１，非空树ｃ与Ｔ不相交。

操作结果：插入