3

私と私の友人は、Python 3.1 でプログラミングを行う学校の仕事をしていて、非常に行き詰っています。二分木をプログラミングしていますが、文を作成する方法ですべてのノードを順番に出力したい場合を除いて、正常に動作しています (すべての単語が順番に並んでいます)。私たちはどうやって進めるか手がかりを求めてインターネット中を探しており、このささいなことに2時間ほど取り組んできました. アドバイス/ヘルプは素晴らしいでしょう。

私たちのプログラム/二分木:

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

また、最後から 2 番目の行では、「True」ではなく「None」が表示されますが、これは奇妙です。

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

テストを簡単にする 1 つの方法は、出力してコードを参照する代わりに -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 のヘッド ノードで開始されていないかどうかを確認してみてください。

最後から 2 行目に None が出力されている理由は、キーに等しい「p.item」を見つける場合に、exists メソッドで「return True」ではなく「return」があるためです。 .

于 2011-02-17T14:29:45.290 に答える