Java数据结构--树

港控/mmm° 2023-10-06 10:32 49阅读 0赞

## `一、树的概念` ##

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

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

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

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 1]

#### 1.1 树的概念 ####

> 树是零个或多个结点的有限集合。结点树为0的数称为空树，结点树大于0的数称为非空树。在一颗树中：  
> 1）有且仅有一个特定的称为跟的结点。  
> 2）当结点数大于1时，除根结点外，其他结点被分成n(n > 0)个互不相交的子集：T1,T2,T3，…，Tn，其中每个子集本身又是一颗树（称为子树），每一棵子树的根xi (1 ≤ i ≤ n)都是根结点root的后续，树T1，T2，… ，Tn称为根的子树。

#### 1.2 树的基本语术 ####

> 结点的度：指结点拥有的子树的数目。  
> 叶子或终端结点：指度为0的结点。  
> 非终端结点或分支结点：指度不为0的结点。  
> 树的度：指树内各结点度的最大值。  
> 孩子和双亲：某个结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲。  
> 兄弟：同一个双亲的孩子结点互为兄弟。  
> 结点的层次：规定根所在的层次为第一层，根的孩子在第二层以此类推。  
> 树的深度或高度：树中结点最大的层数。  
> 有序数：指数中结点的各子树从左到右是有次序的，否则称为无序树。  
> 深林：指n（n ≥ 0）棵互不相交的树的集合。  
> 根据树的概念可知：树中任一个结点都可以有零个或多个后续结点（孩子），但是最多只能有一个前趋结点（双亲）；根结点无双亲，叶子结点无孩子；祖先与子孙的关系是父子关系的拓展；有序树中兄弟结点之间从左至右有次序之分。

## `二 、树的逻辑表示方法` ##

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

#### 2.1 树形图法 ####

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

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 2]

## 2.2 嵌套集合表示法 ##

> 嵌套集合法采用集合的包含关系表示树，`如图2.2所示`。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 3]

#### 2.3 广义表表示法 ####

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

#### 2.4 凹入表示法 ####

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

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 4]

## `三、 树的存储结构` ##

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

#### 3.1 双亲表示法 ####

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

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 5]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 6]  
> 在常规指针表示法中，每一个节点是一个结构，包含两个域：数据域和指针域。指针域指向该节点的双亲节点，没有双亲节点的指针域是空指针域。在仿真指针表示法中，每个节点是数组的一个元素，每个元素也包含数据域和指针域，但是指针域存放的是双亲节点所在的数组下标地址（即仿真指针），没有双亲节点的指针域为-1。  
> 双亲表示法多查找一个节点的双亲节点及祖先节点的操作十分便利，但是查找其孩子结点并不方便。

#### 3.2 孩子表示法 ####

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

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

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 7]

#### 3.3 双亲孩子表示法 ####

> 采用双亲表示法和孩子表示法的优势，使用指针即表示出每个结点的双亲结点，又表示出每个结点的孩子结点，就是双亲孩子表示法。指针域即包括指向孩子的指针，也包括指向双亲结点的指针。`图3.3`是双亲孩子表示法采用常规指针表示的存储结构，其中蓝线表示孩子指针，红线表示双亲指针。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 8]

#### 3.4 孩子兄弟表示法 ####

> 使用指针即指向每个结点的孩子结点，又指向每个结点的兄弟结点，就是孩子兄弟表示法。指针域包含两个指针，指向孩子结点的指针和指向最邻近兄弟结点的指针。  
> `图3.4`是常规指针表示的存储结构，其中蓝线表示孩子指针，红线表示兄弟指针。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200703223905919.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200703224757987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200703232736234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200703234133504.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200703234504735.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200704224939806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020070422541466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020070423050362.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200704233326181.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200704233245338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70