在二叉搜索树顺序继承人 [英] In Order Successor in Binary Search Tree

问题描述

由于在BST的一个节点，一个人如何找到下一个更高的关键？

Given a node in a BST, how does one find the next higher key?

推荐答案

一般的方法取决于你是否有在你的节点或没有父母的联系。

The general way depends on whether you have a parent link in your nodes or not.

然后你选择：

1. 右孩子的最左边的孩子，如果当前节点有一个合适的孩子。如果有合适的孩子没有左孩子，右孩子是你的序后继。
2. 在浏览了父母祖先节点，当你发现父母的左孩子是你当前的节点，父母是你的原始节点的序后继。

如果你有合适的孩子，这样做的方法（案例1以上）：

If you have right child, do this approach (case 1 above):

如果你没有一个合适的孩子，这样做的方法（案例2段）：

If you don't have a right child, do this approach (case 2 above):

然后，你需要运行树的完整的扫描，保持节点的轨迹，通常有一个栈，所以你有必要基本上做一样依赖父母链路上的第一种方法的信息。

Then you need to run a complete scan of the tree, keeping track of the nodes, usually with a stack, so that you have the information necessary to basically do the same as the first method that relied on the parent link.

这篇关于在二叉搜索树顺序继承人的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！