二叉树

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

二叉树存储结构

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

ElementType tree[MAX_SIZE];

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

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

特殊的二叉树

Full Binary Tree
A
B
C
D
E
F
G
Complete Binary Tree
A
B
C
D
E
  • 满二叉树（Full Binary Tree）：
    • 每个节点要么没有子节点，要么有两个子节点。
    • 每一层都被完全填满。
    • 高度为 $h$ 的满二叉树节点数目为 $2^h - 1$。
  • 完全二叉树（Complete Binary Tree）：
    • 由满二叉树通过删除最后一层的一些节点而得到的。
    • 除了最后一层外，所有其他层都是完全填满的，而且最后一层的节点都集中在左侧。
    • 结点数量为 $n$ 的完全二叉树的高度为 $log_2^{}{(n+1)}$。

遍历方式

  • 前序：根左右
  • 中序：左根右
  • 后续：左右根
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // operation here
    preorderTraversal(root->left); // 遍历左子树
    preorderTraversal(root->right); // 遍历右子树
}
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    // operation here
    inorderTraversal(root->right); // 遍历右子树
}
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    inorderTraversal(root->right); // 遍历右子树
    // operation here
}
// 层次遍历二叉树
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);
        }
    }
}

线索二叉树

Threaded Binary Tree
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);
    }
}

常见操作

int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return max(getHeight(node->left), getHeight(node->right)) + 1;
}

二叉树构建

从前序、中序、后序序列中选两个构造二叉树

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

例子：

前序遍历为：ABDCE，中序遍历为：BDACE，树的结构如下：

    A
   / \
  B   C
   \   \
    D   E

我们如何从这两个遍历中恢复这棵树？

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

BST

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

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

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

  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. 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。