5.3.2.3 先序线索与后序线索
原书定位
印刷页P147起,对应PDF第159页。下文为目视整理的知识提要;完整内容见原书对照。
先序后继:有左孩子就选左孩子;否则有右孩子就选右孩子;叶结点可沿后继线索。线索化时访问根之后须区分刚建立的线索与真实孩子,避免死循环。
后序后继常与双亲有关:右孩子处理完后访问双亲;若当前在左子树且双亲有未处理的右子树,则转入右子树后序的首结点。仅凭原来的两孩子指针与空域线索,未必能直接找到双亲,因此可增加双亲指针或借助栈。

图5.19 先序与后序线索二叉树,原书P147。
对应练习
关联知识
原书对照
展开原书对照截图

