Распечатать двоичное дерево, Python, в порядке

Question

Я и мой друг занимаемся в школе программированием на Python 3.1 и ОЧЕНЬ застряли.Мы программируем двоичное дерево, и оно работает нормально, за исключением случаев, когда мы хотим напечатать все узлы в порядке, таким образом, чтобы создать предложение (все слова в порядке сразу после друг друга в строке).Мы искали по всему Интернету подсказки о том, как действовать, и мы работали с этой мелочью около двух часов.Любой совет / помощь будет потрясающим.

Наша программа / Двоичное дерево:

class Treenode:  
    def __init__(self, it = None, le = None, ri = None):  
        self.item = it  
        self.left = le  
        self.right = ri  

class Bintree:  
    def __init__(self):  
        self.item = None  
        self.left = None  
        self.right = None  

    def put(self, it = None):
        key = Treenode(it)
        if self.item == None:
            self.item = key
            return
        p = self.item
        while True:
            if key.item < p.item:
                if p.left == None:
                    p.left = key
                    return
                else:
                    p = p.left
            elif key.item > p.item:
                if p.right == None:
                    p.right = key
                    return
                else:
                    p = p.right
            else:
                return

    def exists(self, it):
        key = it
        p = self.item
        if p == key:
            return True
        while True:
            if key < p.item:
                if p.left == None:
                    return False
                else:
                    p = p.left
            elif key > p.item:
                if p.right == None:
                    return False
                else:
                    p = p.right
            else:
                return

    def isEmpty(self):
        if self.item == None:
            return True
        else:
            return False

def printtree (Treenode):
    if Treenode.left != None:
        printtree (Treenode.left)
    print (Treenode.item)
    if Treenode.right != None:
        printtree (Treenode.right)

Когда мы запускаем программу, мы получаем вид печати, который выглядит следующим образом: «объект bintree.Treenode в 0x02774CB0», а это не то, чтомы хотим.

Мы используем дерево, выполнив это:

import bintree

tree = bintree.Bintree()
print(tree.isEmpty())    # should give True
tree.put("solen")
print(tree.isEmpty())    # should give False
tree.put("gott")
tree.put("sin")
tree.put("hela")
tree.put("ban")
tree.put("upp")
tree.put("himlarunden")
tree.put("manen")
tree.put("seglar")
tree.put("som")
tree.put("en")
tree.put("svan")
tree.put("uti")
tree.put("midnattsstuden")

print(tree.exists("visa"))     # should give False
print(tree.exists("ban"))      # should give True
tree.printtree()               # print sorted

Кроме того, вторая последняя строка дает нам «None» вместо «True», что странно.

Answer 1

print(tree.exists("visa")) возвращает None, потому что в последней строке exists() есть оператор return без какого-либо значения (по умолчанию None).

Также не следует называтьprinttree аргумент Treenode, поскольку это имя существующего класса, и это может привести к путанице.Это должно выглядеть примерно так:

def printtree(tree_node):
    if tree_node.left is not None:
        printtree(tree_node.left)
    print(tree_node.item)
    if tree_node.right is not None:
        printtree(tree_node.right)

Другая вещь вызывает printtree - это функция, а не Bintree метод, поэтому я полагаю, вы должны вызывать ее printtree(tree).

Answer 2

Вы не указываете начальный регистр для printtree (). Вы определяете, как правильно проходить по своему дереву, но у вашего вызова printtree () нет узла для начала. Попробуйте установить проверку по умолчанию, чтобы увидеть, передается ли параметр, и если он не запускается в головном узле bintree.

Причина, по которой ваша вторая до последней строки печатает None, заключается в том, что в вашем методе существует просто «return», а не «return True», для случая нахождения «p.item», который равно ключу.

Answer 3

Чтобы распечатать двоичное дерево, если вы печатаете лист, вы просто печатаете значение; в противном случае вы печатаете левого потомка, а затем правого.

def print_tree(tree):
    if tree:
        print tree.value
        print_tree(tree.left)
        print_tree(tree.right)

Answer 4

Один из способов сделать тестирование проще - использовать -assert () - вместо того, чтобы что-то печатать, а затем возвращаться к своему коду.

tree = Bintree()
assert(tree.isEmpty())
tree.put("solen")
assert(not tree.isEmpty())
tree.put("gott")
tree.put("sin")
tree.put("hela")
tree.put("ban")

http://docs.python.org/reference/simple_stmts.html#the-assert-statement

Возникает ошибка, если условие не выполняется.Я знаю, что это не исправляет вашу ошибку, но устранение неоднозначности всегда помогает при отладке.