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 回答