用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 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”，这也很奇怪。

Answer 1

你没有为printtree()指定一个起始节点。你已经定义了如何正确地遍历你的树，但你调用printtree()时没有指定一个起始节点。试着设置一个默认检查，看看是否传入了参数，如果没有，就从二叉树的头节点开始。

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

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

Answer 3

要打印一个二叉树，如果你要打印的是叶子节点（也就是没有子节点的节点），那你只需要打印它的值；如果不是叶子节点，那就先打印左边的孩子节点，然后再打印右边的孩子节点。

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