Dając drzewo binarne, napisz iteracyjne i rekursywne rozwiązanie do przemierzania drzewa używając inorder traversal w C++, Javie i Pythonie.
W przeciwieństwie do list połączonych, tablic jednowymiarowych i innych liniowych struktur danych, które są przemierzane w kolejności liniowej, drzewa mogą być przemierzane na wiele sposobów w kolejności depth-first (preorder, inorder i postorder) lub breadth-first (level order traversal). Poza tymi podstawowymi traversalami, możliwe są różne bardziej złożone lub hybrydowe schematy, takie jak wyszukiwanie z ograniczeniem głębokości, jak iteracyjne pogłębianie wyszukiwania depth-first. W tym poście, inorder tree traversal jest omówiony szczegółowo.
Traversing a tree involves iterating over all nodes in some manner. Ponieważ drzewo nie jest liniową strukturą danych, może istnieć więcej niż jeden możliwy następny węzeł od danego węzła, więc niektóre węzły muszą być odroczone, tj. przechowywane w jakiś sposób do późniejszego odwiedzenia. Traversal może być wykonany iteracyjnie, gdzie odroczone węzły są przechowywane na stosie, lub może być wykonany przez rekurencję, gdzie odroczone węzły są przechowywane niejawnie w stosie wywołań.
Dla traversing (niepuste) drzewo binarne w sposób inorder, musimy zrobić te trzy rzeczy dla każdego węzła n zaczynając od korzenia drzewa:
(L) Rekursywnie trawersować jego lewy subtree. Gdy ten krok się zakończy, jesteśmy znowu w n.(N) Przetwarzaj n sam w sobie.(R) Rekursywnie przemierzaj jego prawe poddrzewo. Po zakończeniu tego kroku jesteśmy ponownie w n.W normalnym inorder traversal, odwiedzamy lewe poddrzewo przed prawym poddrzewem. Jeśli odwiedzimy prawy poddrzewo przed odwiedzeniem lewego poddrzewa, jest to określane jako odwrotne inorder traversal.
Jak widzimy, przed przetworzeniem dowolnego węzła najpierw przetwarzane jest lewe poddrzewo, następnie węzeł, a prawe poddrzewo jest przetwarzane na końcu. Operacje te mogą być zdefiniowane rekurencyjnie dla każdego węzła. Implementacja rekurencyjna jest określana jako Depth-first search (DFS), ponieważ drzewo wyszukiwania jest pogłębiane tak bardzo, jak to możliwe na każdym dziecku przed przejściem do następnego rodzeństwa.
Poniżej znajduje się program w języku C++, Java i Python, który to demonstruje:
Iteracyjna implementacja –
Aby przekształcić powyższą procedurę rekurencyjną w iteracyjną, potrzebujemy jawnego stosu. Poniżej znajduje się prosty algorytm iteracyjny oparty na stosie, aby wykonać inorder traversal.
iterativeInorder(node)
Algorytm ten można zaimplementować w następujący sposób w językach C++, Java i Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// Funkcja iteracyjna funkcja do wykonania inorder traversal na drzewie
void inorderIterative(Node *root)
{
// utwórz pusty stos
stos<Node*> stos;
// rozpoczynamy od węzła głównego (ustawiamy węzeł bieżący na węzeł główny)
Node *curr = root;
// jeśli węzeł bieżący jest null i stos jest również pusty, to kończymy
while (!stack.empty() || curr != nullptr)
{
// jeśli bieżący węzeł istnieje, wepchnij go na stos (odroczenie)
// i przejdź do jego lewego dziecka
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// w przeciwnym razie, jeśli bieżący węzeł jest null, pop element ze stosu,
// wydrukuj go, a na koniec ustaw bieżący węzeł na jego prawe dziecko
curr = stack.top();
stack.pop();
cout << curr->data << ” „;
curr = curr->right;
}
}
}
|
Download Run Complete Code
.
Java
|
1
2
3
. 4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// Iteracyjna funkcja do wykonania inorder traversal na drzewie
public static void inorderIterative(TreeNode root)
{
// utwórz pusty stos
Stack<TreeNode> stack = new Stack();
// rozpocznij od węzła głównego (ustaw bieżący węzeł na węzeł główny)
TreeNode curr = root;
// jeśli bieżący węzeł jest pusty i stos również jest pusty, to kończymy
while (!stack.empty() || curr != null)
{
// jeśli bieżący węzeł istnieje, wepchnij go na stos (odroczenie)
// i przejdź do jego lewego dziecka
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// w przeciwnym razie, jeśli bieżący węzeł jest null, pop element ze stosu,
// wydrukuj go, a na koniec ustaw bieżący węzeł na jego prawe dziecko
curr = stack.pop();
System.out.print(curr.data + ” „);
curr = curr.right;
}
}
}
|
Download Run Complete Code
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Funkcja iteracyjna do wykonywania inorder traversal na drzewie
def inorderIterative(root):
# create an empty stack
stack = deque()
# start from the root node (set current node to the root node)
curr = root
# if the current node is None and the stack is also empty, kończymy
while stack or curr:
# jeśli bieżący węzeł istnieje, wepchnij go na stos (odroczenie)
# i przejdź do jego lewego dziecka
if curr:
stack.append(curr)
curr = curr.left
else:
# inaczej, jeśli bieżący węzeł jest None, pop element ze stosu,
# wydrukuj go, a na koniec ustaw bieżący węzeł na jego prawe dziecko
curr = stack.pop()
print(curr.data, end=’ ’)
curr = curr.right
|
Download Run Complete Code
Złożoność czasowa powyższych rozwiązań wynosi O(n), gdzie n jest całkowitą liczbą węzłów w drzewie binarnym. Złożoność przestrzenna programu jest O(n), ponieważ wymagana przestrzeń jest proporcjonalna do wysokości drzewa, która może być równa całkowitej liczbie węzłów w drzewie w najgorszym przypadku dla drzew pochylonych.
.