5.3.1.3 后序遍历
原书定位
印刷页P142起,对应PDF第154页。下文为目视整理的知识提要;完整内容见原书对照。
顺序为左—右—根 LRN,适合在两个子树处理完之后计算根的结果,如求高度、求子树结点数、释放整棵树。非递归实现需记录右子树是否已处理,可用最近访问结点或状态标记,防止重复访问与提前访问根。

图5.9 二叉树后序遍历,原书P142。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P142起,对应PDF第154页。下文为目视整理的知识提要;完整内容见原书对照。
顺序为左—右—根 LRN,适合在两个子树处理完之后计算根的结果,如求高度、求子树结点数、释放整棵树。非递归实现需记录右子树是否已处理,可用最近访问结点或状态标记,防止重复访问与提前访问根。

图5.9 二叉树后序遍历,原书P142。
