I den här artikeln kommer vi att diskutera förbeställningsövergången i datastruktur. Linjära datastrukturer som stack, array, kö etc. har bara ett sätt att gå igenom data. Men i en hierarkisk datastruktur som t.ex träd , det finns flera sätt att gå igenom data.
nackdelar med internet
Vid förbeställnings-traversering besöks först rotnoden, sedan vänster underträd och efter det högra underträdet. Processen med förbeställningsövergång kan representeras som -
root → left → right
Rotnoden korsas alltid först i förbeställningsgenomgång, medan det är den sista posten i postordergenomgång. Genomgång av förbeställning används för att få prefixuttrycket för ett träd.
Stegen för att utföra förbeställningsgenomgången listas enligt följande -
- Besök först rotnoden.
- Besök sedan det vänstra underträdet.
- Besök äntligen det högra underträdet.
Förbeställnings-traverseringstekniken följer Rot Vänster Höger politik. Själva namnförordningen antyder att rotnoden skulle korsas först.
Algoritm
Låt oss nu se algoritmen för förbeställnings-traversering.
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
Exempel på genomgång av förbeställning
Låt oss nu se ett exempel på förbeställning. Det blir lättare att förstå processen för förbeställning genom att använda ett exempel.
Noderna med gul färg är inte besökta ännu. Nu kommer vi att korsa noderna i ovanstående träd med förbeställnings-traversering.
- Börja med rotnoden 40. Först, tryck 40 och sedan rekursivt gå igenom det vänstra underträdet.
- Flytta nu till det vänstra underträdet. För vänster underträd är rotnoden 30. Skriv ut 30 , och flytta mot det vänstra underträdet på 30.
- I det vänstra underträdet på 30 finns ett element 25, alltså tryck 25 , och gå igenom det vänstra underträdet på 25.
- I det vänstra underträdet av 25 finns ett element 15, och 15 har inget underträd. Så, tryck 15 , och flytta till höger underträd av 25.
- I höger underträd av 25 finns 28, och 28 har inget underträd. Så, tryck 28 , och flytta till höger underträd av 30.
- I höger underträd av 30 finns det 35 som inte har något underträd. Så tryck 35 , och gå igenom det högra underträdet på 40.
- I det högra underträdet av 40 finns det 50. Skriv ut 50 , och gå igenom det vänstra underträdet på 50.
- I det vänstra underträdet av 50 finns det 45 som inte har något barn. Så, tryck 45 , och gå igenom det högra underträdet på 50.
- I höger underträd av 50 finns det 60. Skriv ut 60 och gå igenom det vänstra underträdet på 60.
- I det vänstra underträdet av 60 finns det 55 som inte har något barn. Så, tryck 55 och flytta till höger underträd av 60.
- I det högra underträdet av 60 finns det 70 som inte har något barn. Så, tryck 70 och stoppa processen.
Efter slutförandet av förbeställningsgenomgången är den slutliga utmatningen -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Komplexiteten i förbeställningsgenomgång
Tidskomplexiteten för genomgång av förbeställning är På) , där 'n' är storleken på ett binärt träd.
Medan rymdkomplexiteten för förbeställnings-traversering är O(1) , om vi inte tar hänsyn till stackstorleken för funktionsanrop. Annars är utrymmeskomplexiteten för förbeställningsgenomgång Åh) , där 'h' är trädets höjd.
Implementering av Preorder-traversal
Låt oss nu se implementeringen av förbeställningsövergång i olika programmeringsspråk.
Program: Skriv ett program för att implementera förbeställnings-traversal i C-språk.
#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; } Produktion
Efter exekvering av ovanstående kod kommer utgången att vara -
Program: Skriv ett program för att implementera förbeställnings-traversal i C++.
#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></'
></'> Produktion
Efter exekvering av ovanstående kod kommer utgången att vara -
Program: Skriv ett program för att implementera förbeställningstraversal i Java.
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(); } } Produktion
Efter exekvering av ovanstående kod kommer utgången att vara -
Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.