时间戳

首页 > 解决方案 > 如何通过交换 Python 中的节点来修复或更正 BST？

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

问题描述

我有一个不正确的 BST，其中两个节点不在正确的位置。我知道 BST 的中序遍历是排序的。因此，我用三个指针遍历树：第一个、最后一个、中间。如果当前节点小于前一个节点，我将前一个节点设置为第一个，当前节点设置为中间。这是第一次违规。当发生第二次违规时，我将 last 分配为当前节点。现在当 last 是NULL，交换第一个和中间，当 last 不是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)

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

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

标签： pythonrecursionbinary-search-treeswap

解决方案

你发挥作用fixBST，swap什么也不做。first, middle, 和last仅限于 的本地范围fixBST，所以从这个意义上说是的，它们没有被存储。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

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

推荐阅读