In dit artikel bespreken we de preorder-traversal in de datastructuur. Lineaire datastructuren zoals stack, array, wachtrij, etc. hebben maar één manier om de data te doorkruisen. Maar in een hiërarchische gegevensstructuur zoals boom , zijn er meerdere manieren om de gegevens te doorkruisen.
Bij pre-order traversal wordt eerst het hoofdknooppunt bezocht, vervolgens de linker subboom en daarna de rechter subboom. Het proces van pre-order traversal kan worden weergegeven als -
root → left → right
Het hoofdknooppunt wordt altijd als eerste doorlopen bij pre-order-traversal, terwijl het het laatste item is bij post-order-traversal. Preorder traversal wordt gebruikt om de voorvoegselexpressie van een boom te verkrijgen.
De stappen voor het uitvoeren van de pre-order-doorgang worden als volgt weergegeven:
- Bezoek eerst het hoofdknooppunt.
- Bezoek vervolgens de linker subboom.
- Bezoek ten slotte de juiste subboom.
De preorder-traversaltechniek volgt de Wortel Links Rechts beleid. De naam preorder zelf suggereert dat het hoofdknooppunt als eerste zou worden doorlopen.
Algoritme
Laten we nu eens kijken naar het algoritme van pre-order traversal.
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
Voorbeeld van pre-order-traversal
Laten we nu een voorbeeld bekijken van pre-order traversal. Het zal gemakkelijker zijn om het proces van pre-order traversal te begrijpen aan de hand van een voorbeeld.
De knooppunten met gele kleur zijn nog niet bezocht. Nu zullen we de knooppunten van de bovenstaande boom doorkruisen met behulp van pre-order traversal.
- Begin met het hoofdknooppunt 40. Eerst afdrukken 40 en doorkruis vervolgens recursief de linker deelboom.
- Ga nu naar de linker subboom. Voor de linker subboom is het hoofdknooppunt 30. Afdrukken 30 , en ga naar de linker subboom van 30.
- In de linkerdeelboom van 30 is er een element 25, dus afdrukken 25 , en doorloop de linker deelboom van 25.
- In de linker subboom van 25 is er een element 15, en 15 heeft geen subboom. Dus, afdrukken 15 , en ga naar de rechter subboom van 25.
- In de rechter deelboom van 25 zijn er 28, en 28 heeft geen deelboom. Dus, afdrukken 28 en ga naar de rechter subboom van 30.
- In de rechter subboom van 30 zijn er 35 die geen subboom hebben. Dus afdrukken 35 , en doorloop de rechter deelboom van 40.
- In de rechter deelboom van 40 is er 50. Afdrukken 50 , en doorloop de linker deelboom van 50.
- In de linker subboom van 50 zijn er 45 die geen enkel kind hebben. Dus, afdrukken 45 en doorloop de rechter deelboom van 50.
- In de rechterdeelboom van 50 is er 60. Afdrukken 60 en doorkruis de linker deelboom van 60.
- In de linker subboom van 60 zijn er 55 die geen enkel kind hebben. Dus, afdrukken 55 en ga naar de rechter subboom van 60.
- In de rechter subboom van 60 zijn er 70 die geen enkel kind hebben. Dus, afdrukken 70 en stop het proces.
Na voltooiing van de pre-order-transactie is de uiteindelijke uitvoer:
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
vergelijking van leeuw en tijger
Complexiteit van pre-order-traversal
De tijdscomplexiteit van preorder-traversal is Op) , waarbij 'n' de grootte van de binaire boom is.
Terwijl de ruimtecomplexiteit van preorder-traversal dat wel is O(1) , als we geen rekening houden met de stapelgrootte voor functieaanroepen. Anders is de ruimtecomplexiteit van preorder-traversal dat wel Oh) , waarbij 'h' de hoogte van de boom is.
Implementatie van Preorder-traversal
Laten we nu eens kijken naar de implementatie van pre-order traversal in verschillende programmeertalen.
Programma: Schrijf een programma om preorder traversal in C-taal te implementeren.
#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; } Uitvoer
Na de uitvoering van de bovenstaande code zal de uitvoer zijn:
Programma: Schrijf een programma om preorder traversal in C++ te implementeren.
#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></'
></'> Uitvoer
Na de uitvoering van de bovenstaande code zal de uitvoer zijn:
Programma: Schrijf een programma om preorder traversal in Java te implementeren.
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(); } } Uitvoer
Na de uitvoering van de bovenstaande code zal de uitvoer zijn:
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.