二叉树

一、什么是二叉树？

1.1 二叉树的定义

• 由一系列节点组成的有限集合，每个节点都有且仅有 2 个子节点（空节点也算在内）
• 每个子节点构成一棵子树，并且子树之间没有交集

1.2 二叉树的结构

      1
   /     \                
  2       3              8
 / \     / \            /
4   5   6   7          9

    二叉树1            二叉树2

1.3 节点关系

• 父子节点：相连的节点之间存在父子关系，连接上面的节点是父节点，比如 2 是 4 和 5 的父节点
• 兄弟节点：同一个父节点的相邻节点，是兄弟节点，比如 4 和 5

  2      -- 父节点
 / \    
4   5    -- 子节点

1.4 节点类型

• 根节点：没有父节点的节点称为根节点，根节点在一棵树中只会有 1 个
• 内部节点：有非空子节点的节点，称为内部节点/分支节点，比如 1、2、3
• 叶子节点：仅有空子节点的节点，称为叶子节点，比如 4、5、6、7

      1             -- 根节点
   /     \                
  2       3         -- 分支节点
 / \     / \
4   5   6   7       -- 叶子节点

1.5 树的属性

• 节点高度：节点到叶子节点的最长路径
• 节点深度：根节点到节点的路径长度
• 节点层数：节点深度 + 1
• 树的高度：根节点的高度

    二叉树          高度      深度     层次

      1              2        0        1
   /     \ 
  2       3          1        1        2 
 / \     / \ 
4   5   6   7        0        2        3

1.6 节点属性

• 节点的度：节点的非空子树的数量

1的度数为2       4的度数为1       6的度数为0

   1                4               6
  / \              /
 2   3            5

二、常见的二叉树

2.1 满二叉树

满二叉树（Perfect Binary Tree），也称为完美二叉树:

• 除叶子节点外，所有节点都有 2 个非空子树
• 每一层的节点数量都是满的

比如说，这些二叉树都是满二叉树：

  3层满二叉树          2层满二叉树       1层满二叉树

      1
   /     \ 
  2       3                8             
 / \     / \              / \
4   5   6   7            9   10            11

满二叉树的性质：

• 第 k 层的节点数量为 2^(k-1)
• 树高度为 h，总节点数量为 2^(h+1) - 1
• 叶子节点数量 n0，和非叶子节点数量 n1，满足 n0 = n1 + 1
• 具有 n 个节点的满二叉树的深度为 log(n) 向下取整

2.2 完全二叉树

完全二叉树（Complete Binary Tree）：

• 除了最后一层节点没有满，其余层的节点都是满的
• 最后一层的节点是从左到右依次连续排序的

比如说，这些都是完全二叉树：

      1
   /     \ 
  2       3                8             
 / \     /                /
4   5   6                9    

完全二叉树的性质（如果节点按层次从左至右编写序号，起始序号1）：

• 父节序号为 i 时，左子节点序号为 2*i，右子节点序号为 2*i + 1
• 子节点序号为 i 时，父节点序号为 i/2

满二叉树实际上是完全二叉树的特例，即最后一层节点刚好填满，所以完全二叉树拥有的所有性质，满二叉树也都拥有。

2.3 完满二叉树

完满二叉树（full binary tree）：

• 除了叶节点之外，其余所有节点都有两个子节点
• 所有节点的度数都为 0 或 2

比如说，这些都是完满二叉树：

      1
   /     \ 
  2       3                4             
 / \                      / \
4   5                    5   7
   / \
  6   7

注意完满二叉树和其他二叉树的区别，完满二叉树仅保证每个节点的子节点数要么是 0，要么是 2。

三、为什么用二叉树？

二叉树在计算机科学和数据结构中有许多用途，其中一些主要原因包括：

• 高效的操作：二叉查找树可用于高效地搜索、插入和删除数据
• 排序：二叉查找树可用于数据的排序
• 分层数据表示：二叉树可以用于表示分层数据，如文件系统、组织结构等
• 递归操作：二叉树常用于递归算法，在图形处理、树形结构数据和许多其他领域都非常有用
• 数据编码：哈夫曼编码，在数据压缩上有重要作用
• …

二叉树是一种灵活且多用途的数据结构，可以在许多计算机科学和编程问题中提供高效的解决方案。

四、如何实现二叉树？

在实际应用中，可以使用两种主要的方法来存储二叉树：顺序存储和链式存储。

4.1 顺序存储法

顺序存储法是将二叉树存储在连续的内存块中，通常使用数组来表示二叉树的结构。

具体来说，顺序存储法是将二叉树的节点按照层次顺序从左到右依次存储在数组中。

其结构类似这样：

              30     
           /      \  
          28      16                          -- 逻辑结构
         /  \    /   
        18  22  12   
  
 ____ ____ ____ ____ ____ ____ 
| 30 | 28 | 16 | 18 | 22 | 12 |               -- 物理结构

这种方式对于完全二叉树尤其有效，因为完全二叉树的节点排列紧凑，不会浪费太多内存。

但是，对于一般的二叉树，顺序存储法会浪费大量的内存空间，比如这样的二叉树：

              30     
                  \  
                  16                          -- 逻辑结构
                 /   
                12   
  
 ____ ____ ____ ____ ____ ____ 
| 30 |    | 16 |    |    | 12 |               -- 物理结构

所以，对于一般二叉树来说，顺序存储法并不是那么合适，数组空间太浪费了。

优点：

• 内存利用率高：由于数据是连续存储的，没有指针等额外开销，内存利用率高。
• 快速随机访问：可以通过索引直接访问树的任意节点，时间复杂度为O(1)。
• 对缓存局部性友好：因为是连续存储的，对缓存友好，访问与遍历速度较快

缺点：

• 不适合数据量大的数：数组存储需要连续内存空间，数据量大时对内存的要求较高。
• 不适用于非完全二叉树：对于非完全二叉树，会浪费大量的内存空间。
• 插入和删除操作复杂：插入和删除节点时需要移动大量元素，效率较低。

4.2 链式存储法

链式存储法使用节点和指针来表示二叉树的结构，每个节点包含数据以及指向其左子树和右子树的指针。

其结构类似这样：

                     __ ____ __
                    |  | 30 |  |
                     /        \  
        __ ____ __                 __ ____ __
       |  | 28 |  |               |  | 16 |  |
        /        \                 /   
 __ ____ __   __ ____ __     __ ____ __
|  | 18 |  | |  | 22 |  |   |  | 12 |  |   

这种方式可以适用于任何类型的二叉树，无论是完全二叉树还是非完全二叉树。

优点：

• 适用性广泛：可以用于表示各种类型的二叉树，包括不规则的非完全二叉树。
• 插入和删除操作简单：插入和删除节点只需要调整指针，不需要移动大量数据。

缺点：

• 指针开销：每个节点需要额外的指针开销，占用更多内存。
• 随机访问较慢：由于需要依次遍历指针，随机访问节点的时间复杂度较高。

4.3 如何选择存储方法

选择二叉树的存储方法取决于应用的需求和数据特性：

• 如果数据是完全二叉树，并且对内存占用非常敏感，那么顺序存储法可能是个不错的选择。
• 如果需要处理各种类型的二叉树，链式存储法会更加灵活一些。

顺序存储法和链式存储法都有各自的优点和局限性，要根据具体情况进行权衡和选择。

参考

https://www.hello-algo.com/chapter_tree/binary_tree/

https://blog.csdn.net/weixin_57675461/article/details/121323091

http://c.biancheng.net/view/3384.html

https://blog.csdn.net/fadbgfnbxb/article/details/88701343

https://blog.csdn.net/yyz_1987/article/details/120766760