3

我和我的朋友正在做一些使用 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”，这很奇怪。

4

4 回答 4

2

要打印二叉树，如果要打印叶子，只需打印值；否则，您先打印左孩子，然后再打印右孩子。

def print_tree(tree):
    if tree:
        print tree.value
        print_tree(tree.left)
        print_tree(tree.right)
于 2011-02-17T14:25:02.453 回答
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)。

于 2011-02-17T13:58:26.860 回答
0

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

如果其条件不成立，则会引发错误。我知道这并不能解决您的错误，但让事情变得不那么模棱两可总是有助于调试。

于 2011-02-17T13:48:29.410 回答
0

您没有为 printtree() 指定起始案例。您正在定义如何正确地通过您的树进行递归，但是您对 printtree() 的调用没有节点可以开始。尝试设置默认检查以查看是否传入了参数，以及是否没有从 bintree 的头节点开始。

您的倒数第二行打印 None 的原因是，在您的 exists 方法中，您只有一个“return”，而不是“return True”，以便找到一个等于 key 的“p.item” .

于 2011-02-17T14:29:45.290 回答