《恋上数据结构与算法》笔记（七）：二叉树

青旅半醒 2023-02-11 04:46 19阅读 0赞

## 目录 ##

*  一、树（Tree）的基本概念
    
     *  1、节点
     *  2、子树
     *  3、度
     *  4、深度&高度
     *  5、树的分类
 *  二、二叉树
    
     *  1、二叉树的性质
     *  2、二叉树的种类
        
         *  a、真二叉树
         *  b、满二叉树
         *  c、完全二叉树
 *  三、leetcode算法题
    
     *  1、寻找完全二叉树的叶子节点

--------------------

# 一、树（Tree）的基本概念 #

跳转到目录

*  节点最多为两个的树叫做`二叉树`, 节点多余两个的树叫做多叉树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]
 *  生活中的树形结构  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

### 1、节点 ###

跳转到目录  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

*  **节点**：`1`、`2`、`3`、`4`、`5`、`6`、`21`、`22`、`31`、`51`、`52`、`61`、`221`、`222`、`223`
 *  **根节点**：`1`
 *  **父节点**：`1`是`2`、`3`、`4`、`5`、`6`的父节点，`2`是`21`、`22`的父节点，以此类推。
 *  **子节点**：与父节点相反，2、3、4、5、6是1的子节点，21、22是2的子节点，以此类推。
 *  **兄弟节点**：同一个父节点下的子节点互为兄弟节点，例如上图中的`21`和`22`是兄弟节点，但是`22`和`31`虽然都在同一层，而父节点不同，所以不是兄弟节点。
 *  **空树**：一棵树没有任何节点，包括没有根节点。
 *  一棵树可以只有一个节点，也就是根节点。

### 2、子树 ###

跳转到目录

*  **子树**：一棵树可以有很多节点，而其中除了整体是一颗树外，其中的子节点也可以单独看成一棵树，例如`2`、`21`、`22`、`221`、`222`、`223`就是一颗子树。
 *  **左子树**：左侧的子节点称为`左子树`，例如21是2的左子树。
 *  **右子树**：右侧的子节点称为`右子树`，例如22是2的右子树。

### 3、度 ###

跳转到目录

*  节点的度：`子树的个数`，即子节点的个数，就是节点的度，例如根节点`1`有`5`个子节点，所以根节点`1`的度是`5`。
 *  树的度：所有节点度的`最大值`，上图中节点度最大的是`根节点`， 所以这棵树的度是`5`。
 *  叶子节点：度为`0`的节点，即没有子节点的节点。
 *  非叶子节点：度`不为0`的节点，即有子节点的节点。

### 4、深度&高度 ###

跳转到目录

*  层数：根节点第一层，根节点的子节点在第`2`层，以此类推(有些教程是从第0层开始计算)。
 *  节点的深度：**`从根节点到当前节点的唯一路径上的节点总数。`**
    
     *  节点`2`的深度：1->2，经历2个节点，所以深度为`2`。
     *  节点`223`的深度：1->2->22->223，经历4个节点，所以深度是`4`。
 *  节点的高度：**`从当前节点到最远叶子节点的路径上的节点总数。`**
    
     *  节点2的高度：2->22->221，经历`3`个节点，所以深度是`3`
     *  节点223的深度: 223，只有一个节点，所以深度是`1`。
 *  树的深度：所有节点`深度`的`最大值`。
    
     *  1->2->22->221，所以树的深度是`4`。
 *  树的高度：所有节点`高度`的`最大值`。
    
     *  1->2->22->221，所以树的高度是`4`。

### 5、树的分类 ###

跳转到目录

*  **有序树**：树中任意节点的子节点之间有顺序关系，即两个树所有的值都一样，但是其中的子节点顺序不一样，就是两颗不同的`有序树`。
 *  **无序树**：树中任意节点的子节点之间没有顺序关系，也称为`自由树`。
 *  **森林**：由m（m >= 0）颗互不相交的`树组成的集合`。

# 二、二叉树 #

跳转到目录

### 1、二叉树的性质 ###

跳转到目录

*  每个节点的`度`最大为`2`，即最多拥有`2颗子树`。
 *  左子树和右子树是有顺序的，比如所有节点左子树小于右子树。
 *  即使某节点只有一颗子树，也要区分左右子树  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]
 *  非空二叉树的第`i`层，最多有`2^(i-1)`个节点(i >= 1)。
 *  高度为`h`的二叉树最多有`2^h - 1`个节点(h >= 1)。
 *  对于任意一颗非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有：`n0 = n2 + 1`。
    
     *  假设度为1 的节点个数为n1，那么二叉树的总结点`n = n0 + n1 + n2`  
        二叉树的边数T = n1 + 2 \* n2，这是因为n1的每个节点下有1个子节点，所以边是n1，n2的每一个节点都有2个子节点所以是n2 \* 2。反过来看，因为所有的节点上面都有一条边，只有根节点上没有边。所以，二叉树的边数T = n1 + 2 \* n2 = n - 1 = n0 + n1 + n2 - 1。即: n1 + 2 \* n2 = n0 + n1 + n2 - 1 可以推出`n0 = n2 + 1`。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]

### 2、二叉树的种类 ###

跳转到目录

##### a、真二叉树 #####

跳转到目录

*  所有节点的度要么为`0`，要么为`2`，即没有只有一个子节点的节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 5]

##### b、满二叉树 #####

跳转到目录

*  所有节点的度要么为`0`，要么为`2`。且所有的`叶子节点`都在最后一层。
 *  在同样高度的二叉树中，满二叉树的叶子节点数量`最多`，总结点数量最多。
 *  满二叉树一定是真二叉树，真二叉树不一定是满二叉树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 6]
 *  假设满二叉树的高度为`h`(h >= 1)，那么：
    
     *  第i层的节点数量：`2^(i - 1)`
     *  叶子节点数量：`2^h - 1`
     *  总结点数量 `n`：
        
         *  n = `2^h - 1 = 2^0 + 2^1 + 2^2 + 2^3 +...+ h^(h - 1)`
         *  h = `log2(n + 1)`

##### c、完全二叉树 #####

跳转到目录

*  叶子节点只会出现最后2层，最后1层的叶子节点都`靠左对齐`(只能缺少右子树)。
 *  完全二叉树从`根节点至倒数第2层`是一颗满二叉树。
 *  满二叉树一定是`完全二叉树`，完全二叉树`不一定`是满二叉树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 7]
 *  度为`1`的节点只有左子树。
 *  度为`1`的节点要么是1个，要么是0个。
 *  同样节点数量的二叉树，完全二叉树的高度最小。
 *  假设完全二叉树的高度为h(h >= 1)，那么：
    
     *  至少有2^(h - 1)个节点(2^0 + 2^1 + 2^2 + … + 2^(h - 2) + 1)。
     *  最多有2^h - 1个节点(2^0 + 2^1 + 2^2 + … + 2^(h - 1), 满二叉树)。
     *  总节点数量为 n：
        
         *  2^(h - 1) <= n < 2^h
         *  h - 1 <= log2(n) < h
         *  h = floor(log2n) + 1
 *  一个有n个节点的完整二叉树(n > 0)，从上到下，从左到右对节点从1开始编号，对任意第i个节点：
    
     *  如果i = 1，它是根节点。
     *  如果i > 1，它的父节点编号为floor(i/2)。
     *  如果2i <= n，它的左子节点编号为2i。
     *  如果2i > n，它无左子点。
     *  如果2i + 1 <= n，他的右子节点编号为2i + 1。
     *  如果2i + 1 > n，它无右子节点。
 *  一个有n个节点的完整二叉树(n > 0), 从上到下，从左到右对节点从0开始编号, 对任意第i个节点：
    
     *  如果i = 0，它是根节点。
     *  如果i > 0，它的父节点编号为floor((i- 1)/2)。
     *  如果2i + 1 <= n - 1，它的左子节点编号为2i + 1。
     *  如果2i + 1 > n - 1，它无左子点。
     *  如果2i + 2 <= n - 1，他的右子节点编号为2i + 2。
     *  如果2i + 2 > n - 1，它无右子节点。

# 三、leetcode算法题 #

跳转到目录

### 1、寻找完全二叉树的叶子节点 ###

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

*  `总节点`数量为`n`。
 *  n如果是`偶数`，叶子节点数量`n0 = n / 2`。
 *  n如果是`奇数`，叶子节点数量`n0 = (n + 1) / 2`。
 *  可以一并写成：`n0 = floor((n + 1) / 2)`。
 *  `floor为向下取整`。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521212258978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052121232655.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521212135559.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200521213555258.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200521213932854.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200521214137644.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200521214225421.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200521214658305.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200521215052811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70