5.3.2.1 中序线索二叉树的构造

教材导航 · 第5章

原书定位

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

按中序遍历,维护 pre 指向刚访问过的结点。当前结点左指针为空时建立指向 pre 的前驱线索;pre 的右指针为空时建立指向当前结点的后继线索,然后更新 pre。

最后处理末结点的后继。可增设头结点,连接整棵树及首尾结点,使遍历边界统一。头结点属于辅助存储,不能计入原树的结点数。

图5.17 中序线索二叉树

图5.17 中序线索二叉树,原书P146。

图5.18 带头结点的中序线索二叉树

图5.18 带头结点的中序线索二叉树,原书P146。

对应练习

5.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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

原书对照,原书P146,PDF第158页