打印一棵二叉树，使用Python，在中序遍历中

Question

我和我的朋友正在使用Python 3.1进行编程的学校作业，与IT技术有关。我们正在编写一个二叉树程序，除了在想要按顺序打印所有节点以创建一个句子时出现问题（所有单词按顺序排列在一起），它工作得很好。我们已经在互联网上寻找线索并且已经使用这个小东西工作了两个小时。任何建议/帮助都将是非常棒的。

我们的程序/二叉树：

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 object at 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”，这很奇怪。

- user621399

---

我认为您混淆了当您有一个Treenode实例和当您有一个Bintree实例的时候。例如，程序中的一些东西具有属性“item”，它是一个字符串，而有些东西则具有Treenode作为item。尝试将Bintree中的名称item更改为其他名称，例如node，然后当您尝试在实际上是Bintree而不是Treenode的内容上打印item属性时，您可能会开始获得有意义的错误。 - Duncan

嗯，使用 None 替代 True 似乎是一个简单的修复方法。exists() 的最后一行应该是“return True”。 - stribika

Answer 1

打印二叉树时，如果要打印一个叶子节点，只需打印该节点的值；否则，您需要先打印左孩子，再打印右孩子。

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

- Katriel

Answer 2

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)。

- Michal Chruszcz

---

我认为这可能是一个方法，但是当代码被粘贴时缩进出现了问题。如果是真的，那么就意味着被误导的参数 Treenode，或者按照你所说的 tree_node，实际上应该叫做 self 并且实际上是一个 Bintree！ - Duncan

Answer 3

一种使测试更容易的方法是使用-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

如果条件不为真，则会引发错误。我知道这并不能解决你的错误，但让事情变得不那么模糊总是有助于调试。

- beer_monk

Answer 4

你没有为printtree()指定起始节点。你正确地定义了如何递归遍历你的树，但是调用printtree()时没有节点可供起始。尝试设置一个默认检查来查看是否传入了参数，如果没有，则从bintree的头节点开始。

你的倒数第二行打印None的原因是，在exists方法中，当找到与关键字相等的`p.item`时，你只写了一个"return"而不是"return True"。

- T.K.