知识卡片
左孩子右兄弟压缩分支
孩子数不固定的有根树可让每节点只存最左孩子和紧邻右兄弟指针,再加父指针。找所有孩子从最左孩子沿兄弟链遍历,避免为潜在大量但通常为空的孩子位置预留字段。n 节点共用 O(n) 指针空间,访问所有孩子仍随孩子数增长。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第10章 基本数据结构 · 查看原书依据
x.left-child points to the leftmost child of node x, and x.right-sibling points to the sibling of x immediately to its right.
参考来源
- 位置:《算法导论(第4版)》第 10 章 10.3 节(`OEBPS/chapter010.xhtml`,文本字符 [25000, 27500);图 10.7/Art_P373)。
- 结论依据:原文给出 left-child/right-sibling 的字段含义及任意分支数下 O(n) 空间保证。
- 原始内容:x.left-child points to the leftmost child of node x , and x.right-sibling points to the sibling of x immediately to its right.