二进制搜索树中的顺序继承者 [英] In Order Successor in Binary Search Tree

问题描述

给定一个BST中的节点，如何找到下一个更高的密钥？

解决方案

一般方式取决于是否您的节点中有一个父链接。

如果您存储父链接

然后选择：

1. 如果您当前的节点有一个正确的孩子，那么右边孩子的最左边的孩子。如果正确的孩子没有左小孩，则适当的孩子是您的顺序继承者。


2. 导航父祖父节点，当您找到一个父母，其左孩子是您的父节点时目前，父母是原始节点的顺序继承人。

如果您有正确的孩子，请执行此操作（上述情况1 ）：

如果您没有正确的孩子，请执行此操作（上述情况2）：

< img src =https://i.stack.imgur.com/Dulhx.pngalt =inorder-when-no-right-child>

如果您不存储父链接

然后，您需要运行树的完整扫描，跟踪节点，通常使用堆栈，以便您拥有所需的信息基本上与依赖于父链接的第一种方法相同。

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.

If you store the parent link

Then you pick:

1. The leftmost child of the right child, if your current node has a right child. If the right child has no left child, the right child is your inorder successor.
2. Navigate up the parent ancestor nodes, and when you find a parent whose left child is the node you're currently at, the parent is the inorder successor of your original node.

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

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

If you don't store the parent link

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屋！