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

Question

我的BST不正确，其中两个节点不在正确的位置。我知道对BST的顺序遍历进行了排序。因此，我用三个指针遍历树：第一个，最后一个，中间。如果当前节点小于上一个节点，我将前一个节点设置为第一个节点，将当前节点设置为中间节点。这是第一次违规。发生第二次违规时，我将last指定为当前节点。现在当最后一个是NULL，交换第一和中间，当最后不是NULL交换第一个和最后一个。这就是我所做的：

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)

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

编辑：我编辑了代码。但是，第一，中间和最后的返回值仍然是无。这不是正确的方法吗？

Answer 1

你的功能fixBST和swap什么都不做。 first，middle和last仅限于fixBST的当地范围，所以从这个意义上来说它们并没有存储。 Python passes by assignment。

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

可能重新分配是要走的路。