Schreiben Sie für einen binären Baum eine iterative und rekursive Lösung, um den Baum mit Inorder Traversal in C++, Java und Python zu durchlaufen.
Im Gegensatz zu verknüpften Listen, eindimensionalen Arrays und anderen linearen Datenstrukturen, die in linearer Reihenfolge durchlaufen werden, können Bäume auf mehrere Arten in der Tiefe (preorder, inorder und postorder) oder in der Breite (level order traversal) durchlaufen werden. Neben diesen grundlegenden Traversalen sind verschiedene komplexere oder hybride Schemata möglich, wie z. B. tiefenbegrenzte Suchen wie die iterative Vertiefung der tiefenersten Suche. In diesem Beitrag wird das Traversieren von Bäumen in der Reihenfolge im Detail besprochen.
Beim Traversieren eines Baums werden alle Knoten auf irgendeine Weise durchlaufen. Da der Baum keine lineare Datenstruktur ist, kann es mehr als einen möglichen nächsten Knoten von einem gegebenen Knoten geben, so dass einige Knoten zurückgestellt werden müssen, d.h. auf irgendeine Weise für einen späteren Besuch gespeichert werden. Die Durchquerung kann iterativ erfolgen, wobei die zurückgestellten Knoten im Stapel gespeichert werden, oder sie kann durch Rekursion erfolgen, wobei die zurückgestellten Knoten implizit im Aufrufstapel gespeichert werden.
Um einen (nicht leeren) Binärbaum in geordneter Weise zu durchqueren, müssen wir diese drei Dinge für jeden Knoten n ausgehend von der Wurzel des Baums tun:
(L) Rekursiv seinen linken Teilbaum durchqueren. Wenn dieser Schritt beendet ist, sind wir wieder bei n.(N) Bearbeite n selbst.(R) Rekursiv seinen rechten Teilbaum durchqueren. Wenn dieser Schritt beendet ist, sind wir wieder bei n.Beim normalen Traversieren in Reihenfolge besuchen wir den linken Teilbaum vor dem rechten Teilbaum. Wenn wir den rechten Teilbaum besuchen, bevor wir den linken Teilbaum besuchen, nennt man das reverse inorder traversal.
Wie wir sehen, wird vor der Verarbeitung eines Knotens zuerst der linke Teilbaum verarbeitet, dann der Knoten und zuletzt der rechte Teilbaum. Diese Operationen können rekursiv für jeden Knoten definiert werden. Die rekursive Implementierung wird als Depth-first search (DFS) bezeichnet, da der Suchbaum bei jedem Kind so tief wie möglich vertieft wird, bevor zum nächsten Geschwisterkind übergegangen wird.
Nachfolgend finden Sie das C++-, Java- und Python-Programm, das dies demonstriert:
Iterative Implementierung –
Um das obige rekursive Verfahren in ein iteratives umzuwandeln, benötigen wir einen expliziten Stack. Nachfolgend ist ein einfacher stapelbasierter iterativer Algorithmus zur Durchführung einer inorder traversal.
iterativeInorder(node)
Der Algorithmus kann wie folgt in C++, Java und Python implementiert werden:
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
|
// Iterative Funktion zur Durchführung von Inorder-Traversal auf dem Baum
void inorderIterative(Node *root)
{
// Erstellen eines leeren Stapels
stack<Node*> stack;
// Beginne mit dem Wurzelknoten (setze aktuellen Knoten auf den Wurzelknoten)
Knoten *curr = Wurzel;
// wenn der aktuelle Knoten null ist und der Stapel ebenfalls leer ist, sind wir fertig
while (!stack.empty() || curr != nullptr)
{
// wenn der aktuelle Knoten existiert, schiebe ihn in den Stapel (verschiebe ihn)
// und gehe zu seinem linken Kind
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// otherwise, if the current node is null, pop an element from the stack,
// print it, and finally set the current node to its right child
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
|
// Iterativ Funktion zum Durchlaufen des Baums in Reihenfolge
public static void inorderIterative(TreeNode root)
{
// Erstellen eines leeren Stacks
Stack<TreeNode> stack = new Stack();
// Beginnen Sie mit dem Wurzelknoten (setzen Sie den aktuellen Knoten auf den Wurzelknoten)
TreeNode curr = root;
// wenn der aktuelle Knoten null ist und der Stapel ebenfalls leer ist, sind wir fertig
while (!stack.empty() || curr != null)
{
// wenn der aktuelle Knoten existiert, schiebe ihn in den Stapel (verschiebe ihn)
// und gehe zu seinem linken Kind
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// otherwise, if the current node is null, pop an element from the stack,
// print it, and finally set the current node to its right child
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
|
# Iterative Funktion zur Durchführung von Inorder-Traversal auf dem Baum
def inorderIterative(root):
# Erstellen eines leeren Stapels
Stapel = deque()
# Starten vom Wurzelknoten (aktuellen Knoten auf den Wurzelknoten setzen)
curr = root
# wenn der aktuelle Knoten None ist und der Stapel ebenfalls leer ist, sind wir fertig
while stack oder curr:
# wenn der aktuelle Knoten existiert, schiebe ihn in den Stapel (verschiebe ihn)
# und gehe zu seinem linken Kind
if curr:
stack.append(curr)
curr = curr.left
else:
# andernfalls, wenn der aktuelle Knoten keiner ist, ein Element aus dem Stapel herausholen,
# drucken und schließlich den aktuellen Knoten auf sein rechtes Kind setzen
curr = stack.pop()
print(curr.data, end=‘ ‚)
curr = curr.right
|
Download Run Complete Code
Die Zeitkomplexität der obigen Lösungen ist O(n), wobei n die Gesamtzahl der Knoten im binären Baum ist. Die Raumkomplexität des Programms ist O(n), da der benötigte Platz proportional zur Höhe des Baums ist, die im schlimmsten Fall bei schiefen Bäumen gleich der Gesamtzahl der Knoten im Baum sein kann.