在二进制搜索树中的顺序继承者

Question

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

Answer 1

一般方法取决于您的节点中是否有父链接.

如果存储父链接

然后你选择:

1. 如果您当前的节点有一个正确的孩子,那么右孩子的最左边的孩子.如果合适的孩子没有留下孩子,那么正确的孩子就是你的继承人.
2. 向上导航父祖先节点,当您找到其子节点是您当前所在节点的父节点时,父节点是原始节点的inorder后继节点.

如果您有正确的孩子,请采用这种方法(上述案例1):

如果您没有合适的孩子,请采用以下方法(上述案例2):

如果您不存储父链接

然后,您需要对树进行完整扫描,跟踪节点,通常使用堆栈,这样您就可以获得必要的信息,基本上与依赖父链接的第一个方法相同.

Answer 2

对Lasse的答案的 Python代码:

def findNext(node):
  if node.rightChild != None:
    return findMostLeft(node.rightChild)
  else:
    parent = node.parent
    while parent != None:
      if parent.leftChild == node:
        break
      node = parent
      parent = node.parent
    return parent