In diesem Artikel werden wir die Vorbestellungsdurchquerung in der Datenstruktur diskutieren. Lineare Datenstrukturen wie Stapel, Array, Warteschlange usw. haben nur eine Möglichkeit, die Daten zu durchlaufen. Aber in einer hierarchischen Datenstruktur wie z Baum Es gibt mehrere Möglichkeiten, die Daten zu durchlaufen.
Bei der Vorbestellungsdurchquerung wird zuerst der Wurzelknoten besucht, dann der linke Unterbaum und anschließend der rechte Unterbaum. Der Prozess der Vorbestellungsdurchquerung kann wie folgt dargestellt werden:
root → left → right
Der Wurzelknoten wird bei der Durchquerung vor der Bestellung immer zuerst durchlaufen, während er bei der Durchquerung nach der Bestellung das letzte Element ist. Die Vorbestellungsdurchquerung wird verwendet, um den Präfixausdruck eines Baums zu erhalten.
Die Schritte zur Durchführung der Vorbestellungsdurchquerung sind wie folgt aufgeführt:
- Besuchen Sie zunächst den Wurzelknoten.
- Besuchen Sie dann den linken Teilbaum.
- Besuchen Sie abschließend den rechten Teilbaum.
Die Preorder-Traversal-Technik folgt dem Wurzel links rechts Politik. Die Namensvorbestellung selbst legt nahe, dass der Wurzelknoten zuerst durchlaufen wird.
Algorithmus
Sehen wir uns nun den Algorithmus der Vorbestellungsdurchquerung an.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
Beispiel für eine Vorbestellungsdurchquerung
Sehen wir uns nun ein Beispiel für die Vorbestellungsdurchquerung an. Anhand eines Beispiels lässt sich der Prozess der Vorbestellungsdurchquerung leichter verstehen.
Java-Nullprüfung
Die Knoten mit gelber Farbe wurden noch nicht besucht. Jetzt werden wir die Knoten des obigen Baums mit der Vorbestellungs-Traversierung durchlaufen.
- Beginnen Sie mit dem Wurzelknoten 40. Zuerst 40 drucken und dann den linken Teilbaum rekursiv durchlaufen.
- Gehen Sie nun zum linken Teilbaum. Für den linken Teilbaum ist der Wurzelknoten 30. Drucken 30 , und bewegen Sie sich in Richtung des linken Teilbaums von 30.
- Im linken Teilbaum von 30 gibt es also ein Element 25 Drucken 25 und durchquere den linken Teilbaum von 25.
- Im linken Teilbaum von 25 gibt es ein Element 15, und 15 hat keinen Teilbaum. Also, Drucken 15 , und wechseln Sie zum rechten Teilbaum von 25.
- Im rechten Teilbaum von 25 gibt es 28, und 28 hat keinen Teilbaum. Also, Drucken 28 , und wechseln Sie zum rechten Teilbaum von 30.
- Im rechten Teilbaum von 30 gibt es 35, der keinen Teilbaum hat. Also Drucken 35 , und durchquere den rechten Teilbaum von 40.
- Im rechten Teilbaum von 40 gibt es 50. Drucken Sie 50 und durchquere den linken Teilbaum von 50.
- Im linken Teilbaum von 50 gibt es 45, die kein Kind haben. Also, Drucken 45 und durchquere den rechten Teilbaum von 50.
- Im rechten Teilbaum von 50 gibt es 60. Drucken Sie 60 und durchquere den linken Teilbaum von 60.
- Im linken Teilbaum von 60 gibt es 55, die kein Kind haben. Also, Drucken 55 und gehen Sie zum rechten Teilbaum von 60.
- Im rechten Teilbaum von 60 gibt es 70, die kein Kind haben. Also, Drucken 70 und stoppen Sie den Vorgang.
Nach Abschluss der Vorbestellungsdurchquerung lautet die endgültige Ausgabe:
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Komplexität der Vorbestellungsdurchquerung
Die zeitliche Komplexität der Vorbestellungsdurchquerung beträgt An) , wobei 'n' die Größe des Binärbaums ist.
Die räumliche Komplexität der Vorbestellungsdurchquerung hingegen ist O(1) , wenn wir die Stapelgröße für Funktionsaufrufe nicht berücksichtigen. Ansonsten beträgt die räumliche Komplexität der Vorbestellungsdurchquerung Oh) , wobei „h“ die Höhe des Baumes ist.
Implementierung der Vorbestellungsdurchquerung
Sehen wir uns nun die Implementierung der Vorbestellungsdurchquerung in verschiedenen Programmiersprachen an.
binärer Suchbaum
Programm: Schreiben Sie ein Programm, um die Vorbestellungsdurchquerung in der Sprache C zu implementieren.
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } Ausgabe
Nach der Ausführung des obigen Codes lautet die Ausgabe:
Programm: Schreiben Sie ein Programm, um die Vorbestellungsdurchquerung in C++ zu implementieren.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } int main() { struct node* root = createNode(39); root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-16.webp" alt="Preorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Ausgabe
Nach der Ausführung des obigen Codes lautet die Ausgabe:
Programm: Schreiben Sie ein Programm, um die Vorbestellungsdurchquerung in Java zu implementieren.
Zeile vs. Spalte
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } Ausgabe
Nach der Ausführung des obigen Codes lautet die Ausgabe:
Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie.