🔗链表存储结构对比
二叉链表 (Binary Linked List)
结点结构
lchild
data
rchild
n 个结点的二叉链表中，有 n+1 个空链域
三叉链表 (Triple Linked List)
结点结构
lchild
data
rchild
parent
增加 parent 指针，便于向上查找和回溯
| 特性 | 二叉链表 | 三叉链表 |
|---|---|---|
| 指针域个数 | 2 (lchild, rchild) | 3 (lchild, rchild, parent) |
| 找双亲 | 需从根遍历，O(n) | 直接访问 parent，O(1) |
| 存储密度 | 较高 | 较低（多一个指针） |
| 适用场景 | 普通二叉树操作 | 需频繁向上访问（如线索化） |