#python #recursion #tree #binary-search-tree
#питон #рекурсия #дерево #двоичный поиск-дерево
Вопрос:
Я хочу вернуть список в отсортированном порядке, при условии, что я дал старт/стоп значение для метода. Например, если start=2 и конца=8, тогда я хочу вернуть список в пределах этого диапазона, соответственно, значения по британскому летнему времени в отсортированном порядке.
Поскольку я хочу, чтобы это было в порядке и не разрешается размещать отсортировать список после вызова метода, я думаю, что я должен пройти через по британскому летнему времени в порядок обхода. когда я проверить мою реализацию, первый doctest возвращение [7,9,11] вместо [5,7,9,11], как предполагалось.
from __future__ import annotations
from typing import Any, List, Optional, Tuple
class BinarySearchTree:
"""Binary Search Tree class.
# === Representation Invariants ===
# - If self._root is None, then so are self._left and self._right.
# This represents an empty BST.
# - If self._root is not None, then self._left and self._right
# are BinarySearchTrees.
# - (BST Property) If self is not empty, then
# all items in self._left are <= self._root, and
# all items in self._right are >= self._root.
"""
def __init__(self, root: Optional[Any]) -> None:
"""Initialize a new BST containing only the given root value.
If <root> is None, initialize an empty tree.
"""
if root is None:
self._root = None
self._left = None
self._right = None
else:
self._root = root
self._left = BinarySearchTree(None)
self._right = BinarySearchTree(None)
def is_empty(self) -> bool:
"""Return True if this BST is empty.
>>> bst = BinarySearchTree(None)
>>> bst.is_empty()
True
>>> bst = BinarySearchTree(10)
>>> bst.is_empty()
False
"""
return self._root is None
def items_in_range(self, start: Any, end: Any) -> List:
"""Return the items in this BST between <start> and <end>, inclusive.
Precondition: all items in this BST can be compared with <start> and
<end>.
The items should be returned in sorted order.
As usual, use the BST property to minimize the number of recursive
calls.
>>> bst = BinarySearchTree(7)
>>> left = BinarySearchTree(3)
>>> left._left = BinarySearchTree(2)
>>> left._right = BinarySearchTree(5)
>>> right = BinarySearchTree(11)
>>> right._left = BinarySearchTree(9)
>>> right._right = BinarySearchTree(13)
>>> bst._left = left
>>> bst._right = right
>>> bst.items_in_range(4, 11)
[5, 7, 9, 11]
>>> bst.items_in_range(10, 13)
[11, 13]
"""
if self.is_empty():
return []
else:
#use helper here
if end >= self._root >= start:
return (self._left._helper_items_in_range_left(start)
[self._root]
self._right._helper_item_in_range_right(end))
elif self._root > end:
return self._left.items_in_range(start,end)
elif self._root < start:
return self._right.items_in_range(start,end)
else:
pass
def _helper_items_in_range_left(self, start):
if self.is_empty():
return []
elif self._root < start:
return []
else:
return self._left._helper_items_in_range_left(start)
[self._root] self._right._helper_items_in_range_left(start)
def _helper_item_in_range_right(self, end):
if self.is_empty():
return []
elif self._root > end:
return []
else:
return self._left._helper_item_in_range_right(end) [self._root]
self._right._helper_item_in_range_right(end)
Комментарии:
1. Пожалуйста, измените свой код таким образом, мы можем проверить это.
Ответ №1:
Вы могли бы использовать что-то вроде этого. Обратите внимание, что я тестировал его, используя другую структуру дерева.
import itertools
from collections import deque
class BSTIterator(object):
def __init__(self, root):
# Constructor takes in a tree root
self.stack = deque()
self._get_min(root)
def _get_min(self, root):
# We need to create our stack, i.e. dive down the left
curr = root
while curr != None:
self.stack.append(curr)
curr = curr.left
def __iter__(self): # Return self as the iterator
return self
def __next__(self): # Every time `next` is called return our data.
try:
curr = self.stack.pop()
self._get_min(curr.right)
return curr.data
except IndexError:
raise StopIteration
Тип дерева используется:
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
Протестировано с:
root = Node(8)
root.insert(3)
root.insert(10)
root.insert(1)
root.insert(7)
root.insert(12)
root.insert(121)
root.insert(23)
root.insert(19)
root.insert(9)
b_iter = BSTIterator(root)
# root.print_tree()
# Since we now have an iterator we can for loop over it
# such as
# y = [x for x in b_iter]
# or we can slice it like
y = [x for x in itertools.islice(b_iter, 2, 5)]
print(y)
С принтами:
[7, 8, 9]