Как реализовать «диапазон» с python BST

Мой код в данный момент позволяет мне искать определенный узел, я бы хотел его отредактировать, чтобы я мог выполнять поиск в диапазоне чисел. Например, у меня есть прейскурант яблок, и я хотел бы добавить все яблоки в список / словарь, стоимость которого составляет от $ 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%, как

python,binary-search-tree,

1

Ответов: 1


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
питон, двоично-поиск-дерево,
Похожие вопросы