python - 如何使用 python BST 实现 'range'

Question

我现在的代码允许我搜索特定的节点，我想编辑它以便我可以在数字范围内搜索。例如，我有一个苹果的价目表，我想将所有苹果添加到价格在 2-4 美元或类似价格之间的列表/字典中。

这是我当前的代码

def valueOf(self, key):
    node = self._bstSearch(self._root, key)
    assert node is not None, "Invalid map key."
    return node.value

def _bstSearch(self, subtree, target):
    if subtree is None:
        return None
    elif target < subtree.key:
        return self._bstSearch( subtree.left, target)
    elif target > subtree.key:
        return self._bstSearch(subtree.right, target)
    else:    
        return subtree

我认为我应该编辑目标，将其从单个项目搜索更改为范围项目搜索，但我不是 100% 确定如何操作

Answer 1

使用递归中序遍历:

def range(self, a, b):
    return self._traverse_range(self._root, a, b)

def _traverse_range(self, subtree, a, b, cumresult=None):
    if subtree is None:
        return

    # Cumulative variable.
    if cumresult is None:
        cumresult = []

    # Traverse LEFT subtree if it is possible to find values in required range there.
    if subtree.key > a:
        self._traverse_range(subtree.left, a, b, cumresult)

    # Push VALUE if it is in our range.
    if a <= subtree.key <= b:  # Change to strict "< b" to act like python's range
        cumresult.append(subtree.key)

    # Traverse RIGHT subtree if it is possible to find values in required range there.
    if subtree.key < b:
        self._traverse_range(subtree.right, a, b, cumresult)

    return cumresult