二叉树数据类型.docx

一、题目

采用字符类型为元素信息，用顺序存储结构和链式存储结构，实现二叉树抽象数据类型。

ADTBiTree{

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

若D为空集，则称为空二叉树；

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

在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

若D–{root}≠Φ，则存在D–{root}的一个划分DD，D∩D=Φ;

l r l r

若D

l

*Φ,则D

l

中存在惟一的数据元素x

l

，root,x∈H，且存在

l

D 上的关系H

l l

H；若D

r

*Φ,则D

r

中存在惟一的数据元素x

r

，root,

x∈H，且存在D

r r

上的关系H

r

H；

（4） （D，{H

l

}）是一棵符合本定义的二叉树，称为根root的左子树；

l、

（D，{H }）是一棵符合本定义的二叉树，称为根root的右子树。

r r、

基本操作P：

InitBitree(T);

操作结果：构造空二叉树。

CreateBitree(T);

初始条件：二叉树存在。

操作结果：按输入格式构造二叉树。

DestroyBitree(T);

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

ClearBitree(T);

初始条件：二叉树存在。

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

BitreeEmpty(T);

初始条件：二叉树存在。

操作结果：若T为空二叉树，则返回TURE，否则FALSE。BitreeDepth(T);

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

Root(T);

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

Value(T,e);

初始条件：二叉树存在，e是T中某个结点。操作结果：返回结点e的值。

Assign(T,e,value);

初始条件：二叉树存在，e是T中某个结点。操作结果：结点e赋值为value。

Parent(T,e);

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

操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。

LeftChild(T,e);

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

操作结果：返回e的左孩子。若e无左孩子，则返回“空”。

RightChild(T,e);

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

操作结果：返回e的右孩子。若e无右孩子，则返回“空”。

PreOrder(T);

初始条件：二叉树存在。

操作结果：先序遍历T，按顺序输出每个结点。InOrder(T);

初始条件：二叉树存在。

操作结果：中序遍历T，按顺序输出每个结点。PostOrder(T);

初始条件：二叉树存在。

操作结果：后序遍历T，按顺序输出每个结点。LevelOrder(T);

初始条件：二叉树存在。

操作结果：按层遍历T，按顺序输出每个结点。

}ADTBiTree

二、存储结构定义

公用头文件dso.h：#includeiostream.h#includestdlib.h

#includestring.h //字符串操作

#includemath.h //数学

#includememory.h //内存操作文件

#includetime.h //系统时间

#includequeue.h //队列

usingnamespacestd;#defineTURE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineMAXLEN30#defineElemTypechar#defineStatusint

顺序存储结构

#defineMAX_SIZE100

typedefElemTypeSqBitree[MAX_SIZE];

链式存储结构

typedefstructBiTNode

{

ElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*Bitree;

三、算法设计

顺序存储结构

StatusInitBitree(SqBitreeT)

//构造空二叉树。

{

//置为空树

memset(T,0,sizeof(T));

T[0]=;

T[1]=#;

returnOK;

}

StatusCreateBitree(SqBitreeT)

//按输入顺序构造二叉树。

{

//按照完全二