1

Python を使用して BST を実装しましたが、要素をツリーに追加するときにいくつかのエラーが発生します。

class Node:
    def __init__(self,word,meaning):
        self.left=None
        self.right=None
        self.word=word
        self.meaning=meaning



class BST:
    def __init__(self,word,meaning):
        self.root=Node(word,meaning)

    def add_word(self,word,meaning):
        if(self.root.word==None):
            self.root.word=word
            self.root.meaning=meaning
            return "Create root"

        else:
            current=self.root
            while(1):
                if(word<current.word):
                    if(current.left):
                        self.add_word(word,meaning)
                    else:
                        current.left=Node(word,meaning)
                        break
                elif(word>current.word):
                    if(current.right):
                        self.add_word(word,meaning)
                    else:
                        current.right=Node(word,meaning)
                        break
                else:
                    break

    def in_order(self,node):
        if(node!=None):
            self.in_order(node.root.left)
            print(node.root.word,node.root.meaning)
            self.in_order(node.root.right)
4

2 に答える 2

1

これはどうですか？ 


def add_word(self, word, meaning):
    self._add_word(self.root, word, meaning)



def _add_word(self, node, word, meaning):
    if node is None:
        node = Node(word, meaning)
        return
    if word < node.word: self._add_word(node.left, word, meaning)
    elif word > node.word: self._add_word(node.right, word, meaning)

于 2013-09-24T01:37:01.083 に答える
0

このメソッドは、操作対象のノードを示す引数がないため、再帰関数として機能しませadd_wordん。self.add_word内部から(変更されていない引数を使用して)呼び出すadd_wordと、再帰制限まで実行されます。

再帰を行う代わりに、 の値を変更するだけですcurrent:

def add_word(self,word,meaning):
    if(self.root.word==None):
        self.root.word=word
        self.root.meaning=meaning
        return "Create root"

    else:
        current=self.root
        while(1):
            if(word<current.word):
                if(current.left):
                    current = current.left # changed here!
                else:
                    current.left = Node(word,meaning)
                    break
            elif(word>current.word):
                if(current.right):
                    current = current.right # and here too!
                else:
                    current.right = Node(word,meaning)
                    break
            else:     # you might want to raise an exception or something here
                break # since this branch indicates that the word alread exists

メソッドにも問題があります。これは値in_orderを期待していnodeますが、その属性にアクセスしようとします(インスタンスの場合は機能しrootません)。属性を持つ唯一のオブジェクトは BST 自体なので、必要なのは 、 などだけです。nodeNoderootnode.leftnode.right

再帰を開始するには、node引数をオプションにし、デフォルト値をセンチネルにして、関数でセンチネルを取得する場合に設定nodeする必要があります。self.root

_sentinel = object()
def in_order(self, node=_sentinel):
    if(node is not None):
        if node == BST._sentinel:
            node = self.root
        self.in_order(node.left)
        print(node.word, node.meaning)
        self.in_order(node.right)
于 2013-09-24T01:39:38.097 に答える