Python реализует метод предварительного заказа двоичного дерева

Question

Почему эта программа на питоне не может работать правильно. Я хотел бы построить двоичное дерево, а затем пройти его в предварительном порядке. Когда я вызываю метод PreOrder, он ничего не возвращает.

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

class BTree:
    def __init__(self, root):
        self.root = root

    def CreateTree(self, root):
        self.root.data = raw_input("Enter data,'*' means empty: ")
        if self.root.data == '*':
            return
        self.root.left = Node()
        self.root.right = Node()
        self.CreateTree(self.root.left)
        self.CreateTree(self.root.right)

    def PreOrder(self, root):
        if self.root != None:
            if self.root.data != '*':
                print self.root.data,
                PreOrder(self, self.root.left)
                PreOrder(self, self.root.right)

if __name__ == '__main__':
    t = Node()
    bt = BTree(t)
    bt.CreateTree(t)
    bt.PreOrder(t)

Answer 1

PreOrder - это метод класса BTree, вы можете изменить рекурсивные вызовы, например:

def PreOrder(self):
    if self.root != None:
        if self.root.data != '*':
            print self.root.data,
            self.root.left.PreOrder()
            self.root.right.PreOrder()

Вам также не нужно передавать root в CreateTree, если вы используете только self.root, который вы сохранили в __init__

Answer 2

Поскольку вы устанавливаете self.root.data = '*' в функции CreateTree, выполнив это self.root.data = raw_input("Enter data,'*' means empty: "). И чтобы завершить запрос ввода, вы должны ввести '*' в конце. Итак, последнее значение, которое имеет ваш self.root.data, равно '*'.

Попробуйте это

    print self.root.data
    root.data = raw_input("Enter data,'*' means empty: ")
    print self.root.data
    if root.data == '*':
        return

и это

    def CreateTree(self,root):
        print self.root.data
        root.data = raw_input("Enter data,'*' means empty: ")
        print self.root.data
        if root.data == '*':
            return
        self.root.left = Node()
        self.root.right = Node()
        self.CreateTree(self.root.left)
        self.CreateTree(self.root.right)

    def PreOrder(self, root):
        print root
        print self.root
        print self.root.data
        if self.root != None:
            if self.root.data != '*':
                print self.root.data,
                PreOrder(self, self.root.left)
                PreOrder(self, self.root.right)
            else:
                print 'what the hell'

if __name__ == '__main__':
    t = Node(10,Node(),Node())
    print t.data
    bt = BTree(t)
    bt.CreateTree(t)
    bt.PreOrder(t)

чтобы знать, где это пошло не так.

Answer 3

Ваш метод CreateTree вообще не упоминает параметр root. Этот метод всегда работает на self.root.

Как-то так может работать:

def CreateTree(self, current_node):
    current_node.data = raw_input("Enter data,'*' means empty: ")
    if current_node.data == '*':
        return
    current_node.left = Node()
    current_node.right = Node()
    self.CreateTree(current_node.left)
    self.CreateTree(current_node.right)

Answer 4

Если вы посмотрите на ваш CreateTree метод, вы увидите, что вы никогда не используете root, и поэтому self.root.data всегда будет *. Если вы исправите это, у вашего кода будет больше проблем, связанных с self и областями действия. Вы можете проверить это .