BST 节点的中序后继：某些节点的属性错误

Question

我正在尝试解决GeeksforGeeks问题BST中的顺序后继者：

给定一个 BST，以及对 BST 中节点 x 的引用。在 BST 中查找给定节点的中序后继。

解决方案在 GeeksforGeeks 进行了讨论，我查看了那里列出的第二种方法：

方法2（从根目录搜索）

该算法不需要父指针。该算法根据输入节点的右子树是否为空分为两种情况。

我采用了这种方法，但不明白为什么我的尝试没有达到预期效果。这是我尝试过的：

def inorder_successor(root, x):
  if x.right != None :
      t = x.right 
      while t.left != None:
        t = t.left
        #print(t.elem)
      return t  
  if root.left == None or root.right:
    return
  if root.left == x:
    return root 

  inorder_successor(root.left, x)
  inorder_successor(root.right, x)
  
def inorder(root):
  if root == None:
    return

  inorder(root.left)
  print(root.elem, end = ' ')
  inorder(root.right)
  
class BTNode:
  def __init__(self, elem):
    self.elem = elem
    self.right = None
    self.left = None

# Create input BST    
n20 = BTNode(20)
n8  = BTNode(8)
n22 = BTNode(22)
n4  = BTNode(4)
n12 = BTNode(12)
n10 = BTNode(10)
n14 = BTNode(14)

n20.left = n8
n20.right = n22

n8.left = n4
n8.right = n12

n12.left = n10
n12.right = n14

print('Given Tree Inorder Traversal: ', end = ' ')
inorder(n20) #Given Tree Inorder Traversal:  4 8 10 12 14 20 22
print()

# This works:
x = n8
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}') #Inorder successor of node 8: 10

# This doesn't work (None). Expected 8
x = n4
print(f'Inorder successor of node {x.elem}: {inorder_successor(n20, x).elem}')  # Error

这是上面代码尝试使用的树：

     20
    /  \
   8    22
  / \
 4   12
    /  \
  10    14

问题

在为

inorder_successor

 或 

n10

 等节点调用 

n4

 时，我的代码没有给出正确的输出：它会产生错误，因为 

inorder_successor

 函数返回 

None

。

但是，如果我在第 11 行打印

n20.elem

，它就会工作并打印所需的节点元素。所以我很困惑这是否有效，但代码给出了错误（“'NoneType'对象没有属性'elem'”）。该代码适用于像 

n20

 这样的节点。

我的错误在哪里？

Answer 1

您的代码的以下部分有几个问题：

  if root.left == None or root.right:
    return
  if root.left == x:
    return root 

  inorder_successor(root.left, x)
  inorder_successor(root.right, x)

• 只要

  or root.right

   有右孩子，

  if

   部分就会使 

  root

   条件为真，这在函数的非递归调用中始终是这种情况，因此您的函数总共返回 

  None

  执行这部分代码的情况（即 

  x

   没有右子节点时）。

• 此逻辑唯一一次返回节点是您拥有

  return root

   的位置，在这种情况下 

  x

   是其左子节点。但这假设如果 

  x

   的后继者不是它的后代，那么它必须是它的 

  immediate 父级，并且它必须是其左子级。这通常不是真的。 x

  的继承者可能是它的grand(grand(grand))parent...

• 递归调用没有任何目标，因为在完成所有工作后，您的代码不会查看它们返回的内容

• 这棵树是 BST 的事实在这部分代码中并未被利用。例如，当

  x.elem

  大于

  root.elem

  时，查看

  root.left

  是没有意义的，因为可以肯定

  x

  的后继者只能在右侧。

更正

正如您已经指出的资源提供了正确的代码和解释，我将在这里提供一个保留使用递归思想的解决方案。

代码中引用的部分可以替换为：

  if root:
      if x.elem > root.elem:  # must go right:
          return inorder_successor(root.right, x)
      if x.elem < root.elem:  # go left, but root might be the successor
          return inorder_successor(root.left, x) or root