如何计算二叉搜索树中节点的总和和总数？

Question

我正在尝试找出一种方法来计算 BST（二叉搜索树）中节点的总和和总数。我假设节点的值都是数字的。我制作了以下代码并尝试了不同的方法，但一切都会导致丢失根或类似的丢失。

class BinarySearchTree:
    def __init__(self, value=None):
        self.value = value
        if self.value:
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()
        else:
            self.left_child = None
            self.right_child = None

    def is_empty(self):
        return self.value is None

    def insert(self, value):
        if self.is_empty():
            self.value = value
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()

        elif value < self.value:
            self.left_child.insert(value)

        elif value > self.value:
            self.right_child.insert(value)

    def compute_sum(self):
        #Here I should make a function to compute the sum of all the node values in the BST. 
        return "Not Implemented"


    def compute_count(self):
        #Here I should make a function to compute the total number of nodes in the BST. 
        return "Not Implemented"

def main():
    my_tree = BinarySearchTree()

    my_tree.insert(2)
    my_tree.insert(4)
    my_tree.insert(6)
    my_tree.insert(8)
    my_tree.insert(10)

    print('sum:', my_tree.compute_sum())
    print('number of nodes:', my_tree.compute_count())

if __name__ == "__main__":
    main()

请不要恨(: 以前大家都是初学者

Answer 1

更新代码如下。

class BinarySearchTree:
    def __init__(self, value=None):
        self.value = value
        if self.value:
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()
        else:
            self.left_child = None
            self.right_child = None

    def is_empty(self):
        return self.value is None

    def insert(self, value):
        if self.is_empty():
            self.value = value
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()

        elif value < self.value:
            self.left_child.insert(value)

        elif value > self.value:
            self.right_child.insert(value)

    def compute_sum(self):
        ' compute the sum of all the node values in the BST '
        if self.value is None:
            return 0         # No nodes
        else:
            # current plus sum of child nodes
            return self.value + self.left_child.compute_sum() + self.right_child.compute_sum()


    def compute_count(self):
        ' compute the total number of nodes in the BST ' 
        if self.value is None:
            return 0  # No nodes
        else:
            # One for current plus count of child nodes
            return 1 + self.left_child.compute_count() + self.right_child.compute_count()

def main():
    my_tree = BinarySearchTree()

    my_tree.insert(2)
    my_tree.insert(4)
    my_tree.insert(6)
    my_tree.insert(8)
    my_tree.insert(10)

    print('sum:', my_tree.compute_sum())
    print('number of nodes:', my_tree.compute_count())

if __name__ == "__main__":
    main()

如何计算二叉搜索树中节点的总和和总数？

How to compute the sum and the total number of nodes in a Binary Search Tree?

python

python-requests

binary

sum

binary-search-tree