知识卡片

普通读书笔记卡 · 1292.e.1.a

左孩子右兄弟压缩分支

理解等级:中级

孩子数不固定的有根树可让每节点只存最左孩子和紧邻右兄弟指针,再加父指针。找所有孩子从最左孩子沿兄弟链遍历,避免为潜在大量但通常为空的孩子位置预留字段。n 节点共用 O(n) 指针空间,访问所有孩子仍随孩子数增长。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.