python - python二分探索木

Question

何らかの理由で、「検索」メソッドが機能しないようです。スコープの問題に関係していると思います... root.val はグローバルに更新されていないようです。AtributeError: 'int' object has no attribute 'val' というエラーメッセージが表示されます。現時点でのコードは次のとおりです。

class BinaryNode:
    def __init__(self, v):
        self.val = v
        self.leftChild = None
        self.rightChild = None
    def get(self):
        return self.val
    def set(self, v):
        self.val = v
    def getChildren(self):
        children = []
        if self.leftChild != None:
            children.append(self.leftChild)
        if self.rightChild != None:
            children.append(self.rightChild)
        return children

class Tree:
    def __init__(self):
        self.root = None
    def setRoot(self, node):
        self.root = node
    def size(self):
        if self.root == None:
            return 0
    def subtreeSize(node):
        return 1 + sum(subtreeSize(c) for c in node.getChildren())
        return subtreeSize(self.root)

class BinarySearchTree(Tree):
    def insert(self, val):
        self.insertNode(self.root, val)

    def insertNode(self, node, val):
        if node is None:
            self.setRoot(BinaryNode(val))
        elif val <= node.val:
            node.leftChild = insertNode(BinaryNode(val), val)
        elif val > node.val:
            node.rightChild = insertNode(BinaryNode(val), val)
        else:
            node.val = val


    def find(self, val):
        self.findNode(self.root, val)

    def findNode(self, node, val):
        if node is None:
            return False
        elif val == node.val:
            return True
        elif val < node.val:
            self.findNode(val, node.leftChild)
        else:
            self.findNode(val, node.rightChild)


if __name__ == "__main__":
    btree = BinarySearchTree()
    vals = [5]
    for v in vals:
        btree.insert(v)
    tests = [8, 5]
    for t in tests:
        print "find(%i) = %s" % (t, ("True" if btree.find(t) else "False"))

score 5 · Accepted Answer

あなたのfindNode()方法には2つの問題があります：

再帰的に呼び出すときに引数と引数を交換しました。これにより、コードはノードではなく整数値を検索しようとします。nodeval.val
再帰呼び出しの結果を返すのを忘れました。

修正された方法:

def find(self, val):
    return self.findNode(self.root, val)

def findNode(self, node, val):
    if node is None:
        return False
    elif val == node.val:
        return True
    elif val < node.val:
        return self.findNode(node.leftChild, val)
    else:
        return self.findNode(node.rightChild, val)

次の問題はinsertNode方法です。insertNode()その中でグローバル関数を呼び出そうとします。それはおそらくself.insertNode()代わりになるはずです。ただし、そのメソッドには戻り値がないnode.leftChildため、 ornode.rightChildを設定することになりますNone。

挿入ポイントの検索を再帰呼び出しに渡すだけで、戻り値を使用する必要はありません。

def insert(self, val):
    if self.root is None:
        self.setRoot(BinaryNode(val))
    else:
        self.insertNode(self.root, val)

def insertNode(self, node, val):
    if val <= node.val:
        if node.leftChild:
            self.insertNode(node.leftChild, val)
        else:
            node.leftChild = BinaryNode(val)
    elif val > node.val:
        if node.rightChild:
            self.insertNode(node.rightChild, val)
        else:
            node.rightChild = BinaryNode(val)

これらの変更により、簡単なテストで以下が出力されます。

find(8) = False
find(5) = True

score 0 · Accepted Answer

問題の 1 つは、ステートメントfindNode()が欠落していることです。returnの

    elif val < node.val:
        self.findNode(val, node.leftChild)
    else:
        self.findNode(val, node.rightChild)

読むべき

    elif val < node.val:
        return self.findNode(val, node.leftChild)
    else:
        return self.findNode(val, node.rightChild)

にも同様の問題がありinsertNode()ます。

python - python二分探索木

2 に答える 2

Related

Reference