DS之树

DS之树

树型结构是一类非常重要的非线性数据结构，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。

树的定义

树(Tre)e是n(n>=0)个结点的有限集。在任意一棵非空树中：

(1)有且仅有一个特定的称为根(Root)的结点。

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，...，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

(3)树的结点包含一个数据元素及若干指向其子树的分支。

(4)结点拥有的子树数称为结点的度。

(5)度为0的结点称为叶子或终端结点。

(6)度不为0的结点称为非终端结点或分支结点。

(7)除根结点之外，分支结点也称为内部结点。

(8)树的度是树内各结点的度的最大值。

(9)结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。

(10)结点的层次从根开始定义起，根为第一层，根的孩子为第二层。

(11)树中各结点的最大层次称为树的深度或高度。

从上面的示例可以看出：

(1)这棵树的根为A。

(2)这棵树的深度或高度为5。

(3)这棵树的层次为五层。

(4)这棵树的叶子为：D，E，F，G，I，K。

(5)这棵树的度为3，因为这棵树中结点C有三个孩子并且为孩子最多的结点。

(6)这棵树的内部结点为：B，C，D，E，F，G，H，I，J，K。

如果将树结点的各子树看成从左至右是有次序的(即不能替换),则称该树为有序树，否则为无序树。

森林是m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

树的基本操作：

InintTree(&T)
操作结果：构造空树T
DestroyTree(&T)
初始条件：树T存在
操作结果：销毁树T
CreateTree(&T,definition)
初始条件;definition给出树的定义
操作结果：按definition构造树
ClearTree(&T)
初始条件;树T存在
操作结果：将树T清空为树
TreeEmpty(T)
初始条件：树T存在
操作结果：若T为空树，则返回TRUR，否则返回FALSE
TreeDepth(T)
初始条件：树T存在
操作结果：返回T的深度
Root(T)
初始条件：树T存在
操作结果：返回T的根
Value(T,e) 
初始条件：树T存在，e是T中的某个结点
操作结果：返回e的值
Assign(T,e,value)
初始条件：树T存在，e是T中的某个结点
操作结果：结点e赋值为value
Parent(T,e)
初始条件：树T存在，e是T中的某个结点
操作结果：若e是T的非根结点，则返回它的双亲，否则函数值为“空”
LeftChild(T,e)
初始条件：树T存在，e是T中的某个结点
操作结果：若e是T的非叶子结点，则返回它的最左孩子，否则函数值为“空”
RightChild(T,e)
初始条件：树T存在，e是T中的某个结点
操作结果：若e是T的非叶子结点，则返回它的最右孩子，否则函数值为“空”
InsertChild(&T,&p,i,e)
初始条件：树T存在，p指向T中的某个结点，1<=i<=p所指结点的度+1，非空树c与T不相交
操作结果：插入c为T中p指结点的第i棵子树
DeleteChild(&T,&p,i
初始条件：树T存在，p指向T中某个结点，1<=i<=p指结点的度
操作结果：删除T中p所指结点的第i棵子树
TraverseTree(T,Visit())
初始条件：树T存在，Visit是对结点操作的应用函数
操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败