如何通过在Python中交换节点来修复或纠正BST？

Question

我有一个错误的BST，其中两个节点不在正确的位置。我知道BST的无序遍历是排序的。因此，我用三个指针遍历树：第一、最后、中间。如果当前节点小于上一个节点，我将上一个设置为第一个，将当前节点设置为中间节点。这是第一次违规。当第二个冲突发生时，我将最后一个指定为当前节点。现在，当最后一个为＜code＞NULL＜/code＞时，先交换第一个和第二个，当最后最后一个不是＜code＞NULL＜/code＞时，首先交换最后一个。这就是我所做的：

class Node:
   def __init__(self,data):
      self.data = data
      self.left = None
      self.right = None


def fixBST(root,first,middle,last,prev):

    if( root ): 


        fixBST( root.left, first, middle, last, prev )

        if (prev and root.data < prev.data): 

            if ( first is None ): 

                first = prev 
                middle = root 

            else:
                last = root


        prev = root


        fixBST( root.right, first, middle, last, prev )
        return (first,middle,last)


def correctBST( root ): 


    first = middle = last = prev = None 


    first,middle,last = fixBST( root, first, middle, last, prev ) 

    if( first and last ): 
              t = first.data 
              first.data = last.data 
              last.data = t 
    elif( first and middle ): 
              t = first.data 
              first.data = middle.data 
              middle.data = t 



def printInorder(node): 

    if (node == None): 
        return
    printInorder(node.left)
    print node.data
    printInorder(node.right) 



root = Node(6)
root.left     = Node(10) 
root.right     = Node(2) 
root.left.left = Node(1) 
#root.left.right = Node(3) 
#root.right.right = Node(12) 
#root.right.left = Node(7) 

print "Inorder Traversal of the original tree \n" 
printInorder(root)

correctBST(root)

print "\nInorder Traversal of the fixed tree \n"
printInorder(root)

第二次打印顺序遍历后，我得到相同的错误树。我相信第一个、中间、最后一个值没有被存储？我错过了什么吗？

编辑:我编辑了代码。但是first、middle和last的返回值仍然是None。难道不是正确的方法吗？

Answer 1

您的函数固定BST和交换什么都不做。第一个、中间和最后一个仅限于固定BST的本地范围，所以从这个意义上说，是的，它们不被存储。Python通过赋值传递。

def swap(a,b): 

    t = a 
    a = b 
    b = t 

a, b = 1, 2
swap(a, b)
print(a, b)
# 1 2

您应该做的是返回一个值并重新分配或使用全局范围：

# Reassign
def swap(a,b): 
    return b, a

a, b = 1, 2
a, b = swap(a, b)
print(a, b)
# 2 1

# Global
a, b = 1, 2
def swap():
    global a
    global b
    t = a
    a = b
    b = t
swap()
print(a, b)
# 2 1

也许重新分配是应该走的路。