Как исправить или исправить BST путем замены узлов в Python? - PullRequest
Новая
       35

Как исправить или исправить BST путем замены узлов в Python?

0 голосов
/ 08 марта 2019

У меня неверный BST, где два узла не в правильном положении. Я знаю, что прохождение по BST отсортировано. Поэтому я пересекаю дерево с тремя указателями: первый, последний, средний. Если текущий узел меньше предыдущего, я устанавливаю предыдущий узел как первый, а текущий узел как средний. Это для первого нарушения. Когда происходит второе нарушение, я назначаю последний как текущий узел. Теперь, когда последний равен 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)

Я получаю то же неверное дерево после печати обхода заказа во второй раз. Я считаю, что первое, среднее, последнее значения не сохраняются? Я что-то упускаю?

РЕДАКТИРОВАТЬ: я редактировал код. Но все же возвращаемое значение первого, среднего и последнего равно None. Разве это не правильный путь?

1 Ответ

0 голосов
/ 08 марта 2019

Вы выполняете функции 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

Возможно, переназначение - это способидти.

...