5.3.2 线索二叉树
原书定位
印刷页P145起,对应PDF第157页。下文为目视整理的知识提要;完整内容见原书对照。
将空左孩子指针用于指向遍历前驱,空右孩子指针用于指向遍历后继。增加 ltag、rtag:0 表示真实孩子,1 表示线索。线索化改变存储中的指针用途,不改变原树的逻辑结构。
“前驱、后继”必须说明对应先序、中序还是后序;有真实子树时,不能把孩子指针直接当作相邻访问结点。构造与遍历都要检查标志,避免沿线索再次递归。

图5.16 线索二叉树结点与标志域,原书P145。
下级知识点
对应练习
关联知识
- 5.3 二叉树的遍历和线索二叉树
- 5.3.1.2 中序遍历
- 5.3.2.1 中序线索二叉树的构造
- 5.3.2.2 中序线索二叉树的遍历
- 5.3.2.3 先序线索与后序线索
- 7.3.1 二叉排序树的定义
原书对照
展开原书对照截图
