1.1 顺序存储#

顺序存储使用数组存放完全二叉树，通过下标表示结点关系。

编号规则（从 1 开始）：

特点：适合完全二叉树，空间利用率高；非完全二叉树会浪费空间。

1.2 链式存储（二叉链表）#

链式存储使用指针连接结点，每个结点包含：

• data：数据域
• lchild：左孩子指针
• rchild：右孩子指针

重要规律：空指针个数 = 结点数 + 1

1.3 三叉链表#

在二叉链表基础上增加 parent 指针，方便向上查找。

2.1 C++ 写法#

1
struct BTNode {
2
    char data;
3
    BTNode *lchild;
4
    BTNode *rchild;
5
};

2.2 C 语言写法（typedef）#

使用 typedef 给结构体起别名，简化声明：

1
typedef struct BTNode {
2
    char data;
3
    struct BTNode *lchild, *rchild;
4
} BTNode;
5

6
// 使用时不需要加 struct 前缀
7
BTNode a, *d;
8
BTNode *b = (BTNode*)malloc(sizeof(BTNode));

3.1 为什么需要线索化#

二叉链表中存在大量空指针（结点数+1 个），造成浪费。

线索化：利用空指针存储前驱/后继信息，提高遍历效率。

3.2 线索化规则#

3.3 线索标志位#

如何区分指针指向的是孩子还是线索？增加 ltag 和 rtag 标志位：

结点结构：

1
typedef struct BTNode {
2
    char data;
3
    struct BTNode *lchild, *rchild;
4
    int ltag, rtag;  // 线索标志
5
} BTNode;

3.4 中序线索二叉树示例#

对二叉树进行中序线索化后：

• 中序序列：B → D → A → C
• 空指针被利用为前驱/后继线索