时间戳

首页 > 解决方案 > 如何在二叉搜索树中对给定值下的所有节点求和？

python - 如何在二叉搜索树中对给定值下的所有节点求和？

问题描述

我的作业需要我对 BST 中给定值下的所有数字求和。但是，我不知道该怎么做。感谢任何帮助。

class BinarySearchTree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    def search(self, find_data):
        if self.data == find_data:
            return self
        elif find_data < self.data and self.left != None:
            return self.left.search(find_data)
        elif find_data > self.data and self.right != None:
            return self.right.search(find_data)
        else:
            return None 
    def get_left(self):
        return self.left
    def get_right(self):
        return self.right
    def set_left(self, tree):
        self.left = tree
    def set_right(self, tree):
        self.right = tree
    def set_data(self, data):
        self.data = data
    def get_data(self):
        return self.data

def create_new_bst(lst):
    #creates a new tree with root node 55, and then inserts all the
    #remaining values in order into the BST


def sum_beneath(t, value):
    # don't know how to do


t = create_new_bst([55, 24, 8, 51, 25, 72, 78])
result = sum_beneath(t, 72)
print('Sum beneath 72 =', result)# should show 'Sum beneath 72 = 78'

我对 BST 很陌生，所以我真的不知道如何开始和做这个问题。

def insert(self, new_data):#can I just call this function in 'create_new_bst'?
       if self.data:
            if new_data < self.data:
                if self.left is None:
                    self.left = BinarySearchTree(new_data)
                else:
                    self.left.insert(new_data)
            elif new_data > self.data:
                if self.right is None:
                    self.right = BinarySearchTree(new_data)
                else:
                    self.right.insert(new_data)
        else:
            self.data = data

标签： pythonpython-3.xbinary-search-tree

解决方案

好的，因为这是一个练习，我不会填写所有内容，但我会尝试让您了解应该如何完成它：

您需要以一种简单的方式创建树，您可以这样做：

def create_new_bst(lst):
    tree = BinarySearchTree(tree[0])
    # And then, using the insert method, which is correct, add your nodes in the tree
    return tree

首先，您需要找到带有根的您的子树72

# Replace the pass with the appropriate code

def find_subtree(tree, value):
    if value == tree.data: # This is found yeah !
         pass
    if value > tree.data: # Ok, this is not our data, we should look recursively in one of the children (I will not tell you which one). Maybe we can use find_subtree reccursively?
         pass
    if value < tree.data: # Same as above, but maybe we should look in the other child
         pass
    raise ValueError("Not found value " + str(value)) # Nothing has been found.

现在，您找到了带有 的树my_tree = find_subtree(t, 72)，您应该将左树（如果存在）和右树（如果存在）相加

def sum_beneath(t, value):
    my_tree = find_subtree(t, value)
    s = 0
    if my_tree.left is not None:
         s += my_tree.left.sum_tree()
    if my_tree.right is not None:
         s += my_tree.right.sum_tree()
    return s

让我们定义sum_tree方法（在类中）！:)

def sum_tree(self):
    ans =  self.data
    # Add the left sum reccursively
    # Add the right sum reccursively
    return ans

我希望这将有助于您理解 BST 的概念。如果您需要帮助，请不要犹豫发表评论

推荐阅读