2

私はしばらくこの問題に苦労しており、BSTに関してはPythonの初心者なので、助けていただければ幸いです。(ソートされていない) 配列の要素を BST に動的に追加しています。その部分は結構です、私はそれを行う方法を知っています。次のステップは、私の現在のスキル セットでは不可能であることが判明しました。ツリーに要素を追加しているので、ツリー内の任意の要素の現在のランクを見つけることができる必要があります。この問題には微妙な点があることを知っているので、少なくとも BST で特定のノードの下にあるノードの数を見つけるには助けが必要です。たとえば、この場合、ノード 15 にはその下にノード 10、5、および 13 があるため、関数は 3 を返します。これが私の既存のコードです [これは、コーディングのインタビュー、第 11 章のクラックの問題です]。

class Node:

"""docstring for Node"""
def __init__(self, data):
    self.data = data
    self.left=None
    self.right=None
    self.numLeftChildren=0
    self.numRightChildren=0
class BSTree:
    def __init__(self):
        self.root = None

    def addNode(self, data):
        return Node(data)

    def insert(self, root, data):
        if root == None:
            return self.addNode(data)
        else:
            if data <= root.data:
                root.numLeftChildren+=1
                root.left = self.insert(root.left, data)
            else:
                root.numRightChildren+=1
                root.right = self.insert(root.right, data)
            return root 
    def getRankOfNumber(self,root,x):
        if root==None:
            return 0
        else:
            if x>root.data :
                return self.getRankOfNumber(root.right,x)+root.numLeftChildren+1
            elif root.data==x:
                return root.numLeftChildren
            else:
                return self.getRankOfNumber(root.left,x)   
BTree=BSTree()
root=BTree.addNode(20)
BTree.insert(root,25)
BTree.insert(root,15)
BTree.insert(root,10)
BTree.insert(root,5)
BTree.insert(root,13)
BTree.insert(root,23)
4

4 に答える 4

1

BST を変更して、各ノードの下にノードの数を含めることができます。

または、最小から最大まで従来の BST を反復処理し、必要な値のノードが見つかったらカウントを停止することもできます。

于 2013-11-13T05:01:19.990 に答える