Wyświetlanie tytułów książek w kolejności alfabetycznej
W tym filmie poznałeś trzy sposoby implementacji przeszukiwania w głąb (depth first search) w drzewach binarnych: in-order, pre-order i post-order.
W poniższym drzewie BST przechowano tytuły kilku książek.
Drzewo zostało wstępnie załadowane do zmiennej bst (wiersz 15):
bst = CreateTree()
Czy potrafisz zastosować przeszukiwanie in-order tak, aby tytuły książek pojawiły się w kolejności alfabetycznej?
To ćwiczenie jest częścią kursu
Struktury danych i algorytmy w Pythonie
Instrukcje do ćwiczenia
- Sprawdź, czy
current_nodeistnieje. - Wywołaj funkcję
in_order()rekurencyjnie na odpowiedniej połowie drzewa. - Wyświetl wartość
current_node. - Wywołaj funkcję
in_order()rekurencyjnie na drugiej połowie drzewa.
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
class BinarySearchTree:
def __init__(self):
self.root = None
def in_order(self, current_node):
# Check if current_node exists
if ____:
# Call recursively with the appropriate half of the tree
self.in_order(current_node.____)
# Print the value of the current_node
print(____)
# Call recursively with the appropriate half of the tree
self.in_order(current_node.____)
bst = CreateTree()
bst.in_order(bst.root)