 遍历全解析)
文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本篇文章基于 CLRS 习题解答仓库中的 docs/Chap10/10.4.md 展开系统讲解《算法导论》Introduction to Algorithms, Third Edition第 10 章第 4 节「有根树的表示Representing Rooted Trees」的六道习题。你将掌握如何从数组属性还原二叉树、递归与非递归的中序遍历、左孩子右兄弟left-child, right-sibling表示下的树遍历以及两道星级难题——仅用常数额外空间且不修改树的遍历和用「两指针 一布尔位」压缩表示的技巧。背景有根树在算法教材中的三种表示方式第 10 章的基本数据结构部分栈、队列见 docs/Chap10/10.1.md链表见 docs/Chap10/10.2.md指针与对象的数组实现见 docs/Chap10/10.3.md讨论的都是线性结构而 10.4 节将视角扩展到非线性结构——树。教材以及本仓库对应的习题主要围绕三种树表示二叉树的标准表示每个节点含key、left、right三个属性必要时加parent通过T.root指向根节点。左孩子右兄弟表示LCRS每个节点含left-child与right-sibling用于将任意有根树孩子个数不定编码成二叉树形态。带parent指针的表示牺牲一点空间换取回溯能力是 10.4-5、10.4-6 两道难题的基础。下面按习题逐一讲解本仓库给出的解法。习题 10.4-1从属性数组还原二叉树Draw the binary tree rooted at index 6 that is represented by the following attributes.给定 10 个节点的属性表index、key、left、rightindexkeyleftright112732158NIL3410NIL4105952NILNIL6181477NILNIL81462921NILNIL105NILNIL还原过程就是从根节点 index 6key 18出发沿left/right属性逐层展开根 6左孩子 1key 12右孩子 4key 10节点 1左孩子 7key 7右孩子 3key 4节点 3左孩子 10key 5右孩子 NIL节点 4左孩子 5key 2右孩子 9key 21节点 7、5、9 均为叶子left/right为 NIL。值得指出的是属性表中节点 2 与节点 8 互相指向2.left 8且8.right 2构成一个环状配对它们并不位于根 6 的可达子树内。这正是数组表示下不保证每个条目都从根可达的典型例子——还原时应只画出以根为起点的连通部分。上面引用的配图docs/img/10.4-1.png即本题标准答案的二叉树图示。这一题的实践价值在于它演示了教材第 10.3 节「用数组实现指针与对象」的思想——当key/left/right被平铺在数组里时所谓指针就是数组下标NIL就是 0 或哨兵值树的遍历完全可以在数组上下标跳转完成。可结合 docs/Chap10/10.3.md 中ALLOCATE-OBJECT/FREE-OBJECT的空闲表管理理解这种下标即地址的表示法。习题 10.4-2O(n) 递归打印二叉树所有键Write an O(n)-time recursive procedure that, given an n-node binary tree, prints out the key of each node in the tree.递归解法即经典的中序遍历in-order先左子树、再根、后右子树每个节点恰好访问一次总时间 O(n)PRINT-BINARY-TREE(T) PRINT-BINARY-TREE-AUX(T.root) PRINT-BINARY-TREE-AUX(x) if node ! NIL PRINT-BINARY-TREE-AUX(x.left) print x.key PRINT-BINARY-TREE-AUX(x.right)要点分析终止条件x NIL时直接返回对应二叉树中空子树的自然表达时间复杂度n 个节点各被访问一次每次做常数次操作因此是严格的 O(n)空间开销递归深度等于树高最坏链状树为 Θ(n) 的调用栈空间——这正是下一题要用显式栈替换递归的动机。递归遍历是后续第 12 章二叉搜索树BST查询操作如 docs/Chap12/12.2.md 中的 TREE-SEARCH、INORDER-TREE-WALK的基础骨架。习题 10.4-3O(n) 非递归遍历辅助栈版Write an O(n)-time nonrecursive procedure that ... Use a stack as an auxiliary data structure.用显式栈模拟递归栈沿左链压栈直至最左叶子出栈打印后再转向右子树PRINT-BINARY-TREE(T, S) PUSH(S, T.root) while !STACK-EMPTY(S) x S[S.top] while x ! NIL // store all nodes on the path towards the leftmost leaf PUSH(S, x.left) x S[S.top] POP(S) // S has NIL on its top, so pop it if !STACK-EMPTY(S) // print this node, leap to its in-order successor x POP(S) print x.key PUSH(S, x.right)逐步解读这段伪代码初始把根压入栈外层循环持续到栈空内层循环反复把x.left压栈直到栈顶为 NIL——此时栈中保存着「根到最左叶子的整条路径」这与递归版先递归左子树的行为完全一致POP(S)弹掉栈顶的 NILNIL 是哨兵不入栈则代码要额外判断这里用先压 NIL 再弹 NIL简化分支若栈非空弹出节点并打印其 key然后将x.right压栈进入右子树。该过程用到了 docs/Chap10/10.1.md 中定义的PUSH、POP、STACK-EMPTY等栈原语。复杂度方面每个节点被压栈、弹栈各一次外加 NIL 哨兵的入栈出栈总时间为 O(n)空间为 O(h)h 为树高。栈式遍历消除了递归深度限制适合树高较大或递归栈受限如嵌入式环境的场景。习题 10.4-4遍历左孩子右兄弟LCRS表示的有根树Write an O(n)-time procedure that prints all the keys of an arbitrary rooted tree with n nodes, where the tree is stored using the left-child, right-sibling representation.任意有根树的每个节点孩子数不定用left-child第一个孩子与right-sibling下一个兄弟两个指针即可编码。遍历时先打印根再递归进入第一个孩子然后沿right-sibling链递归处理其余孩子PRINT-LCRS-TREE(T) x T.root if x ! NIL print x.key lc x.left-child if lc ! NIL PRINT-LCRS-TREE(lc) rs lc.right-sibling while rs ! NIL PRINT-LCRS-TREE(rs) rs rs.right-sibling理解要点先根前序语义对 LCRS 表示print x.key在递归孩子之前执行对应原树的先根序遍历两重递归第一重递归处理left-child子树第二重while循环沿right-sibling链遍历兄弟——这正是任意叉树在二叉树编码下的遍历写法复杂度每个节点恰好被PRINT-LCRS-TREE调用一次无论作为左孩子还是兄弟内部指针移动均为常数次故总时间 O(n)。从结构上看LCRS 表示把任意有根树等价转换成二叉树因此在第 13 章红黑树、第 18 章 B 树等章节中把多叉结构折叠成二叉树是一种通用设计手法。本题的代码模式也直接服务于 10.4-6 对 LCRS 表示的空间压缩改造。习题 10.4-5 ★O(n) 常数空间、不修改树的遍历Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.这是本节第一道星级难题。限制有三条非递归、除树本身外仅常数额外空间、遍历过程中不能临时改动树。解法依赖每个节点自带parent指针——用prev记录上一个访问的节点通过我从哪里来判断下一步走向PRINT-KEY(T) prev NIL x T.root while x ! NIL if prev x.parent print x.key prev x if x.left x x.left else if x.right x x.right else x x.parent else if prev x.left and x.right ! NIL prev x x x.right else prev x x x.parent运行机理可归纳为三种状态转移prev是x的父节点说明刚下行进入x此时打印x.key前序语义优先下探左孩子左孩子为空则下探右孩子左右皆空则回退到父节点prev是x的左孩子说明左子树已遍历完毕若x有右孩子则转向右孩子其他情况prev是x的右孩子说明左右子树都已完成回退到父节点。复杂度论证时间 O(n)每条树边父→子在两个方向上各被走过一次共 2(n-1) 次指针移动加上每个节点的常数次打印与判断总操作 O(n)空间 O(1)全程只用prev、x两个游标变量外加伪代码中隐含的临时量不申请与 n 相关的辅助结构不修改树所有状态都记录在prev游标中树中任何left/right/parent属性都不被改写——这不同于经典 Morris 遍历Morris 需要临时把右子树最右节点的空指针指向后继。正是因为节点带了parent指针才能做到用路径记忆代替结构改写。这一技巧在后续章节有直接应用例如 docs/Chap13/13.1.md 红黑树的树结构调整、以及各种需要从叶子回溯到祖先如求树高、判平衡、LCA 类问题的场景。它也是面试中高频考察的O(1) 空间遍历二叉树标准答案之一。习题 10.4-6 ★两指针 一布尔值的压缩 LCRS 表示The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers in each node: left-child, right-sibling, and parent. ... Show how to use only two pointers and one boolean value in each node so that the parent of a node or all of its children can be reached and identified in time linear in the number of children.标准 LCRS 表示每个节点需要left-child、right-sibling、parent三个指针从任意节点可 O(1) 找到父节点遍历孩子需 O(孩子数)。本题要求把三个指针压缩为两个指针 一个布尔值同时保持「找父节点 / 找全部孩子」都在 O(孩子数) 时间内完成。仓库给出的精炼答案Use boolean to identify the last sibling, and the last siblings right-sibling points to the parent.方案展开如下每个节点保留left-child和right-sibling两个指针外加一个布尔标志位is-last-sibling对非最后一个兄弟的节点right-sibling指向下一个兄弟is-last-sibling false对最后一个兄弟的节点right-sibling不再指向 NIL而是指向父节点is-last-sibling true。由此得到的操作能力找父节点从某个孩子节点出发沿right-sibling链向后走直到遇到is-last-sibling true的节点其right-sibling就是父节点。花费 O(孩子数) 时间枚举全部孩子从left-child出发沿right-sibling走遇到is-last-sibling true即停该节点的right-sibling是父节点而非兄弟正好作为链的终止哨兵。同样 O(孩子数)空间收益每节点从 3 个指针降为 2 个指针 1 bit在指针为 64 位、布尔位可打包如 C 语言位域或单字节标志时节点内存可节省约 1/3 指针空间且仍然不需要独立的parent指针。正确性关键在于布尔标志解除了「right-sibling 指向谁」的歧义若不设标志单看right-sibling无法区分指向兄弟与指向父节点有了is-last-sibling链的终点被显式标注遍历与回溯就都能在常数时间内判断边界。这与 docs/Chap10/10.2.md 习题 10.2-8XOR 链表用单指针同时编码 prev 与 next在思想上同源——都是在指针数量受限时用额外标志位或位运算换空间。总结六题覆盖的树遍历能力图谱习题表示方式遍历方式时间额外空间是否修改树10.4-1数组属性表key/left/right手工还原———10.4-2二叉树left/right递归中序O(n)O(h) 调用栈否10.4-3二叉树left/right非递归显式栈O(n)O(h)否10.4-4LCRSleft-child/right-sibling递归先根O(n)O(h)否10.4-5 ★二叉树 parent非递归游标法O(n)O(1)否10.4-6 ★压缩 LCRS两指针一布尔支持父节点/孩子枚举O(孩子数)每节点省一指针—纵观六题有一条清晰的主线从表示走向遍历——10.4-1 解决如何读懂一种表示10.4-2/3/4 解决三种表示下的 O(n) 遍历10.4-5 把空间压到常数且不破坏结构10.4-6 把表示本身压到最小。掌握这些解法后你可以直接迁移到二叉搜索树docs/Chap12、红黑树docs/Chap13以及一切基于指针表示的分层数据结构中。本仓库README 见 README.md站点配置见 mkdocs.yml以 Markdown KaTeX 组织《算法导论》第三版习题解答其中 docs/Chap10/10.4.md 正是 10.4 节全部习题的解答原文上文所有伪代码均取自该文档可按需继续查阅同章 10.1、10.2、10.3 各节及章节习题Problems/10-1 等以获得更完整的上下文。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 10.4 节精讲二叉树的表示与 O(n) 遍历 —— 从递归、栈辅助到常数空间的 Parent 指针遍历CLRS 第 10.4 节精讲二叉树的表示与 O n 遍历 —— 从递归、栈辅助到常数空间的 Parent 指针遍历 导读 本文以《算法导论》Introdu文档教程示例工程CLRS 算法导论 6.1 节精讲堆的数组表示、高度与叶子性质的七道习题完整解析CLRS 算法导论 6.1 节精讲堆的数组表示、高度与叶子性质的七道习题完整解析 本文对应《Introduction to Algorithms》第三版第 6文档教程教育CLRS 算法导论 12.2 节精讲二叉搜索树查询操作TREE-MINIMUM / TREE-MAXIMUM / TREE-SUCCESSOR / TREE-PREDECESSOR与习题全解析CLRS 算法导论 12.2 节精讲二叉搜索树查询操作TREE MINIMUM / TREE MAXIMUM / TREE SUCCESSOR / TREE文档教程示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
