我一直在努力解决这个问题，而且我是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)I have been struggling with this problem for a while and I am a Python beginner when it comes to BST, so I would appreciate some help. I am dynamically adding elements from an (unsorted) array into BST. That part is fine, I know how to do that. The next step, proved to be impossible with my current skill set. As I am adding elements to the tree, I need to be able to find current rank of any element in the tree. I know there are subtleties in this problem, so I would need help to at least find the number of nodes that are below the given node in BST. For example, in this case, node 15 has nodes 10,5 and 13 below it, so the function will return 3. Here is my existing code [this is a problem from 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.现在，回到原来的问题，你必须找出左子树中的子项数。 只需在O（logN）时间找出该节点，然后打印numLeftChildren
时间复杂度：O（logN）
PS：我添加了另一个字段numRightChildren，如果您总是只想知道左子树中的节点数，则可以删除它。
You can go by this approach:
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.Now, come back to your original problem, You have to find out the number of children in left subtree. Just find out that node in O(logN) time and just print the numLeftChildren
Time Complexity: O(logN)
PS: I have added another field numRightChildren which you can remove if you are always interested in knowing the number of nodes in left subtree only.
更多推荐
发布评论