树结构 —— 二叉树的概述

比眉伴天荒 2023-07-11 15:14 54阅读 0赞

# 前文 #

[树结构概述][Link 1]

### 文章目录 ###

*  前文
 *  什么是二叉树？
 *   *  二叉树的定义
 *  满二叉树
 *   *  什么是满二叉树
     *  定义
 *  完全二叉树
 *   *  什么是完全二叉树？

# 什么是二叉树？ #

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒

## 二叉树的定义 ##

*  任何一个节点的子节点数量都不超过 2  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70]
 *  有左节点和右节点（不能随意颠倒）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 1]  
    左边树的左节点为 B，右节点为 C  
    右边数的左节点为 C，右节点为 B

# 满二叉树 #

## 什么是满二叉树 ##

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树

在上面那幅图的基础上加多一个节点，那么这棵树就变成满二叉树了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 2]

## 定义 ##

*  所有叶子节点都在最后一层
 *  节点的总数为： **2 的 n 次方 - 1（n 是树的高度）**

这怎么理解呢？比如上面这幅图有三层，所以 n 就等于 3，那么 2 的 3 次方 - 1 就是 7个节点，那么说明这就是一颗完全二叉树

# 完全二叉树 #

## 什么是完全二叉树？ ##

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从1至 n 的结点一一对应时称之为完全二叉树  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 3][]

这是一颗完全二叉树

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

这也是一颗完全二叉树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 5]

这也是一颗完全二叉树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 6]

这也是一颗完全二叉树

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

**这不是一颗完全二叉树**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 8]

这里为什么说不是完全二叉树？因为这图中最后一层左边并没有连续，直接从右边连续了，所以这并不是完全二叉树

通俗地来说完全二叉树的所有子节点都在最后一层或者倒数第二层，并且最后一层的叶子节点在左边连续（且左节点必须在前），倒数第二节点叶子节点在右边连续，依次按顺序能数完的才是完全二叉树

[Link 1]: https://blog.csdn.net/Woo_home/article/details/104693272
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306130200478.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200306130337120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200306130746311.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200306131726296.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200306131826653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200306131905401.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200306131929568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020030613205446.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200306132613778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70