数据结构-树

冷不防 2022-12-29 06:43 10阅读 0赞

### 文章目录 ###

*  树基础定义
 *  树的存储结构
 *   *  线性存储
     *  链式存储
 *  二叉树

# 树基础定义 #

*  树定义  
    树使用有n个节点的一种数据结构。  
    n=0时为空树，n>=0时树有且只有一个根节点（root节点）；  
    n>1时，其余节点可分为m个互不相交的有向集T1,T2…  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70]
 *  结点分类

1.  树的结点包含一个数据元素和若干指向子树的分支。
2.  结点拥有的子树数，称为结点的度。
3.  度为0的结点称为叶子结点或者终端结点，度不为0的结点称为分支结点。
4.  树的度是树内各结点的最大值。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 1]

*  结点间关系  
    结点子树根称为结点的孩子；  
    相应该节点是孩子的双亲，结点不分父母男女；  
    同一个双亲孩子互称兄弟；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 2]
 *  结点的层次  
    结点的层次从根开始定义。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 4]

# 树的存储结构 #

在学数据结构“树”之前希望大家一定要学过数组、链表这些基础数据结构，不然可能会看不懂，如果没有学过可以看看我的博客[数据结构-链表][-]、[Java中的数组、ArrayList源码剖析][Java_ArrayList]  
在讨论树的存储结构我们采用逐步深入，而不是直接写出如何实现树存储结构，这样更能帮助大家理解为什么要这么设计树的存储结构。  
提到存储方式，那就是考虑到底是基于线性（数组）存储方式，或者链式存储方式。线性和链式是讨论存储方式，至于如何组织线性和链式是存储的方法。我下面给大家介绍三种方法，由浅入深。

## 线性存储 ##

*  方法一：双亲表示法（线性存储）（不推荐采用）  
    假设以一段连续空间存储树的结点，同时设置一个指示器指向双亲结点到链表中的位置。每个结点知道自己的数据，还知道双亲的位置。  
    ![结点结构][20201221152933462.png]  
    data是数据域，存储结点信息；  
    parent是指针域，存储双亲位置；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 6]  
    这样的存储结构，我们可以通过parent轻松的找到双亲，直到找到parent=-1时，说明找到树的根节点。  
    当然，这样存储结构我们每个结点只能找到双亲，但是我们想要直到孩子，那我们只能基于数组在改变存储结构，每个结点在开辟一个孩子域，改变后如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 7]  
    但是这个时候我们只知道结点长子，其中一个孩子结点，但是如果我们想要知道结点其它孩子结点，那么只能再给结点创建更多的指针域，指向孩子，那这样会空间占用过大。

## 链式存储 ##

*  孩子表示法（链式）  
    谈到链式存储树，最容易想到就是孩子表示法，只需要结点存储上它孩子指针，那我就可以把整棵树存储起来，可是**普通树中结点有几个孩子并不知道**（当然二叉树就肯定知道一个结点至多有两个孩子，但是普通树对结点孩子数目没有限制）具体孩子表示法我们看下面。
 *  孩子表示法就是在结点中存储所有孩子指针，孩子表示法结点结构：  
    ![在这里插入图片描述][2020122302040155.png]  
    **data为数据域；  
    degree是度域（前面我们提到无法知道结点有几个孩子，所以需要专门存储结点的度）  
    child1-childx（若干个孩子结点指针域）**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 8]  
    这种方法克服线性浪费空间的问题，但是因为要维护度域，造成空间浪费，所有有了下面的孩子兄弟表示法。
 *  孩子兄弟表示法（链式）  
    对于普通树我们采取孩子兄弟表示法在好不过了。这里为什么说是普通树呢，因为基于这种方法改进后就是我们的二叉树。至于什么是二叉树，我们先开这里方法，慢慢我会给大家引出二叉树。  
    孩子兄弟表示法  
    这个方法我们在定义树中结点时有三个部分：  
    data数据域当然是必不可少的；  
    有两个指针域，一个是结点其中一个**孩子**指针，存储该结点第一个孩子的存储地址。  
    而另一个是它的**兄弟**结点的指针域，存储该节点右兄弟结点的存储地址。  
    ![在这里插入图片描述][2020122301464556.png]  
    下图是这种方法树的实现示意图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 9]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 10]  
这个方法非常的方便，我们找到结点时，就可以找到它的长子，而通过它的长子就可以找到它的兄弟，进而可以串联整个树。

当我们综合了链式两种方法思想，在对树加以约束，每个结点至多只允许有两个孩子，那么指针域只需要存储左孩子和右孩子。这个时候就有了二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 11]

# 二叉树 #

基于上面普通树的定义和特点特二叉树特点和定义如下：

*  二叉树特点定义

1.  每个结点最多有两个子树，既结点度不大于2；
2.  左树和右树是有有顺序的，位置不能颠倒；
3.  即使结点只有一颗子树，也到区别左树还是右树；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 12]  
    讲了二叉树的定义 具体二叉树存储方式、遍历方式、创建方式。以及它们通过Java语言实现方式。我写在了另外一篇博客里面。  
    [二叉树的构建以及遍历（Java语言描述）  
    ][Java_]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70]: /images/20221120/d8a6ca66ce5840bc8d498d418df9d8be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201221010212610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201221011543877.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/202012210116444.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201221011843692.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[-]: https://blog.csdn.net/qq_42411214/article/details/107445144
[Java_ArrayList]: https://blog.csdn.net/qq_42411214/article/details/107427621
[20201221152933462.png]: https://img-blog.csdnimg.cn/20201221152933462.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201221155651351.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201221155705268.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201221161321400.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[2020122302040155.png]: https://img-blog.csdnimg.cn/2020122302040155.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201223020619950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[2020122301464556.png]: https://img-blog.csdnimg.cn/2020122301464556.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201223015130328.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20201223014608683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20201223022119876.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20201223022810487.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDExMjE0,size_16,color_FFFFFF,t_70
[Java_]: https://blog.csdn.net/qq_42411214/article/details/108620209