请你对Java中树的了解有多少？

1200101班的学生信息表如图6.1所示，其中学生被分到了不同的学习小组，第一组组长是李华，组员有王丽、张阳、赵斌; 第二组组长是孙琪，组员有马丹; 第三组组长是刘畅，组员有周天、黄凯

这些分组信息就构成了一棵树，如图6.2 所示。这就是一种典型的数据结构——树，要实现学生组员的插人、删除、查找等操作，就要用到树的相关知识。

树

6.1.1 树的概念及基本术语

1.树的概念

树(Tree) 是零个或多个结点的有限集合。结点数为0 的树称为空树，结点数大于0的树称为非空树。在一棵非空树中:

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

(2) 当结点数大于1时，除根结点外，其他结点被分成n (n>0 )个互不相交的子集:T1，T2,...，Tn,，其中每个子集本身又是一棵树( 称为子树)，每一棵子树的根x;( 1<=i<=n)都是根结点root 的后继，树'T1，T2，...，Tn。称为根的子树。

2.树的基本术语

结点的度(Degree):指结点拥有的子树的数目。

叶子或终端结点: 指度为0的结点。

非终端结点或分支结点: 指度不为0 的结点。

树的度: 指树内各结点的度的最大值。

孩子(Chi1d)和双亲(Parent):某个结点的子树的根称为该结点的孩子，相应的，该结点称为其孩子的双亲。

兄弟:同一个双亲的孩子结点互为兄弟。

结点的层次: 规定根所在的层次为第1层，根的孩子在第二层，依次类推。

树的深度或高度: 树中结点最大的层数。

有序树: 指树中结点的各子树从左至右是有次序的，否则称为无序树。

森林: 指n(n>=0)棵互不相交的树的集合。

根据树的概念可知: 树中任一个结点都可以有零个或多个后继结点( 孩子)，但最多只能有一个前趋结点(双亲);根结点无双亲，叶子结点无孩子; 祖先与子孙的关系是父子关系的拓展; 有序树中兄弟结点之间从左至右有次序之分。

【例6.1】列出如图6.3 所示的树的叶子结点、非终端结点、每个结点的度及树深度。

根据树的基本术语的相关概念有:

(1)叶子结点有: B、D、F、G、H、I、J。

(2)非终端结点有: A、C、E。

(3)每个结点的度分别是: A的度为4，C的度为2，E的度为3，其余结点的度为0。

(4)树的深度为3。

6.1.2 树的逻辑表示方法

树的常用表示方法有以下4 种: 树形图法、嵌套集合法、广义表表示法和凹入表示法。

1.树形图法

图6.4给出了图形表示树的直观表示法，其中用圆圈表示结点，连线表示结点间的关系，并把树根画在上面。树形图法主要用于直观描述树的逻辑结构。

2.嵌套集合法

嵌套集合法采用集合的包含关系表示树，如图6.5所示。

3.广义表表示法

广义表表示法以广义表的形式表示树，利用广义表的嵌套区间表示树的结构，如：A(B，C(E，F)，D(G))。

4.凹入表示法

凹入表示法采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。图6.6 所示为横向凹入表示。

6.1.3 树的存储结构

存储树时，既要存储结点的数据元素，又要存储结点之间的逻辑关系。结点之间的逻辑关系有: 双亲——孩子关系、兄弟关系。因此，采用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。

1.双亲表示法

使用指针表示每一个结点的双亲结点，即双亲表示法。每个结点包含两个域：数据域和指针域。双亲表示法存储如图6.7所示。

在常规指针表示法中，每一个节点是一个结构，包含两个域: 数据域和指针域。指针域指向该节点的双亲节点，没有双亲节点的指针域是空指针。在仿真指针表示法中，每个节点是数组的一个元素，每个元素也包含数据域和指针域，但是指针域存放的是双亲节点所在的数组下标地址( 即仿真指针)，没有双亲的节点指针域为-1。

双亲表示法对查找一个节点的双亲节点及祖先节点的操作十分便利，但是查找其孩子节点并不方便。

2.孩子表示法

使用指针表示出每个结点的孩子结点，即孩子表示法。由于每个结点的孩子结点个数不同，为了简便起见，孩子表示法中的每个结点的指针域个数是树的度。图6.8 是孩子表示法采用常规指针表示的存储结构。

孩子表示法与双亲表示法的特点相反。孩子表示法可方便地找到一个结点的孩子及其后裔，并能方便地实现树的遍历。

3.双亲孩子表示法

采用双亲表示法和孩子表示法的优势，使用指针既表示出每个结点的双亲结点，又表示出每个结点的孩子结点，就是双亲孩子表示法。指针域既包括指向孩子的指针，也包括指向双亲结点的指针。图6.9是双亲孩子表示法采用常规指针表示的存储结构，其中实线表示孩子指针，虚线表示双亲指针。

4.孩子兄弟表示法

使用指针既指向每个结点的孩子结点，又指向每个结点的兄弟结点，就是孩子兄弟表示法。指针域包含两个指针，指向孩子结点的指针和指向最邻近兄弟结点的指针。

图6.10是常规指针表示的存储结构，其中实线表示孩子指针，虚线表示兄弟指针。