5.3.2.2 中序线索二叉树的遍历
原书定位
印刷页P147起,对应PDF第159页。下文为目视整理的知识提要;完整内容见原书对照。
求第一个结点时沿真实左孩子一直向下;求后继时,若 rtag==1 则直接沿右线索,否则到真实右子树中寻找最左下结点。求前驱与之对称。
中序线索树可不借助栈顺序遍历,整体 、额外空间 ;单次寻找后继若要沿左链下降,并非对任意结点都严格为常数时间。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P147起,对应PDF第159页。下文为目视整理的知识提要;完整内容见原书对照。
求第一个结点时沿真实左孩子一直向下;求后继时,若 rtag==1 则直接沿右线索,否则到真实右子树中寻找最左下结点。求前驱与之对称。
中序线索树可不借助栈顺序遍历,整体 、额外空间 ;单次寻找后继若要沿左链下降,并非对任意结点都严格为常数时间。
