二叉树

重点内容，需熟练掌握多种二叉树的概念，在选择题中会考察，在大题中也可能出相关的概念题。

二叉树存储结构

  1. 链式存储结构：
    • 链式存储是最常见的二叉树存储方式。在链式存储中，每个节点都包含一个数据元素以及指向其左子树和右子树的指针。
    • 链式存储结构适用于表示任意形状和大小的二叉树，并且对于树的动态操作（插入、删除节点）非常方便。
  2. 顺序存储结构（数组表示）：
    • 顺序存储结构使用数组来表示二叉树。通常，数组的索引与二叉树的节点之间存在特定的关系，例如，对于索引 $i$ 的节点，其左子节点在索引 $2i+1$ 处，右子节点在索引 $2i+2$ 处，父节点在索引 $(i-1)$ / $2$ 处。
    • 顺序存储结构通常用于堆数据结构（如二叉堆）的实现，其中对于堆的性质要求，使得数组表示变得非常有效。

链接存储

在链接存储中，我们需要在结构体中定义两个指针，分别指向二叉树左边的结点和右边的结点。

typedef struct TreeNode {
    ElementType data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

顺序存储

顺序存储表示用数组存储一颗树，如下图所示。

14
4
34
18
8
22
7
53
实际二叉树结构
顺序存储结构
下标
元素
0
1
2
3
4
5
6
7
14
4
8
34
18
22
7
-1
8
9
10
11
-1
-1
-1
53

理解顺序存储的关键在于理解其 结点的隐式链接关系 以及 空指针的定义 这两点。

  • 在顺序存储中，结点的链接关系由其下标指定：
    • 数组的下标从 1 开始的话，如果当前结点的下标为 $i$，那么其左结点的下标为 $2i$，右结点的下标为 $2i + 1$。
    • 数组的下标从 0 开始的话，如果当前结点的下标为 $i$，那么其左结点的下标为 $2i + 1$，右结点的下标为 $2i + 2$。
  • 通常采用一个特殊值来表示空指针，上图中采用 -1 表示空指针。
#define MAX_SIZE 100

int tree[MAX_SIZE];

int lchild(int index) {
    return tree[2 * i + 1];
})

int rchild(int index) {
    return tree[2 * i + 2];
}

顺序存储最常见于 堆排序 中。

特殊二叉树

特殊的二叉树包含满二叉树、完全二叉树两种。

简单来说，满二叉树必须每一层结点数都是满的， 完全二叉树允许最后一层的最后几个结点为空。

满二叉树
A
B
C
D
E
F
G
完全二叉树
A
B
C
D
E

满二叉树

满二叉树（Full Binary Tree）具备如下特点：

  • 每个节点要么没有子节点，要么有两个子节点。
  • 每一层都被完全填满。
  • 第 $n$ 层的结点数量为 $2^n$。
  • 高度为 $h$ 的满二叉树节点数目为 $2^{h+1} - 1$。

完全二叉树

完全二叉树（Complete Binary Tree）具备如下特点：

  • 由满二叉树通过删除最后一层的一些节点而得到的。
  • 除了最后一层外，所有其他层都是完全填满的，而且最后一层的节点都集中在左侧。
  • 高度为 h 的完全二叉树的结点数量范围为 [$2^{h}$, $2^{h+1} - 1$]
  • 结点数量为 $n$ 的完全二叉树的高度为 $log_2^{}{(n+1)}$。

遍历方式

DFS

深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法。

当使用 DFS 遍历二叉树中的结点时，算法会优先探索树的深度，直到达到最深的节点。 当达到叶子节点或无法继续深入时，算法会回溯返回到上一个节点，探索其他分支。

二叉树的深度优先（DFS）遍历方式包含前序、中序、后序遍历三种。 理解这三种遍历方式的关键在于理解其递归过程，不同方式的递归顺序不一样。 具体不同点如下表所示：

访问方式递归顺序
前序根左右
中序左根右
后序左右根
前序遍历
1
2
3
4
5
8
6
7
9
10
1
2
3
4
5
6
7
8
9
10
前序遍历序列 = [1, 2, 4, 5, 8, 3, 6, 7, 9, 10]
  • 访问顺序： 根节点 -> 左子树 -> 右子树
  • 步骤：
    1. 访问根节点。
    2. 递归地进行前序遍历左子树。
    3. 递归地进行前序遍历右子树。
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // operation here
    preorderTraversal(root->left); // 遍历左子树
    preorderTraversal(root->right); // 遍历右子树
}
中序遍历
1
2
3
4
5
8
6
7
9
10
5
2
1
4
3
5
6
9
8
10
中序遍历序列 = [4, 2, 8, 5, 1, 6, 3, 9, 7, 10]
  • 访问顺序： 左子树 -> 根节点 -> 右子树
  • 步骤：
    1. 递归地进行中序遍历左子树。
    2. 访问根节点。
    3. 递归地进行中序遍历右子树。
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    // operation here
    inorderTraversal(root->right); // 遍历右子树
}
后序遍历
1
2
3
4
5
8
6
7
9
10
10
4
1
3
2
9
5
8
6
7
后序遍历序列 = [4, 8, 5, 2, 6, 9, 10, 7, 3, 1]
  • 访问顺序： 左子树 -> 右子树 -> 根节点
  • 步骤：
    1. 递归地进行后序遍历左子树。
    2. 递归地进行后序遍历右子树。
    3. 访问根节点。
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    inorderTraversal(root->right); // 遍历右子树
    // operation here
}

BFS

1
2
3
4
5
8
6
7
9
10
1
2
4
5
8
3
6
7
9
10
层次遍历序列 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

二叉树的层次遍历（Level Order Traversal），也称为广度优先搜索（Breadth-First Search，BFS），是一种从上到下、从左到右逐层访问二叉树节点的方法。

BFS 算法从根节点开始，逐层访问节点。同一层级的节点按照从左到右的顺序访问。

void levelOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct Queue* queue = createQueue();
    enqueue(queue, root);

    while (queue->front != NULL) {
        struct TreeNode* current = dequeue(queue);
        // operation here

        if (current->left != NULL) {
            enqueue(queue, current->left);
        }

        if (current->right != NULL) {
            enqueue(queue, current->right);
        }
    }
}

线索二叉树

后继线索
A
B
C
D
E
F
G
H
I
前驱线索

线索二叉树（Threaded Binary Tree）是一种对普通二叉树进行优化的数据结构。它的主要目的是在二叉树上添加一些线索（thread），使得在遍历树的过程中可以更加高效地找到前驱和后继节点。线索二叉树在某些应用中能够提高对树的遍历性能，尤其是中序遍历。

线索二叉树中的每个节点都可以包含以下线索信息：

  • 前驱线索（Inorder Predecessor Thread）： 如果节点有左子树为空，那么它的左子树指针可以指向其前驱节点，即在中序遍历中位于它之前的节点。
  • 后继线索（Inorder Successor Thread）： 如果节点有右子树为空，那么它的右子树指针可以指向其后继节点，即在中序遍历中位于它之后的节点。

线索二叉树的主要优点是，在不使用递归或栈的情况下，可以通过线索信息直接找到下一个要访问的节点，从而提高了中序遍历的效率。这对于需要频繁进行中序遍历的应用非常有用，例如数据库中的 B 树和 AVL 树的实现。

// ltag = 0 时表示 lchild 域指向节点的左孩子，ltag = 1 时表示 lchild 域指向节点的前驱
// rtag = 0 时表示 rchild 域指向节点的右孩子，rtag = 1 时表示 rchild 域指向节点的后继
typedef struct ThreadNode {
    ElementType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode;
// 中序遍历，找到中序遍历的第一个节点，然后遍历 rchild 即可
void InOrder(ThreadNode *n) {
    ThreadNode *p = n;
    while (p->lchild) {
        p = p->lchild;
    }
    for (; p != NULL; p = p->rchild) {
        visit(p);
    }
}

二叉树构建

已知二叉树，可以获得其前序、中序和后序遍历序列。

反之，给定二叉树的遍历序列，可以通过以下两种方式重建其二叉树结构：

  1. 带空指针的单序列重建：给定包含空指针信息的单一遍历序列（如带空指针的前序遍历），可以唯一确定二叉树的结构。
  2. 双序列组合重建：给定两种不同的遍历序列组合，可以唯一确定二叉树的结构。

带空指针的单序列

在二叉树的遍历序列中，明确地标记出空节点（通常用特定的符号，如“#”或“NULL”表示），可以使得单一的遍历序列足以唯一确定二叉树的结构。

常规的前序、中序或后序遍历，如果二叉树中存在空节点，则这些空节点的信息会丢失。 因此，单一的常规遍历序列无法区分某些二叉树的结构。

假设有如下二叉树：

     1
    / \
  2    3
 / \   /
4   # #

那么他的带空指针的前序遍历序列为：1 2 4 # # # 3 # #

重建步骤如下：

  1. 从序列的第一个元素开始，创建根节点。
  2. 读取下一个元素，如果不是空节点，则创建当前节点的左子节点，并递归地处理左子树。
  3. 如果遇到空节点，则表示当前子树为空，返回。
  4. 处理完左子树后，读取下一个元素，创建当前节点的右子节点，并递归地处理右子树。
  5. 重复上述步骤，直到序列结束。

上述过程的 C 代码实现如下所示：

TreeNode *createTree(char a[], int *i) {
    if (a[i] == '#') {
        return NULL;
    }
    TreeNode *cur = new TreeNode(a[i]);
    *i = *i + 1;
    cur->left = createTree(a, i);
    cur->right = createTree(a, i);
}

双序列组合重建

从前序、中序、后序序列中选两个构造二叉树，有两种方式：

  1. 前序 + 中序：这是最常见的组合，因为前序确定了根节点的位置，而中序则可以区分哪些节点在左子树，哪些在右子树。有了这两个信息，就可以唯一确定一棵二叉树。
  2. 后序 + 中序：后序确定了根节点的位置（它是后序遍历的最后一个节点），而中序同样可以帮助我们区分左、右子树。因此，这两者也可以唯一确定一棵二叉树。

重点在于选取的两种遍历方式可以提供关于这颗二叉树的结构信息，以 前序 和 中序 为例：

A
B
D
C
E
前序遍历：
B
D
A
C
E
中序遍历：
根左右
左根右
可以确定是根节点
B、D 在 A 的左边
C、E 在 A 的右边
A
B、D
C、E

如上图所示，给定起始序列，可以判断先序序列中的第一个元素 A 是树的根结点。 再根据中序序列，可以判断 B、D 在 A 的左子树中，C、E 在 A 的右子树中。

由此我们就得到了二叉树的一部分结构，再继续递归地对 A 的左子树和右子树重复如上过程，即可得到完整的二叉树结构。

注意

前序和后序遍历是不足以唯一确定一个二叉树的。原因是前序和后序遍历本身不足以提供足够的信息来唯一确定一个树的结构。

从三种遍历中选取两种时一定要有中序遍历，才能得到完整的二叉树结构。

上述例子的具体重建过程如下：

  • 前序遍历的第一个元素 A 是根节点。
  • 在中序遍历中， A 将序列分为两部分： BD 和 CE 。左边部分 BD 对应于左子树，右边部分 CE 对应于右子树。
  • 在前序遍历中，继 A 之后的 BD 对应于左子树，而 CE 对应于右子树。
  • 对于左子树，其前序遍历为 BD ，中序遍历为 BD 。从这可以确定 B 是左子树的根，而 D 是它的右孩子。
  • 对于右子树，其前序遍历为 CE ，中序遍历为 CE 。从这可以确定 C 是右子树的根，而 E 是它的右孩子。

重建后可以得到二叉树结构：

    A
   / \
  B   C
   \   \
    D   E

BST

二叉排序树，也称为二叉查找树（Binary Search Tree, BST），是一种特殊的二叉树。它或者是一棵空树，或者是满足以下性质的二叉树：

  1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  3. 它的左、右子树也分别为二叉排序树。
8
3
10
1
6
4
7
14
13

二叉查找树的 主要操作 有：

  1. 插入：从根节点开始，如果待插入的值小于当前节点的值，就将其插入到左子树中，否则插入到右子树中。
  2. 查找：从根节点开始，如果待查找的值小于当前节点的值，就在左子树中查找，否则在右子树中查找。
  3. 删除：有三种情况：
    • 如果是叶子节点，直接删除。
    • 如果只有一个子节点，删除它并将其子节点连接到它的父节点。
    • 如果有两个子节点，找到其右子树的最小值或左子树的最大值来替换该节点，然后删除那个节点。
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* newNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
// 插入新节点
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}
// 查找节点
TreeNode* search(TreeNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    }
    return search(root->right, data);
}
// 删除节点
TreeNode* deleteNode(TreeNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // 节点有一个或没有子节点
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        // 节点有两个子节点，找到右子树的最小节点
        TreeNode* temp = findMin(root->right);

        // 复制右子树的最小节点的值
        root->data = temp->data;

        // 删除右子树的最小节点
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

AVL

平衡二叉树（Balanced Binary Tree），也叫做 AVL 树。它的特点是任意节点的左右子树高度差（平衡因子）不超过 1，这确保了树的高度始终保持在 $O(log_2 n)$ 的水平，使得查找、插入和删除操作的时间复杂度都保持在 $O(log_2 n)$。

理解 AVL 的关键在于理解 AVL 的旋转过程，以下针对几个疑问带大家迅速了解关键知识：

  1. 为什么需要旋转？

我们时常需要对 AVL 中的结点进行插入和删除操作，这些操作可能导致 AVL 中的某个子树进入不平衡的状态。 通过旋转操作可以使得不平衡的子树 和 整棵 AVL 树 都变得重新平衡。

  1. 从哪个节点开始旋转？

从最小不平衡子树的根节点旋转，旋转操作会使得最小不平衡子树从不平衡变得平衡。

理解这句话你需要掌握以下概念：

  • 平衡因子：每个节点的平衡因子是其左子树的高度减去右子树的高度
  • 最小不平衡子树：最小不平衡子树是指在整棵二叉树中，高度差（平衡因子的绝对值）最小的子树，该子树的平衡因子绝对值超过 1，即它是导致整棵树不平衡的最小子树。
  1. 如何旋转？

执行插入操作时，如果该次插入使得 AVL 不平衡的话，首先找到最小不平衡子树根节点（用 A 表示该节点）的位置，然后根据插入节点（用 N 表示）相对于 A 的位置，可能有四种不同的旋转操作：

  1. LL，N 在 A 的左子树的左子树中（A 的平衡因子 +2，A 的左子树根节点平衡因子 +1）：A 右旋
  2. RR，N 在 A 的右子树的右子树中（A 的平衡因子 -2，A 的右子树根节点平衡因子 -1）：A 左旋
  3. LR，N 在 A 的左子树的右子树中（A 的平衡因子 +2，A 的左子树根节点平衡因子 -1）：A 的左子树左旋，然后 A 右旋
  4. RL，N 在 A 的右子树的左子树中（A 的平衡因子 -2，A 的右子树根节点平衡因子 +1）：A 的右子树右旋，然后 A 左旋
A
B
(+1)
(0)
BL
BR
AR
h
A
B
(+2)
(+1)
BL
BR
AR
h
h+1
X
X
Insert X into BL
LL Rotation
B
A
BR
AR
BL
h+1
X
h
h
h
(0)
(0)
A
B
(-1)
(0)
BL
BR
AL
h
h
Insert X into BR
A
B
(-2)
(-1)
BL
BR
AL
h
X
h
h+1
RR Rotation
B
A
AL
BL
h
(0)
(0)
BR
X
h+1
A
B
C
BL
CL
CR
(0)
(+1)
(0)
h
h-1
h
AR
Insert X into CR
A
B
C
BL
CL
CR
(-1)
(+2)
(-1)
h
h-1
h
AR
X
h
LR Rotation
C
A
B
BL
h
CL
CR
X
h
h
AR
h-1
(0)
(+1)
A
B
C
CL
CR
(0)
h-1
BR
h
h
(0)
(-1)
Insert X into CR
AL
A
B
C
CL
CR
(-1)
h-1
BR
h
(-2)
AL
X
h
RL Rotation
C
A
B
BR
h
CR
X
h
h
AL
CL
h-1
(+1)
(+1)
LL Rotation
RR Rotation
LR Rotation
RL Rotation
(0)
(0)
(0)

AVL 平衡旋转的代码实现如下所示，过程比较繁琐，了解即可，重点在与如何掌握如何 “人脑” 模拟旋转过程。

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    int height; // 节点高度
};
struct TreeNode* leftRotate(struct TreeNode* x) {
    struct TreeNode* y = x->right;
    struct TreeNode* T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;
}
struct TreeNode* rightRotate(struct TreeNode* y) {
    struct TreeNode* x = y->left;
    struct TreeNode* T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;
}
// 计算以 node 为根节点的子树高度
int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 获取平衡因子
int getBalanceFactor(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}
// 在插入时需要使用该操作，重新计算子树高度
void updateHeight(struct TreeNode* node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
struct TreeNode* insert(struct TreeNode* node, int data) {
    // 步骤 1：执行标准 BST 插入
    if (node == NULL) {
        return createNode(data);
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else { // 如果键值相等，则不插入
        return node;
    }

    // 步骤 2：更新节点的高度
    updateHeight(node);

    // 步骤 3：获取节点的平衡因子
    int balanceFactor = getBalanceFactor(node);

    // 步骤 4：平衡调：根据新插入结点的位置 相对于 最小不平衡子树根节点的位置进行旋转
    // LL 型：右旋
    if (balanceFactor > 1 && data < node->left->data) {
        return rightRotate(node);
    }
    // RR 型：左旋
    if (balanceFactor < -1 && data > node->right->data) {
        return leftRotate(node);
    }
    // LR 型：先左旋，再右旋
    if (balanceFactor > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RL 型：先右旋，再左旋
    if (balanceFactor < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 返回未被修改的节点指针
    return node;
}

红黑树

为了保证 AVL 的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构，代价很大。为此在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构。

Red-black_tree_example_with_NIL

红黑树的考察不会很深，了解以下概念即可：

  1. 从根结点到叶结点的最长路径不大于最短路径的 2 倍。
  2. 根节点和叶结点是黑色的。
  3. 不存在两个相邻的红结点。
  4. 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。