二叉树基础

简述：

1. 虽然二叉树本身作为基础数据结构并不是很难，但是很多更为复杂的数据结构都是基于二叉树的。例如：红黑树、多叉树、二叉堆、图、字典树、并查集、线段树等。
2. 二叉树不单纯是一种数据结构，更代表这递归的算法思想，比如回溯算法，BFS算法，动态规划。

二叉树常见类型：

1. 最普通的二叉树：

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

   • 父节点、子节点：每个节点下方直接相连的节点称为子节点，上方直接相连的节点称为父节点。
   • 根节点、叶节点：我们称没有父节点的节点1为根节点，最下层中无子节点的节点为根节点4、7、8。
   • 二叉树最大深度/高度：根节点到最下方叶节点经过的节点个数。
2. 满二叉树：每一层都是满的的二叉树。
   • 若满二叉树的深度为h，则二叉树的节点个数为: $2^h - 1$
3. 完全二叉树¹：二叉树的每一层节点都紧凑靠左排列，且除了最后一层，其他层都必须是满的。
   • 完全二叉树的左右子树也是完全二叉树，且至少有一棵是满二叉树。

4. 二叉搜索树：Binary Search Tree，简称BST，其左子树的每个节点的值都要小于该节点的值，与之对应，右子树的每个节点的值都要大于这个节点的值。

5. 高度平衡二叉树：其每个节点的左右子树的高度差都不小于1。
   • 假设平衡二叉树中共有N个节点，那么平衡二叉树的高度是O(log N)。如果能保证树的高度为O(log N)，那么这些数据结构的效率便会很高。反之，如果树的高度极不平衡，例如以下这种情况，则约等于退化为了单链表，效率大幅降低。

      1
        \
      2
      \
        3
          \
          4
            \
            5
     

6. 自平衡二叉树：最经典的为红黑树。

实现：

class TreeNode:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value
        
#可以这样构建一棵二叉树：
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)

# 构建出来的二叉树是这样的：
#     1
#    / \
#   2   3
#  /   / \
# 4   5   6

另外，在一般的算法题中，我们并不需要真正还原二叉树这一结构，而是可以将其抽象为二叉树结构，使用哈希表等数据结构来模拟二叉树。上面的二叉树可以使用如下所示的方法还原：

• 定义一个哈希表，其中键为父节点的ID，值为其子节点ID。 ```python

  1 -> [2, 3]

  2 -> [4]

  3 -> [5, 6]

tree = { 1: [2, 3], 2: [4], 3: [5, 6] } ``` 这样就可以模拟操作二叉树结构了，而该数据结构在后面提及图论时可以知道其名字为邻接表。

1. 我们说的完全二叉树对应英文 Complete Binary Tree，而满二叉树的定义对应英文的 Perfect Binary Tree，英文中的 Full Binary Tree 是指一棵二叉树的所有节点要么没有孩子节点，要么有两个孩子节点。 ↩︎