知识卡片

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

后继按右子树和祖先分支

理解等级:高级
  • 节点有右子树时,中序后继是右子树最左节点;
  • 没有右子树时,向上找到第一个从其左侧路径进入的祖先。

这里后继指中序遍历的下一节点,即使存在相等键也适用,不能一律解释成“严格更大的键”。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 12 章 12.2 节(`OEBPS/chapter012.xhtml`,文本字符 [10000, 15000))。 - 结论依据:12.2 节先把后继定义为中序遍历的下一节点,允许相等键;TREE-SUCCESSOR 有右子树时取其最左节点,无右子树时上行至第一个左分支祖先。 - 原始内容:Regardless of whether the keys are distinct, we define the successor of a node as the next node visited in an inorder tree walk.