数据结构-树(1)

树(Tree)是n(n>=0)个结点的有限集。 n=0时称为空树。

在任意一棵非空树中:

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

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

树的定义其实是用到了递归方法，也就是在树的定义中还用到了树的概念。

树的定义还需要强调两点:

(1) n>0 时根节点是唯一的，不可能存在多个根节点，数据结构中的树只能有一个根节点。

(2)m>0时，子树的个数是没有限制的，但是它们一定是互不相交的。

结点分类

树的结点包含一个数据元素以及若干指向其子树的分支。结点拥有的子树数称为结点的度(degree)。

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

除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

这棵树结点的度最大值是结点D的度，为3，因此树的度也是3。

结点间关系

结点的子树的根称为该节点的孩子(child)，相应地，该节点称为孩子的双亲(parent)。

同一个双亲的孩子之间互称兄弟(sibling)。

结点的祖先是从根到该节点所经分支上的所有结点。所以对于H来说， D,B,A都是它的祖先。

反之，以某结点为根的子树中的任何一结点都称为该结点的子孙。B的子孙是D,G,H,I。

树的其他相关概念

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

如果某结点在第i层，那么其子树的根就在i+1层，其双亲在同一层的结点互为堂兄弟。

D,E,F是堂兄弟，G,H,I,J也是堂兄弟。

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

以上树共有4层，因此树的深度为4。

如果将树中结点的各子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

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

线性表和树的区别

​线性结构 

(1) 第一个数据元素，无前驱

(2) 最后一个数据元素，无后继

(3) 中间元素，一个前驱一个后继

树结构

(1) 根节点， 无双亲， 唯一

(2) 叶结点，无孩子，可以多个

(3) 中间结点，一个双亲多个孩子