时间戳

首页 > 解决方案 > 从二叉搜索树计算范围

python - 从二叉搜索树计算范围

问题描述

有没有更合适的方法从这个二叉搜索树中检索一个范围（最高和最低数字之间的差异）？我尝试返回 range 函数中的最大值和最小值之间的差异，但没有任何效果。

这是我的代码：

# %load bst.py


class Node:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        # self.parent = None


class BST:
    def __init__(self):
        self.root = None  # the root of the tree

    def insert(self, new_node):
        if self.root is None:  # is the tree empty?
            self.root = new_node  # if yes, new node becomes the root
            return
        self.insertNode(self.root, new_node)

    def insertNode(self, root, new_node):
        if new_node.data > root.data:
            if root.right_child is not None:  # does right child exist?
                self.insertNode(root.right_child, new_node)
            else:
                root.right_child = new_node  # new node becomes right child
                return
        else:  # case where new_node.data <= root.data
            if root.left_child is not None:  # does left child exist?
                self.insertNode(root.left_child, new_node)
            else:  # left child does not exist
                root.left_child = new_node

    # assignment starts here
    def postOrder(self, node):
        if node.left_child is not None:  # does the left child exist?
            self.postOrder(node.left_child)
        if node.right_child is not None:  # checking if right child exists
            self.postOrder(node.right_child)
        print(node.data)  # visit the node

    # finding maxmum of the array
    def findMax(self, node):
        if node.right_child is not None:  # does the right child exist?
            return self.findMax(node.right_child)
        print(node.data)  # visit the node

    # finding minmum of the array
    def findMin(self, node):
        if node.left_child is not None:  # check if left child exist
            return self.findMin(node.left_child)
        print(node.data)  # visit the node

    # finding range
    def range(numbers=[8, 87]):
        import statistics

        statistics.range
        return max(numbers) - min(numbers)


my_bst = BST()
l = [31, 67, 26, 29, 50, 15, 58, 8, 49, 87, 20]
for n in l:
    n1 = Node(n)
    my_bst.insert(n1)

print('maxmum of the array is')
my_bst.findMax(my_bst.root)
print('minmum of the array is')
my_bst.findMin(my_bst.root)
print('postOrdering the array follows')
my_bst.postOrder(my_bst.root)
print('range is')
my_bst.range(my_bst.root)

我已经尝试过，但我不断收到以下错误：

Traceback (most recent call last):
  File "main.py", line 76, in <module>
    my_bst.range(my_bst.root)
TypeError: range() takes from 0 to 1 positional arguments but 2 were given`

标签： pythonpython-3.x

解决方案

range函数应该是一个方法，所以你需要将self参数定义为函数的第一个参数，像这样：

class BST:

    [...]

    # finding range
    def range(self, numbers=[8, 87]):
        import statistics

        statistics.range
        return max(numbers) - min(numbers)

请注意，具有可变参数不是一个好习惯，因为它不在函数的本地范围内。您可以按如下方式解决此问题：

    def range(self, numbers=None):
        if numbers is None:
            numbers = [8, 87]
        import statistics

        statistics.range
        return max(numbers) - min(numbers)

简而言之，你也可以这样写：

    # finding range
    def range(self, numbers=None):
        numbers = numbers or [8, 87]
        import statistics

        statistics.range
        return max(numbers) - min(numbers)

最好statistics全局导入，如下所示：

import statistics


class BST:

    [...]

    # finding range
    def range(self, numbers=None):
        numbers = numbers or [8, 87]

        statistics.range
        return max(numbers) - min(numbers)

请注意，statistics.range没有调用该函数是因为您忘记了括号（和参数）。所以这是死代码。

在您的主程序中，您尝试使用作为实例my_bst.range()的 a进行调用。因此，在计算a时会出现错误：my_bst.rootNodemax/minNode

Traceback (most recent call last):
  File "...", line 75, in <module>
    my_bst.range(my_bst.root)
  File "...", line 59, in range
    return max(numbers) - min(numbers)
TypeError: 'Node' object is not iterable

您需要自己开发算法。

推荐阅读