5.3.2.1 中序线索二叉树的构造
原书定位
印刷页P145起,对应PDF第157页。下文为目视整理的知识提要;完整内容见原书对照。
按中序遍历,维护 pre 指向刚访问过的结点。当前结点左指针为空时建立指向 pre 的前驱线索;pre 的右指针为空时建立指向当前结点的后继线索,然后更新 pre。
最后处理末结点的后继。可增设头结点,连接整棵树及首尾结点,使遍历边界统一。头结点属于辅助存储,不能计入原树的结点数。

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

图5.18 带头结点的中序线索二叉树,原书P146。
对应练习
关联知识
原书对照
展开原书对照截图

