BST 的有序连续：我很困惑为什么我的代码给我一个属性错误（数据结构 Python）

Question

当我尝试查找给定节点的中序后继者时，我的代码不适用于像

x=n5 

或

x=n1

这样的节点。

问题链接在这里 他们在那里讨论了解决方案，但我对为什么我的解决方案不起作用感到困惑。所以请帮忙。

我的代码不适用于

x=n5 

或

x=n1

等节点 但是，如果我在第 11 行打印 root.elem，它就会工作并打印所需的节点元素。所以我很困惑，这是有效的，但代码给出了错误。该代码适用于像 n1 这样的节点。

这是我尝试过的

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)
  
  #DRIVER CODE
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
    
root = BTNode(20)
n1 = BTNode(8)
n2 = BTNode(22)
n3 = BTNode(4)
n4 = BTNode(12)
n5 = BTNode(10)
n6 = BTNode(14)

root.left = n1
root.right = n2

n1.left = n3
n1.right = n4

n4.left = n5
n4.right = n6

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

x = n3
print(f'Inorder successor of node {x.elem}: {inorder_successor(root, x).elem}') #Inorder successor of node 8: 10

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