从二进制搜索T计算范围

Question

有没有更合适的方法从这个二叉搜索树中检索范围（最高值和最低值之间的差值）？我尝试返回最大值和；范围函数中的最小值，但不起作用

这是我的密码：

# %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`

Answer 1

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.root实例调用my_bst.range()。因此，在计算Node上的max/min时会出错：

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

你需要自己开发你的算法

Answer 2

你的设计没有多大意义。之所以需要一个单独的BST类，是为了在不依赖递归的树上编写方法。如果您要依赖递归，那么只需要一个Node类就更有意义了，因为每个节点本身就是一个二叉树

下面是我将如何重写findMin、findMax和range的BST方法

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
    def insert(self, value):
        if self.root is None:
            self.root = Node(value) 
        else:
            curr_node = self.root
            while True:
                if value < curr_node.data:
                    if curr_node.left is None:
                        curr_node.left = Node(value)
                        return
                    else:
                        curr_node = curr_node.left
                elif value > curr_node.data:
                    if curr_node.right is None:
                        curr_node.right = Node(value)
                        return
                    else:
                        curr_node = curr_node.right
                else:
                    return
    def min(self):
        if self.root is None:
            raise TypeError("Empty Tree")
        curr_node = self.root
        while curr_node.left is not None:
            curr_node = curr_node.left
        return curr_node.data
    def max(self):
        if self.root is None:
            raise TypeError("Empty Tree")
        curr_node = self.root
        while curr_node.right is not None:
            curr_node = curr_node.right
        return curr_node.data
    def range(self):
        return self.max() - self.min()


my_bst = BST()
l = [31, 67, 26, 29, 50, 15, 58, 8, 49, 87, 20]
for v in l:
    my_bst.insert(v)
 print(my_bst.range())  # 79