西交《数据结构》faq（六）

沙鸥老师

西交《数据结构》FAQ（六）
第六章 树与二叉树
1、树的表示方法有哪几种？
树的表示方法有以下四种，各用于不同的目的
1）直观表示法
以倒着的分支树的形式表示。是数据结构中最常用的树的描述方法。
其特点就是对树的逻辑结构的描述非常直观。
2）嵌套集合表示法
将根结点视为一个集合，其子树构成集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。
3）凹入表示法  主要用于树的屏幕和打印输出。
4）广义表表示法  将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出米。
2、树的基本操作
InitTree(&T)初始化一棵空树T。
DestroyTree(&T)树T存在，现销毁树T。
CreateTree(&T，definition)按definiti给出树T的定义构造树T。
ClearTree(&T)树T存在，现将树T清为空。
TreeEmpty(T)若T为空树返回TRUE，否则FALSE。
TreeDepth(T)返回树T的深度。
Value(T，cur-e)cur-e是树T中某个结点，返回cur-e的值。
Assian(T，cur-e，value)给树中结点cur-e赋值为value。
Root(x)求结点x所在树的根结点。   Parent(T，cur-e)求树T中结点cur-e的双亲。若cur-e是T的非根结点，则返回它的双亲，否则函数值为“空”。
LeftChild(T，cur-e)若cur-e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。
RightSibling(T，cur-e)若cur-e有右兄弟，则返回它的右兄弟，否则函数值为“空”。
InsertChild(&T，&p，i，c)把以c为根结点的树，插入到树T中作为结点p的第i棵子树。
DeleteChild(&T，&p,i)删除T中p所指结点的第i棵子树。
p指向T中某个结点，1≤i≤p指结点的度。
TraverseTree(T，Visit())visit是对树的遍历操作。按某种次序对T的每个结点调用visit()一次且至多一次。一旦visit()失败，则操作失败。


3、树的双亲表示法
由树的定义，树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间(一维数组)存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息以及结点的双亲结点在数组中的序号。
树的这种存储方法称为双亲表示法。
#define MAXNODE<树中结点的最大个数>
typedef struct {
elemtype data；
int  parent；
}NodeType；
NodeType t{MAXNODE}；
4、二叉树的定义
1）定义：每个结点至多有两棵子树的有序树。
结点的度≤2(每个结点至多两棵子树)+左右有别(有序)。
2）二叉树的ADT定义
数据对象D
数据关系R
其余比照树的定义。
D是具有相同特性的数据元素的集合。
若D=φ，称BlnaryTree为空二叉树；若D≠φ，则R={H}是如下二元关系
1、在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
2、在D-{root}≠φ，则存在D-{root}={D1，Dr，)，且D1∩Dr=φ；
3、若D1≠φ，则D1中存在唯一元素x1，(root，x1)∈H，且存在D1上的关系H1H；若Dr≠φ，则Dr中存在唯一元素xr，(root，xr)∈H，且存在Dr上的关系HrH；
H={(root，x1)，(root，xr)，H1，Hr)；
4、(D1，{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树。
5、二叉树的基本操作
与树相仿，但分左右，操作位置更为明确
InitBiTree(&T)  置空  构造空二叉树T。
DestroyBiTree(&T)  “收回”  销毁二叉树T。
CreateBiTree(&T，definition)  新建  按definiti定义的二叉树构造二叉树T。
ClearBiTree(&T)  清空  将二叉树T清为空。
BiTreeEmpty(T)  判空  若T为守返回TRUE，否则返回FALSE。
BiTreeDepth(T)：  求深度  返回T的深度。
Root(T)  求根  返回T的根。
Value(T，e)  求值  e是T中某个结点。返回e的值。
Assign(T，&e，value)  赋值  T中结点e赋值为value。
Parent(T，cur-e)  求父结点  若e是T的非根结点，则返回它的双亲，否则函数值为“空”。
LeftChild (T，e)  求e的左孩子。若e无左孩子，则返回“空”。
RightChild (T，cur-e)  求cur-e的右孩子。若e无右孩子，则返回“空”。
LeftSibling (T，e)  求e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。
RightSiblinq(T，e)  求e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。
InsertChild(T，p，LR，c)  插入字数  p指向T中某个结点，LR为0或1，某个结点的左或右子树。非空二叉树c与T不相交且右子树为空。根据LR为0或1，插入c为T中p指结点的左或右子树。P所指结点的原有左或右子树则成为c的右子树。
DeleteChild(T，p，LR)  删除子树  p指向T中某个结点，LR为0或1。根据LR为0或1，删除T中p所指结点的左或右子树。
6、二叉树的遍历
PreOrderTraverse(T，Visit())  前序遍历树visit是对结点操作的应用函数。先序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。
InorderTraverse(T，Visit())中序遍历树
PostOrderTraverse(T．Visit())候序遍历树
LeveleOrderTraverse(T，Visit())层次序遍历树
一棵树至少有一个结点，二叉树可是一棵空树。
对一棵树孩子的顺序是不重要的。
对二叉树只讲左右兄弟，不讲长次兄弟。


是两棵不同的二叉树。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986