二叉搜索树中的有序后继 [英] 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屋！