python之在 BST 中查找小于给定元素的元素数

我已经为这个问题苦苦挣扎了一段时间，而且我是 BST 的 Python 初学者，所以我很感激能得到一些帮助。我正在将(未排序的)数组中的元素动态添加到 BST 中。那部分很好，我知道该怎么做。下一步，以我目前的技能组合证明是不可能的。当我向树中添加元素时，我需要能够找到树中任何元素的当前等级。我知道这个问题有一些微妙之处，所以我需要帮助至少找到 BST 中给定节点下方的节点数。例如，在这种情况下，节点 15 下面有节点 10,5 和 13，因此该函数将返回 3。这是我现有的代码 [这是来自 Cracking the coding interview, chapter 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) 

请您参考如下方法:

你可以通过这种方法:

1. Have 2 more fields in each node numLeftChildren and numRightChildren. 
2. Initialize both of them to 0 when you create a new node. 
3. At the time of insertion, you make a comparison if the newly added node's 
key is less than root's key than you increment, root's numLeftChildren and 
call recursion on root's left child with the new node. 
4. Do Same thing if new node's key is greater than root's key. 

现在，回到你原来的问题，你必须找出左子树中 child 的数量。只需在 O(logN) 时间内找出该节点并打印 numLeftChildren

时间复杂度:O(logN)

PS:我添加了另一个字段 numRightChildren，如果您总是只想知道左子树中的节点数，您可以将其删除。