二叉树

二叉树性质规则

设 n0,n1,n2 分别为度 0、1、2 结点数，则 n0=n2+1；第 h 层最多 2^(h-1) 个结点，树高为 h 时最多 2^h-1 个。满二叉树达到上界；完全二叉树除最后层外全满且最后层靠左，满足 2^(h-1)≤n≤2^h-1。0 基编号下标为 2i+1,2i+2，1 基为 2i,2i+1。

二叉树存储规则

顺序存储按层编号：0 基父子为 left=2i+1,right=2i+2,parent=floor((i-1)/2)；1 基为 left=2i,right=2i+1,parent=floor(i/2)，访问须先做边界检查。链式存储每结点含左右孩子指针；n 个结点有 2n 个指针域、树边 n-1，故有 n+1 个空链，仅针对非空二叉链树。

二叉树遍历规则

先序 NLR、中序 LNR、后序 LRN、层序按层从左到右。递归或显式栈可实现前三者，队列实现层序；空树立即返回。结点互异时，先序+中序或后序+中序可唯一重建；仅先序+后序通常不唯一（单孩子左右方向未知）。

线索二叉树规则

ltag=0/rtag=0 表示真实孩子，ltag=1/rtag=1 表示中序前驱/后继线索。线索域不可把线索当孩子；中序后继若 rtag=1 直接取 rchild，否则进入真实右子树再沿左孩子到底。线索遍历无需递归或栈，但必须尊重标签并处理首尾结点边界。

🔥 高优先级

树和图每年都是必考，这一节每个知识点都十分重要。

二叉树存储结构

1. 链式存储结构 ：

• 链式存储是最常见的二叉树存储方式。在链式存储中，每个节点都包含一个数据元素以及指向其左子树和右子树的指针。
• 链式存储结构适用于表示任意形状和大小的二叉树，并且对于树的动态操作（插入、删除节点）非常方便。

2. 顺序存储结构 （数组表示）：

• 顺序存储结构使用数组来表示二叉树。通常，数组的索引与二叉树的节点之间存在特定的关系，例如，对于索引 i 的节点，其左子节点在索引 2i+1 处，右子节点在索引 2i+2 处，父节点在索引 (i−1) / 2 处。
• 顺序存储结构通常用于堆数据结构（如二叉堆）的实现，其中对于堆的性质要求，使得数组表示变得非常有效。

链接存储

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

typedef struct TreeNode {
```c
ElementType data;
struct TreeNode* left;
struct TreeNode* right;

} TreeNode

#### 顺序存储

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


![](/cc408/images/docs/data-structure/942e7c4d8d.svg)

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

  * 在顺序存储中，结点的链接关系由其下标指定：
* 数组的下标从 1 开始的话，如果当前结点的下标为 i ，那么其左结点的下标为 2i ，右结点的下标为 2i+1 。
* 数组的下标从 0 开始的话，如果当前结点的下标为 i ，那么其左结点的下标为 2i+1 ，右结点的下标为 2i+2 。



  * 通常采用一个特殊值来表示空指针，上图中采用 -1 表示空指针。

```c
```c
#define MAX_SIZE 100

int tree[MAX_SIZE];

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

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

顺序存储最常见于 [堆排序](/docs/data-structure/ch07-sort/internal-sort/#%e5%a0%86%e6%8e%92%e5%ba%8f) 中。因为 **堆是一棵完全二叉树** 。

  * 对完全二叉树而言，顺序存储不会造成空间浪费；
  * 父结点与子结点之间的关系可以直接通过下标计算得到（无需额外指针）；
  * 堆排序过程中需要频繁地比较和交换父结点与子结点，数组下标运算能显著提升效率。

因此，堆排序天然适合采用顺序存储结构来实现。

### 特殊二叉树

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

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


![](/cc408/images/docs/data-structure/cc432ff6c1.svg)

#### 满二叉树

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

  * 每个节点要么没有子节点，要么有两个子节点。
  * 每一层都被完全填满。
  * 第 k 层的结点数量为 2^k（这里假设根结点是第 0 层）。
  * [高度](/docs/data-structure/ch04-tree/tree/#%e9%ab%98%e5%ba%a6) 为 h（根为第 1 层）的满二叉树节点数目为 2^h−1。
  * 结点数量为 n 的满二叉树的高度为 log2​\(n+1\) 。

#### 完全二叉树

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

  * 由满二叉树通过删除最后一层的一些节点而得到的。
  * 除了最后一层外，所有其他层都是完全填满的，而且最后一层的节点都集中在左侧。
  * [高度](/docs/data-structure/ch04-tree/tree/#%e9%ab%98%e5%ba%a6) 为 h（根为第 1 层）的完全二叉树结点数满足 2^(h−1) ≤ n ≤ 2^h−1。
  * 结点数量为 n 的完全二叉树的高度为 ⌈log2​\(n+1\)⌉ 。

### 遍历方式

#### DFS

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

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


![](/cc408/images/docs/data-structure/image-20260612100626281.png)

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

访问方式| 递归顺序  
---|---  
前序| 根左右（NLR）  
中序| 左根右（LNR）  
后序| 左右根（LRN）  

补充

在表述递归顺序时，通常用 N 表示根节点，L 表示左孩子，R 表示右孩子。

##### 前序遍历

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

  * 访问顺序：根节点 -> 左子树 -> 右子树
  * 步骤：
1. 访问根节点。
2. 递归地进行前序遍历左子树。
3. 递归地进行前序遍历右子树。




```c
![](/cc408/images/docs/data-structure/image-20260612101748942.png)

    void preorderTraversal(struct TreeNode* root) {
        if (root == NULL) {
            return;
        }
        // operation here
        preorderTraversal(root->left); // 遍历左子树
        preorderTraversal(root->right); // 遍历右子树
    }

中序遍历

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

• 访问顺序：左子树 -> 根节点 -> 右子树

• 步骤：

1. 递归地进行中序遍历左子树。
2. 访问根节点。
3. 递归地进行中序遍历右子树。

![](/cc408/images/docs/data-structure/image-20260612101815059.png)

```c
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    // operation here
    inorderTraversal(root->right); // 遍历右子树
}

##### 后序遍历

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

  * 访问顺序：左子树 -> 右子树 -> 根节点
  * 步骤：
1. 递归地进行后序遍历左子树。
2. 递归地进行后序遍历右子树。
3. 访问根节点。




```c
![](/cc408/images/docs/data-structure/image-20260612101835603.png)

    void postorderTraversal(struct TreeNode* root) {
        if (root == NULL) {
            return;
        }
        postorderTraversal(root->left); // 遍历左子树
        postorderTraversal(root->right); // 遍历右子树
        // operation here
    }

BFS

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

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

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

void levelOrderTraversal(struct TreeNode* root) {
```c
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);
    }
}

}

### 线索二叉树


![](/cc408/images/docs/data-structure/image-20260612101929222.png)

**线索二叉树** （Threaded Binary Tree）是一种为了提高二叉树遍历效率而设计的数据结构。它通过利用二叉树中原本为空的指针域来存储指向前驱或后继结点的指针（称为“线索”），从而省去递归或栈的遍历方式。

[普通二叉树](/docs/data-structure/ch04-tree/tree/#%e9%93%be%e6%8e%a5%e5%ad%98%e5%82%a8) 的结点有两个指针：`left` 和 `right`，但在一棵 `n` 个结点的二叉树中，实际的左右子树为空的指针数有很多（约 `2n` 个）。线索二叉树的思想就是把 **这些空指针利用起来** ，指向结点在某种遍历序列中的前驱或后继。

#### 数据结构

  * 节点存储结构

```c
// ltag = 1 时表示 lchild 域指向节点的前驱
// rtag = 1 时表示 rchild 域指向节点的后继
typedef struct ThreadNode {
```c
ElementType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;

} ThreadNode;

  * 遍历

TODO


// 以中序线索二叉树为例
// 中序遍历，找到中序遍历的第一个节点，然后遍历 rchild 即可
void InOrder(ThreadNode *n) {
```c
ThreadNode *p = n;
while (p->lchild) {
    p = p->lchild;
}
for (; p != NULL; p = p->rchild) {
    visit(p);
}

}

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

• 前驱线索

• 如果 p 的左子指针 left 原本为空，那么将其改为指向 p 的“遍历前驱结点”。

• 同时 ltag = 1，表示这个指针是线索，而不是左孩子。

  • 后继线索

• 如果 p 的右子指针 right 原本为空，那么将其改为指向 p 的“遍历后继结点”。

• 同时 rtag = 1，表示这个指针是线索，而不是右孩子。

类型

📌 按不同的遍历方式，线索可分为：

在实际应用中，最广泛使用的是 中序线索二叉树 。因为通过中序线索，可以用如下方式访问整棵树：

1. 从最左下角的结点开始
2. 通过右线索一步步访问中序后继
3. 直到结束，不需要递归或辅助栈

这种遍历方法最简单、最直接。

二叉树构建

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

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

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

带空指针的单序列

在二叉树的遍历序列中，明确标记空节点 （例如用 # 或 NULL），可以保证仅通过 一个前序遍历序列 就能唯一确定一棵二叉树的结构。

如果只用常规的前序、中序或后序遍历而不标记空节点，那么遇到某些情况时会出现歧义。例如，一棵根节点为 1 的树，如果它只有一个左孩子或只有一个右孩子，两种情况的普通前序序列都是 1 X，无法区分。

但是如果在遍历时显式地写出空指针（#），序列就变得 无歧义 。

举个例子，对于以上二叉树，我们可以使用以下方法构建二叉树：

1. 从序列的第一个元素开始：

• 如果是 #，说明该子树为空，返回 NULL。
• 否则，创建一个新节点作为当前子树的根。

2. 递归处理下一个元素：

• 按前序规则，先为当前节点构建 左子树 。
• 如果遇到 #，左子树为空，返回。

3. 再递归处理下一个元素：

• 构建 右子树 。
• 如果遇到 #，右子树为空，返回。

4. 重复步骤 1–3，直到序列完全读完。

​

TreeNode* createTree(char a[], int *i) {
```c
if (a[*i] == '#') {   // 空指针标记
    (*i)++;           // 别忘了推进下标
    return NULL;
}
// 创建当前节点
TreeNode *cur = (TreeNode*)malloc(sizeof(TreeNode));
cur->val = a[*i];
(*i)++;               // 消费当前字符

// 按前序顺序构建左右子树
cur->left = createTree(a, i);
cur->right = createTree(a, i);

return cur;

}

#### 双序列组合重建

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

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

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

前序遍历：

中序遍历：


![](/cc408/images/docs/data-structure/cfeebcb302.svg)

如上图所示，给定起始序列，可以判断先序序列中的第一个元素 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. 它的左、右子树也分别为二叉排序树。

![](/cc408/images/docs/data-structure/3959cfd97b.svg)

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

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




  * 结点定义

```c
typedef struct TreeNode {
```c
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;

}

  * 插入

```c
// 插入新节点
TreeNode* insert(TreeNode* root, int data) {
```c
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;

}

  * 查找

```c
// 查找节点
TreeNode* search(TreeNode* root, int data) {
```c
if (root == NULL || root->data == data) {
    return root;
}
if (data < root->data) {
    return search(root->left, data);
}
return search(root->right, data);

}

  * 删除

```c
// 删除节点
TreeNode* deleteNode(TreeNode* root, int data) {
```c
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\(log2​n\) 的水平，使得查找、插入和删除操作的时间复杂度都保持在 O\(log2​n\) 。

![](/cc408/images/docs/data-structure/5a539fc142.svg)

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

  1. **为什么需要旋转？**

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

  2. **从哪个节点开始旋转？**

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

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

  * **平衡因子** ：每个节点的平衡因子是其左子树的高度减去右子树的高度
  * **最小不平衡子树** ：最小不平衡子树是指在整棵二叉树中，高度差（平衡因子的绝对值）最小的子树，该子树的平衡因子绝对值超过 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 左旋

![](/cc408/images/docs/data-structure/3ee40d3239.svg)

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

  * 节点定义

```c
struct TreeNode {
```c
int data;
struct TreeNode* left;
struct TreeNode* right;
int height; // 节点高度

};

  * 左旋

```c
struct TreeNode* leftRotate(struct TreeNode* x) {
```c
struct TreeNode* y = x->right;
struct TreeNode* T2 = y->left;

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

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

return y;

}

  * 右旋

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

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

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

return x;

}

  * 计算平衡因子

```c
// 计算以 node 为根节点的子树高度
int getHeight(struct TreeNode* node) {
```c
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);

}

  * 更新节点高度

```c
// 在插入时需要使用该操作，重新计算子树高度
void updateHeight(struct TreeNode* node) {
```c
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

}

  * 旋转的完整实现

```c
struct TreeNode* insert(struct TreeNode* node, int data) {
```c
// 步骤 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](/cc408/images/docs/data-structure/a8effcea2e.svg)

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

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


<a id="binary-indexing"></a>
### 顺序编号：公式、不变量与边界

统一约定：根为第 1 个结点时，`left(i)=2i`、`right(i)=2i+1`、`parent(i)=floor(i/2)`；根为第 0 个结点时，`left(i)=2i+1`、`right(i)=2i+2`、`parent(i)=floor((i-1)/2)`（`i>0`）。访问前必须检查 `0≤i<n`（或 `1≤i≤n`），并检查子下标是否越界；越界代表空孩子，不能读数组。

完全二叉树的层序编号不变量是：结点 `i` 的后代编号连续且严格大于 `i`。这解释了堆的父子计算，也解释了为什么任意空槽之后不能再出现非空槽。常见错误是混用 0/1 基公式，或把数组容量 `MAX_SIZE` 当成实际结点数。

<a id="binary-null-links"></a>
### 空指针守恒与线索

含 `n` 个结点的二叉链表有 `2n` 个左右指针域；树边数为 `n-1`，其余 `2n-(n-1)=n+1` 个域为空。因此线索化最多得到 `n+1` 条线索。`ltag=0/rtag=0` 表示对应域仍是孩子，`ltag=1/rtag=1` 表示该域是前驱/后继线索；判断右孩子必须用 `p->rtag==0`，不能只判断 `rchild!=NULL`。

中序线索中，若有左孩子，前驱是左子树最右结点；若有右孩子，后继是右子树最左结点。后序后继通常不能仅靠线索确定：当结点是左孩子且父亲有右子树时，后继是右子树后序的第一个结点；标准二叉线索没有双亲指针，必须回溯或额外保存 parent。

<a id="traversal-reconstruction"></a>
### 遍历关系与唯一重建

前序 NLR、中序 LNR、后序 LRN、层序按层从左到右。前序+中序、后序+中序（结点值互异）可唯一重建：先用前/后序确定根，再在中序切分左右区间并递归；前序+后序一般不能唯一重建，单孩子时左右方向缺失。层序+中序也可按层序首个落在区间内的结点切分。带空标记 `#` 的单一遍历序列才可唯一描述结构。

若先序与后序互为逆序，树必为单支树，任意非叶结点恰有一个孩子，按根到叶方向高度等于结点数；若先序与中序相同，则所有非叶结点无左孩子（只有右子树）。不要把“只有一个叶子”误当成充分条件。

<a id="threaded-successor"></a>
### 遍历模板与线索可达性

递归模板只有一个不变量：进入函数时 `root` 是待处理子树根，空指针立即返回；把“访问根”的动作分别放在左右递归之间即可得到 NLR/LNR/LRN，复杂度均为 `O(n)`、栈空间 `O(h)`。层序模板使用队列，出队一个结点并依次入队非空左右孩子，时间 `O(n)`、峰值空间为最大宽度。

中序后继伪代码：若 `rtag==1`，直接返回 `rchild`；否则转到右孩子，再沿真实左孩子走到底。前驱对称处理 `ltag`。线索只承诺对应遍历次序的邻接关系，不能据此直接得到任意遍历的前驱/后继。

<a id="binary-algorithm-framework"></a>
### 综合算法闭环：不变量→步骤→边界→题型

以下题型共用“递归返回子问题结果，父层合并”的框架：

* **LCA**：空树或命中 `p/q` 返回当前结点；递归左右，若两侧均非空当前即 LCA，否则返回非空侧。结点不存在时应显式返回失败；时间 `O(n)`、空间 `O(h)`。
* **层高/最大宽度**：高度 `height(NULL)=0`，`height=1+max(left,right)`；宽度用队列逐层计数，空树边界返回 0。不要把“高度按边计数”和“按层计数”混用。
* **完全树判定**：层序扫描；遇到第一个空槽后，后续不得再遇到非空结点。时间 `O(n)`、空间 `O(w)`。
* **交换左右、计数度 2、删除 x 子树**：交换在后序或任意递归访问中对每个结点互换指针；计数在左右递归返回后判断两子树均非空；删除先后序释放左右再释放根，命中 `x` 时整棵子树返回空。三者均为 `O(n)`，空树是必测边界。
* **第 k 个先序**：维护剩余计数 `k`，访问根时先减一，随后递归左、右并在找到后立即停止；`k≤0` 或超过结点数返回未找到。不要把中序的计数顺序套用到先序。

易错点集中在：把线索域当孩子域、遗漏 `n+1` 推导、先序+后序声称唯一、递归释放时先释放根、以及未定义空树/不存在结点的返回值。

## 相关笔记

- 数组和特殊矩阵
- 串的定义与实现
- 串的模式匹配
- 串概述