文章目录
- 线索二叉树的作用
- 线索二叉树的存储结构
- 三种线索二叉树
-
- `*`中序线索二叉树
- 先序线索二叉树
- 后序线索二叉树
- 对比
- 手画线索二叉树
n 个结点的二叉树，有
n+1 个
空指针域。利用这个可用来记录前驱、后继的信息。
即利用了二叉链表中
n+1 x个空指针域，将遍历过程从“递归/栈”加速为 “线性指针跳转”，空间复杂度降为
O(1)。
线索二叉树的作用
-
痛点 1（空间浪费）：含有 n 个结点的二叉链表，有 2n 个指针域，其中有效指针为 n-1（指向孩子），剩下 n+1 个指针域全是空指针（NULL），浪费严重。
-
痛点 2（效率低）：中序遍历虽然快（O(n)），但依赖递归（系统栈）或自定义栈（O(h) 空间）。如果要频繁查找某个结点的“前驱”或“后继”，每次都要从根开始遍历，效率极低。
解决思路：利用这 n+1 个空指针，指向该结点在某种遍历序列（前/中/后）中的前驱和后继。这些“指向前驱/后继”的指针称为 “线索”。
线索二叉树的存储结构
tag = 0 指孩子，tag = 1 指线索（前驱/后继）
// 线索二叉树结点 称为 线索链表
typedef struct ThreadNode {
int data; // 数据域
struct ThreadNode *lchild, *rchild; // 左右孩子指针
int ltag, rtag; // 标志域（布尔值）
} ThreadNode, *ThreadTree;
/*
* 标志位含义：
* ltag == 0：lchild 指向左孩子（正常） 指向真正的左孩子
* ltag == 1：lchild 指向前驱（线索）
*
* rtag == 0：rchild 指向右孩子（正常） 指向真正的右孩子
* rtag == 1：rchild 指向后继（线索）
*/
三种线索二叉树
*中序线索二叉树
线索化依据：中序遍历序列 tag = 0 指孩子，tag = 1 指线索（前驱/后继）
-
后继（rchild 线索）：若 rtag == 1，直接走 rchild 就是后继；若 rtag == 0，后继结点。
-
前驱（lchild 线索）：若 ltag == 1，直接走 lchild 就是前驱；若 ltag == 0，前驱结点。
先序线索二叉树
线索化依据：先序遍历序列 
后序线索二叉树
线索化依据：后序遍历序列 
对比
手画线索二叉树
