logo

TechCodeview

Baumdurchquerungstechniken – Tutorials zu Datenstruktur und Algorithmen

Baumdurchquerungstechniken umfassen verschiedene Möglichkeiten, alle Knoten des Baums zu besuchen. Im Gegensatz zu linearen Datenstrukturen (Array, verknüpfte Liste, Warteschlangen, Stapel usw.), die nur eine logische Möglichkeit haben, sie zu durchlaufen, können Bäume auf unterschiedliche Weise durchlaufen werden. In diesem Artikel besprechen wir alle Baumdurchquerungstechniken und ihre Verwendung.



Inhaltsverzeichnis

TCP-IP-Modell

Bedeutung der Baumdurchquerung:

Baumdurchquerung bezieht sich auf den Prozess, jeden Knoten des Baums genau einmal in einer bestimmten Reihenfolge zu besuchen oder darauf zuzugreifen. Baumdurchquerungsalgorithmen helfen uns, alle Knoten des Baums zu besuchen und zu verarbeiten. Da es sich bei einem Baum nicht um eine lineare Datenstruktur handelt, gibt es mehrere Knoten, die wir nach dem Besuch eines bestimmten Knotens besuchen können. Es gibt mehrere Baumdurchquerungstechniken, die die Reihenfolge festlegen, in der die Knoten des Baums besucht werden sollen.

Baumdurchquerungstechniken:



Eine Baumdatenstruktur kann auf folgende Weise durchlaufen werden:

  • Tiefensuche oder DFS
    • Inorder-Durchquerung
    • Traversal vorbestellen
    • Durchquerung von Postanweisungen
  • Level Order Traversal oder Breadth First Search oder BFS

Inorder-Durchquerung :

Beim Inorder-Traversal wird der Knoten in der folgenden Reihenfolge besucht: Links -> Wurzel -> Rechts




Algorithmus für Inorder Traversal:

Inorder(Baum)

  • Durchlaufen Sie den linken Teilbaum, d. h. rufen Sie Inorder(left->subtree) auf.
  • Besuchen Sie die Wurzel.
  • Durchqueren Sie den rechten Teilbaum, d. h. rufen Sie Inorder(right->subtree) auf.

Verwendungsmöglichkeiten von Inorder Traversal:

  • Bei binären Suchbäumen (BST) liefert die Inorder-Traversierung Knoten in nicht absteigender Reihenfolge.
  • Um Knoten von BST in nicht aufsteigender Reihenfolge zu erhalten, kann eine Variante der Inorder-Traversierung verwendet werden, bei der die Inorder-Traversierung umgekehrt wird.
  • Mit Inorder-Traversal können in Ausdrucksbäumen gespeicherte arithmetische Ausdrücke ausgewertet werden.

Codeausschnitt für Inorder Traversal:

C++ 
// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->links);  // Dann die Daten des Knotens cout ausgeben<< node->Daten<< ' ';  // Now recur on right child  printInorder(node->Rechts); }>
C 
// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->links);  // Dann die Daten des Knotens drucken printf('%d ', node->data);  // Jetzt auf dem rechten untergeordneten Element wiederholen printInorder(node->right); }>
Java 
void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Python3 
# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>
C# 
// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Javascript 
// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Ausgabe 
Inorder traversal of binary tree is 4 2 5 1 3>

Zeitkomplexität: AN)
Hilfsraum: Wenn wir die Größe des Stapels für Funktionsaufrufe nicht berücksichtigen, gilt O(1), andernfalls O(h), wobei h die Höhe des Baums ist.

Traversal vorbestellen :

Bei der Vorbestellungsdurchquerung wird der Knoten in der folgenden Reihenfolge besucht: Wurzel -> Links -> Rechts

Füße gegen Fuß

Algorithmus für die Vorbestellungsdurchquerung:

Vorbestellung (Baum)

  • Besuchen Sie die Wurzel.
  • Durchlaufen Sie den linken Teilbaum, d. h. rufen Sie Preorder(left->subtree) auf.
  • Durchqueren Sie den rechten Teilbaum, d. h. rufen Sie Preorder(right->subtree) auf.

Verwendungsmöglichkeiten von Preorder Traversal:

  • Die Vorbestellungsdurchquerung wird verwendet, um eine Kopie des Baums zu erstellen.
  • Die Vorbestellungsdurchquerung wird auch verwendet, um Präfixausdrücke in einem Ausdrucksbaum abzurufen.

Code-Snippet für Preorder Traversal:

C++ 
// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->Daten<< ' ';  // Then recur on left subtree  printPreorder(node->links);  // Jetzt im rechten Teilbaum wiederholen printPreorder(node->right); }>
C 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->Daten);  // Dann wiederkehren im linken Teilbaum printPreorder(node->left);  // Jetzt im rechten Teilbaum wiederholen printPreorder(node->right); }>
Java 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Python3 
# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>
C# 
// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Javascript 
// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Ausgabe 
Preorder traversal of binary tree is 1 2 4 5 3>

Zeitkomplexität: AN)
Hilfsraum: Wenn wir die Größe des Stapels für Funktionsaufrufe nicht berücksichtigen, gilt O(1), andernfalls O(h), wobei h die Höhe des Baums ist.

Durchquerung von Postanweisungen :

Postorder-Traversal besucht den Knoten in der Reihenfolge: Links -> Rechts -> Root

Algorithmus für Postorder Traversal:

Algorithmus Postanweisung(Baum)

  • Durchqueren Sie den linken Teilbaum, d. h. rufen Sie Postorder(left->subtree) auf.
  • Durchqueren Sie den rechten Teilbaum, d. h. rufen Sie Postorder(right->subtree) auf.
  • Besuchen Sie die Wurzel

Einsatzmöglichkeiten von Mailorder Traversal:

  • Zum Löschen des Baums wird Postorder-Traversal verwendet. Sehen die Frage nach der Löschung eines Baumes für Details.
  • Postorder-Traversal ist auch nützlich, um den Postfix-Ausdruck eines Ausdrucksbaums zu erhalten.
  • Postorder-Traversal kann bei Garbage-Collection-Algorithmen hilfreich sein, insbesondere in Systemen, in denen manuelle Speicherverwaltung verwendet wird.

Codeausschnitt für Mailorder Traversal:

C++ 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->links);  // Dann wiederkehren im rechten Teilbaum printPostorder(node->right);  // Beschäftige dich nun mit dem Knoten cout<< node->Daten<< ' '; }>
C 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->links);  // Dann wiederkehren im rechten Teilbaum printPostorder(node->right);  // Jetzt mit dem Knoten umgehen printf('%d ', node->data); }>
Java 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  System.out.print(node.key + ' '); }>
Python3 
# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>
C# 
// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  Console.Write(node.key + ' '); }>
Javascript 
// Given a binary tree, print its nodes according  // to the 'bottom-up' postorder traversal function printPostorder(node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  console.log(node.key + ' '); }>
Ausgabe 
Postorder traversal of binary tree is 4 5 2 3 1>

Level-Order-Traversal :

Level-Order-Traversal besucht alle in derselben Ebene vorhandenen Knoten vollständig, bevor er die nächste Ebene besucht.

Algorithmus für Level Order Traversal:

LevelOrder(Baum)

  • Erstellen Sie eine leere Warteschlange Q
  • Stellen Sie den Wurzelknoten des Baums in die Warteschlange Q
  • Schleife, solange Q nicht leer ist
    • Entfernen Sie einen Knoten aus Q und besuchen Sie ihn
    • Stellen Sie das linke untergeordnete Element des aus der Warteschlange entfernten Knotens in die Warteschlange, falls vorhanden
    • Stellen Sie das rechte Kind des aus der Warteschlange entfernten Knotens in die Warteschlange, falls vorhanden

Verwendungsmöglichkeiten der Level-Reihenfolge:

Verkettung Java-String
  • Level Order Traversal wird hauptsächlich als Breitensuche verwendet, um Knoten Ebene für Ebene zu suchen oder zu verarbeiten.
  • Level Order Traversal wird auch für verwendet Baumserialisierung und Deserialisierung .

Codeausschnitt für Level Order Traversal:

C++ 
// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueQ;  // Root in die Warteschlange stellen und Höhe initialisieren q.push(root);  while (q.empty() == false) { // Vorderseite der Warteschlange drucken und aus der Warteschlange entfernen Node* node = q.front();  cout<< node->Daten<< ' ';  q.pop();  // Enqueue left child  if (node->left != NULL) q.push(node->left);  // Rechtes Kind in die Warteschlange stellen if (node->right != NULL) q.push(node->right);  } }>
C 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->Daten);  // Linkes Kind in die Warteschlange stellen if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Rechtes Kind in die Warteschlange stellen if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Knoten aus der Warteschlange entfernen und zu temp_node machen temp_node = deQueue(queue, &front);  } }>
Java 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuequeue = neue LinkedList();  queue.add(root);  while (!queue.isEmpty()) { // poll() entfernt den aktuellen Kopf.  Knoten tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Linkes Kind in die Warteschlange stellen if (tempNode.left != null) { queue.add(tempNode.left);  } // Rechtes Kind in die Warteschlange stellen if (tempNode.right != null) { queue.add(tempNode.right);  } } }>
Python3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Vorderseite der Warteschlange drucken und # aus der Warteschlange entfernen print(queue[0].data, end=' ') node = queue.pop(0) # Linkes Kind in die Warteschlange stellen, wenn node.left nicht None ist: queue.append(node.left) # Rechtes Kind in die Warteschlange stellen, wenn node.right nicht None ist: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuequeue = neue Warteschlange();  queue.Enqueue(root);  while (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Linkes Kind in die Warteschlange stellen if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Rechtes Kind in die Warteschlange stellen if (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>
JavaScript 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Andere Baumdurchquerungen:

  1. Grenzüberschreitung
  2. Diagonale Durchquerung

1. Grenzüberschreitung :

Grenzüberschreitung eines Baumes beinhaltet:

  • Linke Grenze (Knoten auf der linken Seite ohne Blattknoten)
  • Blätter (bestehen nur aus den Blattknoten)
  • rechte Grenze (Knoten auf der rechten Seite ohne Blattknoten)

Algorithmus zur Grenzdurchquerung:

Java verkettet Zeichenfolgen

BoundaryTraversal(Baum)

  • Wenn root nicht null ist:
    • Root-Daten drucken
    • PrintLeftBoundary(root->left) // Druckt die linken Grenzknoten
    • PrintLeafNodes(root->left) // Blattknoten des linken Teilbaums drucken
    • PrintLeafNodes(root->right) // Blattknoten des rechten Teilbaums drucken
    • PrintRightBoundary(root->right) // Druckt die rechten Grenzknoten

Verwendungsmöglichkeiten der Grenzüberquerung:

  • Das Durchlaufen von Grenzen hilft dabei, die äußere Struktur eines Binärbaums zu visualisieren und liefert Einblicke in seine Form und Grenzen.
  • Die Grenzüberschreitung bietet eine Möglichkeit, auf diese Knoten zuzugreifen und sie zu ändern, wodurch Vorgänge wie das Beschneiden oder Neupositionieren von Grenzknoten ermöglicht werden.

2. Diagonale Durchquerung

Bei der diagonalen Durchquerung eines Baums werden alle Knoten in einer einzelnen Diagonale einzeln gedruckt.

Algorithmus für diagonale Durchquerung:

DiagonalTraversal(Baum):

  • Wenn root nicht null ist:
    • Erstellen Sie eine leere Karte
    • DiagonalTraversalUtil(root, 0, M) // Hilfsfunktion mit anfänglicher Diagonalebene 0 aufrufen
    • Für jedes Schlüssel-Wert-Paar (diagonalLevel, Knoten) in M:
      • Für jeden Knoten in Knoten:
      • Knotendaten drucken

DiagonalTraversalUtil(node, diagonalLevel, M):

  • Wenn der Knoten null ist:
  • Zurückkehren
  • Wenn diagonalLevel in M ​​nicht vorhanden ist:
    • Erstellen Sie eine neue Liste in M ​​für diagonalLevel
  • Knotendaten an die Liste bei M[diagonalLevel] anhängen
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Linkes Kind mit erhöhter Diagonalebene durchlaufen
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Rechtes untergeordnetes Element mit derselben Diagonalebene durchlaufen

Verwendungsmöglichkeiten der diagonalen Traversierung:

  • Diagonale Durchquerung hilft bei der Visualisierung der hierarchischen Struktur von Binärbäumen, insbesondere in baumbasierten Datenstrukturen wie binären Suchbäumen (BSTs) und Heap-Bäumen.
  • Die diagonale Durchquerung kann verwendet werden, um Pfadsummen entlang von Diagonalen in einem Binärbaum zu berechnen.

Häufig gestellte Fragen (FAQs) zu Tree-Traversal-Techniken:

1. Was sind Baumdurchquerungstechniken?

Baumdurchquerungstechniken sind Methoden, mit denen alle Knoten in einer Baumdatenstruktur besucht und verarbeitet werden. Sie ermöglichen den systematischen Zugriff auf jeden Knoten genau einmal.

2. Was sind die häufigsten Arten der Baumdurchquerung?

Die häufigsten Arten der Baumdurchquerung sind: Inorder-Durchquerung, Preorder-Durchquerung, Postorder-Durchquerung, Level-Order-Durchquerung (Breadth-First Search)

3. Was ist Inorder-Traversal?

Inorder-Traversal ist eine Tiefentraversierungsmethode, bei der Knoten in der Reihenfolge besucht werden: linker Teilbaum, aktueller Knoten, rechter Teilbaum.

4. Was ist Preorder-Traversal?

Bei der Vorbestellungsdurchquerung handelt es sich um eine Tiefendurchquerungsmethode, bei der Knoten in der folgenden Reihenfolge besucht werden: aktueller Knoten, linker Teilbaum, rechter Teilbaum.

5. Was ist Postanweisungsdurchlauf?

Postorder-Traversal ist eine Tiefen-First-Traversal-Methode, bei der Knoten in der Reihenfolge besucht werden: linker Teilbaum, rechter Teilbaum, aktueller Knoten.

6. Was ist Level Order Traversal?

Beim Durchlaufen der Ebenenreihenfolge, auch bekannt als Breadth-First Search (BFS), werden Knoten Ebene für Ebene besucht, beginnend bei der Wurzel und dann zur nächsten Ebene, bevor eine tiefere Durchquerung erfolgt.

7. Wann sollte ich die einzelnen Traversaltechniken anwenden?

Inorder-Traversal wird häufig für binäre Suchbäume verwendet, um Knoten in sortierter Reihenfolge zu erhalten.

Die Vorbestellungsdurchquerung ist nützlich, um eine Kopie des Baums zu erstellen.

Java aktualisieren

Postorder-Traversal wird häufig in Ausdrucksbäumen verwendet, um Ausdrücke auszuwerten.

Die Durchquerung der Ebenenreihenfolge ist hilfreich, um den kürzesten Weg zwischen Knoten zu finden.

8. Wie implementiere ich Baumdurchquerungsalgorithmen?

Baumdurchquerungsalgorithmen können je nach den spezifischen Anforderungen und der verwendeten Programmiersprache rekursiv oder iterativ implementiert werden.

9. Können Baumdurchquerungsalgorithmen auf andere baumartige Strukturen angewendet werden?

Ja, Baumdurchquerungsalgorithmen können angepasst werden, um andere baumartige Strukturen wie binäre Heaps, n-äre Bäume und als Bäume dargestellte Diagramme zu durchqueren.

10. Gibt es Leistungsaspekte bei der Auswahl einer Traversaltechnik?

Leistungsüberlegungen hängen von Faktoren wie der Größe und Form des Baums, dem verfügbaren Speicher und bestimmten Operationen ab, die während der Durchquerung ausgeführt werden. Im Allgemeinen kann sich die Wahl der Traversierungstechnik auf die Effizienz bestimmter Vorgänge auswirken. Daher ist es wichtig, die für Ihren spezifischen Anwendungsfall am besten geeignete Methode auszuwählen.

Einige andere wichtige Tutorials:

  • DSA-Tutorial
  • Systemdesign-Tutorial
  • Roadmap für die Softwareentwicklung
  • Roadmap zum Produktmanager
  • Lernen Sie SAP
  • Lernen Sie SEO