树的定义
树是n(n>=0)个节点的有限集。n=0时称为空树,在任意一颗非空树中,有以下特性
1.有且仅有一个特定的称为跟的节点
2.当n>1时,其余节点可分为m(m>=0)个互不相交的有限集,其中每一个集合本身又是一棵树,并且称为根的子树
这个定义是一种比较新的定义方法,这里面用到了递归。
树的节点包含一个数据元素及若干指向其子树的分支。节点拥有的子树称为节点的度,度为0的节点称为叶节点或者终端节点。度部位0的节点称为非终端节点或者分支节点。除根节点之外,分支节点也成为了内部节点,树的度是树内各节点的度的最大值。
节点的子树的根称为节点的孩子,相应地,该节点称为孩子的双亲。同一个双亲的孩子之间互称兄弟,节点的祖先是从根到该节点所经过分支上所有节点,以某节点为根的子树中的任意节点都称为该节点的子孙。
树的抽象数据类型
Data:
树是由一个根节点和若干棵子树构成,树中节点具有相同数据类型及层次关系。
Operation:
InitTree:构造空树
DestroyTree:销毁树
CreateTree:按需定义构造树
clearTree:若树存在,则将树清空
TreeEmpty:若树为空,则返回true,否则返回false
TreeDepth:返回树的深度
Root:返回根节点
Value:返回一个节点的值
Assign:给节点赋值
Parent:如果是非Root节点,返回双亲
LeftChild:返回左孩子
RightSibling:返回右兄弟
InsertChild:插入子树
DeleteChild:删除子树