5.3.2 线索二叉树

教材导航 · 第5章

原书定位

印刷页P145起,对应PDF第157页。下文为目视整理的知识提要;完整内容见原书对照。

将空左孩子指针用于指向遍历前驱,空右孩子指针用于指向遍历后继。增加 ltag、rtag:0 表示真实孩子,1 表示线索。线索化改变存储中的指针用途,不改变原树的逻辑结构。

“前驱、后继”必须说明对应先序、中序还是后序;有真实子树时,不能把孩子指针直接当作相邻访问结点。构造与遍历都要检查标志,避免沿线索再次递归。

图5.16 线索二叉树结点与标志域

图5.16 线索二叉树结点与标志域,原书P145。

下级知识点

对应练习

5.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P145,PDF第157页