TRAVERSAL OF BINARY TREE VORBESTELLEN

Durchquerung vorbestellen ist als eine Art von definiert Baumdurchquerung das folgt der Root-Links-Rechts-Politik, wobei:

Zuerst wird der Wurzelknoten des Teilbaums besucht.
Anschließend wird der linke Teilbaum durchlaufen.
Zuletzt wird der rechte Teilbaum durchlaufen.

Durchquerung vorbestellen

entspricht einer Zeichenfolge in Java

Algorithmus für die Vorbestellungsdurchquerung des Binärbaums

Der Algorithmus für die Durchquerung der Vorbestellung wird wie folgt dargestellt:

Vorbestellung (root):

Befolgen Sie die Schritte 2 bis 4, bis root != NULL ist
Root -> Daten schreiben
Vorbestellung (root -> links)
Vorbestellung (root -> rechts)
Schleife beenden

Wie funktioniert Preorder Traversal of Binary Tree?

Betrachten Sie den folgenden Baum:

Beispiel eines Binärbaums

Wenn wir in diesem Binärbaum eine Vorbestellungsdurchquerung durchführen, sieht die Durchquerung wie folgt aus:

Schritt 1: Zunächst wird die Wurzel besucht, also Knoten 1.

Knoten 1 wird besucht

Schritt 2: Anschließend durchqueren Sie den linken Teilbaum. Jetzt wird die Wurzel des linken Teilbaums besucht, d. h. Knoten 2 wird besucht.

Knoten 2 wird besucht

Schritt 3: Wieder wird der linke Teilbaum von Knoten 2 durchlaufen und die Wurzel dieses Teilbaums, d. h. Knoten 4, besucht.
Typkonvertierung und Casting in Java

Knoten 4 wird besucht

Schritt 4: Es gibt keinen Teilbaum von Knoten 4 und der linke Teilbaum von Knoten 2 wird besucht. Nun wird der rechte Teilbaum von Knoten 2 durchlaufen und die Wurzel dieses Teilbaums, d. h. Knoten 5, besucht.

Knoten 5 wird besucht

Schritt 5: Der linke Teilbaum von Knoten 1 wird besucht. Nun wird also der rechte Teilbaum von Knoten 1 durchlaufen und der Wurzelknoten, also Knoten 3, besucht.

Knoten 3 wird besucht
Regalhunde

Schritt 6: Knoten 3 hat keinen linken Teilbaum. Es wird also der rechte Teilbaum durchlaufen und die Wurzel des Teilbaums, d. h. Knoten 6, besucht. Danach gibt es keinen Knoten mehr, der noch nicht durchlaufen wurde. Damit endet die Durchquerung.

Der komplette Baum wird besichtigt

Die Reihenfolge der Knotendurchquerung ist also 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Programm zur Implementierung der Vorbestellungsdurchquerung des Binärbaums

Nachfolgend finden Sie die Code-Implementierung der Vorbestellungsdurchquerung:

C++

 // C++ program for preorder traversals #include  using namespace std; // Structure of a Binary Tree Node struct Node {  int data;  struct Node *left, *right;  Node(int v)  {  data = v;  left = right = NULL;  } }; // Function to print preorder traversal void printPreorder(struct Node* node) {  if (node == NULL)  return;  // Deal with the node  cout << node->Daten<< ' ';  // Recur on left subtree  printPreorder(node->links);  // Wiederholung im rechten Teilbaum printPreorder(node->right); } // Treibercode int main() { struct Node* root = new Node(1);  root->left = new Node(2);  root->right = new Node(3);  root->left->left = new Node(4);  root->left->right = new Node(5);  root->right->right = new Node(6);  // Funktionsaufruf cout<< 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }>

Java

 // Java program for preorder traversals class Node {  int data;  Node left, right;  public Node(int item) {  data = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // Function to print preorder traversal  void printPreorder(Node node) {  if (node == null)  return;  // Deal with the node  System.out.print(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void main(String[] args) {  BinaryTree tree = new BinaryTree();  // Constructing the binary tree  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  // Function call  System.out.println('Preorder traversal of binary tree is: ');  tree.printPreorder(tree.root);  } }>

Python3

 # Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(node.right) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) # Function call print('Preorder traversal of binary tree is:') printPreorder(root)>

 // C# program for preorder traversals using System; // Structure of a Binary Tree Node public class Node {  public int data;  public Node left, right;  public Node(int v)  {  data = v;  left = right = null;  } } // Class to print preorder traversal public class BinaryTree {  // Function to print preorder traversal  public static void printPreorder(Node node)  {  if (node == null)  return;  // Deal with the node  Console.Write(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void Main()  {  Node root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  Console.WriteLine(  'Preorder traversal of binary tree is: ');  printPreorder(root);  } } // This code is contributed by Susobhan Akhuli>

Javascript

 // Structure of a Binary Tree Node class Node {  constructor(v) {  this.data = v;  this.left = null;  this.right = null;  } } // Function to print preorder traversal function printPreorder(node) {  if (node === null) {  return;  }  // Deal with the node  console.log(node.data);  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right); } // Driver code function main() {  const root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  console.log('Preorder traversal of binary tree is:');  printPreorder(root); } main();>

Ausgabe

Preorder traversal of binary tree is: 1 2 4 5 3 6>

Erläuterung:

So funktioniert die Vorbestellungsdurchquerung

Komplexitätsanalyse:

Zeitkomplexität: O(N) wobei N die Gesamtzahl der Knoten ist. Weil es alle Knoten mindestens einmal durchläuft.
Hilfsraum:

O(1) wenn kein Rekursionsstapelplatz berücksichtigt wird.
Ansonsten, Oh) wobei h die Höhe des Baumes ist
Im schlimmsten Fall, H kann dasselbe sein wie N (wenn der Baum ein schiefer Baum ist)
Im besten Fall, H kann dasselbe sein wie ruhig (wenn der Baum ein vollständiger Baum ist)

Anwendungsfälle von Preorder Traversal:

Einige Anwendungsfälle der Vorbestellungsdurchquerung sind:

Dies wird häufig zum Erstellen einer Kopie eines Baums verwendet.
Es ist auch nützlich, den Präfixausdruck aus einem Ausdrucksbaum abzurufen.

In Verbindung stehende Artikel:

Arten der Baumdurchquerung
Iterative Vorbestellungsdurchquerung
Überprüfen Sie, ob das angegebene Array eine Vorbestellungsdurchquerung von BST darstellen kann
Vorbestellung aus Inorder- und Postorder-Traversals
Finden Sie den n-ten Knoten in der Vorbestellungsdurchquerung eines Binärbaums
Durchquerung eines N-ary-Baums vorbestellen