二叉树

Aristore2024-11-222024-11-22

1. 专业术语

在理解二叉树之前，我们首先需要熟悉一些专业术语，这些术语是构成二叉树的基础。以下是一些重要的概念：

1.1 节点 (Node)

定义：

二叉树中的每个元素叫做节点。节点存储数据，并且有两个指针，分别指向该节点的左右子节点。

介绍：

想象二叉树是一棵树，每个节点就是树上的一个 “点”，它保存数据并且通过 “枝条”（指针）与其他节点连接。

示例：

    A
   / \
  B   C
 / \
D   E

这里的 A、B、C、D 和 E 都是节点。

1.2 根节点 (Root Node)

定义：

根节点是二叉树的起始节点，所有的其他节点都通过根节点连接。树从根节点开始构建。

介绍：

根节点就像树的 “根部”，是树的起点，其他节点像是枝叶从根部伸展出去。

示例：

在上面的树结构中，A 是根节点。

1.3 父节点 (Parent Node) 和子节点 (Child Node)

定义：

父节点是指向子节点的节点。每个节点可以有一个或两个子节点。

介绍：

父节点就像是一个家长，子节点就是它的孩子。

示例：

在上面的树结构中，A 是 B 和 C 的父节点，B 是 D 和 E 的父节点。

1.4 叶节点 (Leaf Node)

定义：

没有任何子节点的节点称为叶节点。叶节点位于树的最底层。

介绍：

叶节点就像树的最顶端的小枝条，不能再继续分支。

示例：

在上面的树结构中，D 和 E 是叶节点。

1.5 高度 (Height) 和深度 (Depth)

深度 (Depth)：一个节点的深度是从根节点到该节点的路径长度。
高度 (Height)：一个节点的高度是从该节点到其最深叶节点的最长路径长度。

示例：

对于根节点 A，深度是 0。对于节点 B，它的深度是 1。对于叶节点 D，深度是 2。

2. 基本操作

在理解了二叉树的基础术语后，接下来介绍一些常见的二叉树基本操作，这些操作能帮助我们在编程中处理二叉树。

2.1 初始化

示例：假设当前树为

1
2
3

  5
 / \
3   8

代码：

# 初始化节点
n1 = TreeNode(value=5)
n2 = TreeNode(value=3)
n3 = TreeNode(value=8)
# 构建节点之间的引用（指针）
n1.left = n2
n1.right = n3

2.2 插入

示例：该二叉树中，在节点 n2 的左子树插入 4，树变为

代码：

1
2
3

n4 = TreeNode(value=4)
# 插入节点
n2.left = n4

2.3 删除

示例：该二叉树中，删除节点 n2 ，树变为

1
2
3

  5
 / \
4   8

代码：

1 2	# 删除节点n2，节点n1的左子树将变为n4 n1.left = n4

3. 二叉树的类型

3.1 完美二叉树 (Perfect Binary Tree)

定义：

完美二叉树是一种特殊的二叉树，它要求：

每一层的节点都满。
所有叶节点都在同一层。
每个节点都有两个子节点（除叶节点外）。

示例：

    A
   / \
  B   C
 / \ / \
D  E F  G

3.2 完全二叉树 (Complete Binary Tree)

定义：

完全二叉树是一种非常常见的二叉树类型。它要求：

除了最底层外，其他每一层的节点都是满的。
最底层的节点必须从左到右依次填充，且不一定是满的。

示例：

    A
   / \
  B   C
 / \  
D   E

3.3 完满二叉树 (Full Binary Tree)

定义：

完满二叉树是指：

每个节点要么没有子节点（即是叶节点），要么有两个子节点。

示例：

    A
   / \
  B   C
 / \
D   E
   / \
  F   G

3.4 平衡二叉树 (Balanced Binary Tree)

定义：

平衡二叉树的主要特点是它的左右子树的高度差不能超过一个固定的值（通常是 1），也就是说，二叉树中的任意节点，它的左右子树的高度差的绝对值不能超过 1。

高度平衡：

一个平衡二叉树通常要求：

任意节点的左子树和右子树的高度差不超过 1。

例如，如果一个节点的左子树高度为 3，右子树的高度为 2，那么该节点是平衡的。否则，如果左右子树的高度差超过 1，那么这个节点就不再是平衡的，可能需要进行 旋转操作 来恢复平衡。

常见的平衡二叉树类型

3.4.1 AVL 树 (AVL Tree)

定义：

AVL 树 是一种自平衡的二叉搜索树（BST）。它的特点是：对于每个节点，左子树和右子树的高度差（平衡因子）不超过 1。
通过插入和删除节点时进行旋转操作，保持树的平衡。

特性：

平衡因子：对于每个节点，平衡因子定义为该节点的左子树高度减去右子树高度的差值。AVL 树要求每个节点的平衡因子在 -1、0、1 之间。
- 如果某个节点的平衡因子大于 1，说明左子树太高，需要进行 右旋转。
- 如果某个节点的平衡因子小于 -1，说明右子树太高，需要进行 左旋转。

示例：

在这个树中，节点 20 的左子树高度为 1，右子树高度为 0，平衡因子是 1，符合 AVL 树的要求。旋转操作：

左旋转：当某个节点的右子树较高时，进行左旋转以恢复平衡。
右旋转：当某个节点的左子树较高时，进行右旋转以恢复平衡。

总结：

AVL 树通过旋转来确保树的平衡性，并且它的查找、插入和删除操作时间复杂度都能保持在 O(log n)。

3.4.2 红黑树 (Red-Black Tree)

定义：

红黑树 是一种自平衡的二叉查找树，其中每个节点都有一个颜色，红色或黑色。通过颜色的限制，红黑树保证了树的平衡性。

特性：

根节点是黑色。
每个叶子节点都是黑色的空节点（NIL 节点）。
红色节点的子节点必须是黑色的（即不能有两个连续的红色节点）。
从任何一个节点到其所有后代叶子节点的路径上，必须经过相同数量的黑色节点。
红黑树的查找、插入和删除操作的时间复杂度也为 O(log n)。

示例：

     10(B)
    /    \
  5(R)   20(R)
 /  \      \
2(B) 7(B)  30(B)

在这个例子中，红色节点（R）和黑色节点（B）交替，满足红黑树的各种约束。

总结：

红黑树通过一系列的颜色限制来保持平衡，插入和删除操作时可能会涉及 颜色变换 和 旋转操作，从而保持树的平衡。
它虽然没有 AVL 树严格，但由于旋转操作较少，效率较高，尤其是在插入和删除操作频繁的情况下。

3.5 二叉搜索树 (Binary Search Tree, BST)

定义：
二叉搜索树是一种特殊的二叉树，其中每个节点的左子树所有节点值都小于该节点值，右子树的节点值都大于该节点值。

示例：

4. 二叉树的退化

定义：

二叉树的退化是指二叉树变成链表的情况。在这种情况下，每个节点只有一个子节点。退化后的二叉树的性能和链表一样，查找、插入、删除操作的时间复杂度将变为 O (n)。

示例：

      A
     /
    B
   /
  C
 /
D

这个树就变成了一个链表，每个节点只有一个子节点。

退化的二叉树不再具有平衡性，性能大大下降。因此，在实际应用中，通常会使用自平衡的二叉树（如红黑树、AVL 树）来避免退化。