如何查找BST中的第k个最小节点？ （重新访问）

Question

昨天我问了一个类似的问题，但我从原始问题中发布的问题达到了不同的解决方案，我正在重新发布新代码。我没有跟踪每个节点的左右儿童数量。代码在某些情况下可以正常工作，但对于查找第6个元素的情况，它会失败。问题是我不知何故需要把树上的孩子数量。例如，对于节点5，我需要注意节点4的等级，我无法做到这一点。

这不是一项家庭作业，我正在准备面试，这是一个经典问题，我无法解决它。

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): 
     # initializes the root member 
     self.root = None 

    def addNode(self, data): 
     # creates a new node and returns it 
     return Node(data) 

    def insert(self, root, data): 
     # inserts a new data 
     if root == None: 
      # it there isn't any data 
      # adds it and returns 
      return self.addNode(data) 
     else: 
      # enters into the tree 
      if data <= root.data: 
       root.numLeftChildren += 1 
       # if the data is less than the stored one 
       # goes into the left-sub-tree 
       root.left = self.insert(root.left, data) 
      else: 
       # processes the right-sub-tree 
       root.numRightChildren += 1 
       root.right = self.insert(root.right, data) 
      return root 

    def getRankOfNumber(self, root, x, rank): 
     if root == None: 
      return 0 
     if rank == x: 
      return root.data 
     else: 
      if x > rank: 
       return self.getRankOfNumber(root.right, x, rank+1+root.right.numLeftChildren) 
      if x <= rank: 
       return self.getRankOfNumber(root.left, x, root.left.numLeftChildren+1) 


# main 
btree = BSTree() 
root = btree.addNode(13) 
btree.insert(root, 3) 
btree.insert(root, 14) 
btree.insert(root, 1) 
btree.insert(root, 4) 
btree.insert(root, 18) 
btree.insert(root, 2) 
btree.insert(root, 12) 
btree.insert(root, 10) 
btree.insert(root, 5) 
btree.insert(root, 11) 
btree.insert(root, 8) 
btree.insert(root, 7) 
btree.insert(root, 9) 
btree.insert(root, 6) 

print btree.getRankOfNumber(root, 8, rank=root.numLeftChildren+1) 

Answer 1

你有一个节点的排名。您需要找到其左侧或右侧孩子的排名。那么，节点和它的孩子之间有多少个节点？

 a 
    /\ 
/ \ 
    b  c 
/\ /\ 
W X Y Z 

这里是一个BST的例子。小写字母是节点;大写是子树。 a和b之间的节点数是X中的节点数。 a和c之间的节点数是Y中的节点数。因此，您可以计算排名b或c从排名a和大小X或Y。

rank(b) == rank(a) - size(X) - 1 
rank(c) == rank(a) + size(Y) + 1 

你有c公式，但错误b公式。