2

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

你可以通过这种方法去：

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，如果您总是对仅知道左子树中的节点数感兴趣，可以将其删除。

于 2013-11-13T05:13:09.513 回答
0

您可以通过仅使用Node类的实例来简化代码，因为您的BSTree实例无论如何都在根节点上运行。另一个优化可能是不将重复值表示为单独的节点，而是使用键出现的计数器：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.num_left_children = 0
        self.occurrences = 1

    def insert(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
            self.num_left_children += 1
        elif data > self.data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)
        else:
            self.occurrences += 1

    def get_rank(self, data):
        if data < self.data:
            return self.left.get_rank(data)
        elif data > self.data:
            return (self.occurrences + self.num_left_children +
                    self.right.get_rank(data))
        else:
            return self.num_left_children

演示：

root = Node(20)
root.insert(25)
root.insert(15)
root.insert(10)
root.insert(10)
root.insert(5)
root.insert(13)
root.insert(23)

print(root.get_rank(15))  # 4
于 2018-12-25T20:04:57.880 回答
-1

您可以使用以下函数查找树中的节点数（包括根）。

def countNodes(self, root):
    if root == None:
        return 0
    else
        return (1 + countNodes(root.left) + countNodes(root.right));

要查找位于 下方的节点数，请从函数返回的值中root减去。1我认为这将帮助您开始解决问题。

您的代码将如下所示：

class Node: """docstring for Node""" def init (self, data): self.data = data self.left=None self.right=None self.depth=0

类 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.left = self.insert(root.left, data)
        else:
            root.right = self.insert(root.right, data)
        return root

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) BTree.insert(root,23)

numLeft = countNodes(root->left); numRight = countNodes(root->right); numChildren = numLeft + numRight;

于 2013-11-13T05:11:20.243 回答