知识卡片
后继按右子树和祖先分支
- 节点有右子树时,中序后继是右子树最左节点;
- 没有右子树时,向上找到第一个从其左侧路径进入的祖先。
这里后继指中序遍历的下一节点,即使存在相等键也适用,不能一律解释成“严格更大的键”。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
Regardless of whether the keys are distinct, we define the successor of a node as the next node visited in an inorder tree walk.
参考来源
- 位置:《算法导论(第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.