I denne artikel vil vi diskutere forudbestillingsgennemgangen i datastruktur. Lineære datastrukturer såsom stak, array, kø osv. har kun én måde at krydse dataene på. Men i en hierarkisk datastruktur som f.eks træ , er der flere måder at krydse dataene på.
Ved forudbestillingsgennemgang besøges først rodknudepunktet, derefter venstre undertræ og derefter besøges højre undertræ. Processen med forudbestillingsgennemgang kan repræsenteres som -
root → left → right
Rodknudepunktet gennemløbes altid først i preorder-gennemgang, mens det er det sidste element i postorder-gennemgang. Preorder traversal bruges til at få præfiksudtrykket for et træ.
Trinnene til at udføre forudbestillingsgennemgangen er angivet som følger -
- Besøg først rodnoden.
- Besøg derefter det venstre undertræ.
- Besøg endelig det rigtige undertræ.
Forudbestillings-traversalteknikken følger Rod Venstre Højre politik. Selve navneforudbestillingen antyder, at rodknuden ville blive krydset først.
Algoritme
Lad os nu se algoritmen for forudbestillingsgennemgang.
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
Eksempel på preorder-gennemgang
Lad os nu se et eksempel på gennemgang af forudbestilling. Det vil være lettere at forstå processen med forudbestillingsgennemgang ved hjælp af et eksempel.
Noderne med gul farve er ikke besøgt endnu. Nu vil vi krydse knudepunkterne i ovenstående træ ved hjælp af forudbestillingsgennemgang.
- Start med rodnoden 40. Først, print 40 og kryds derefter rekursivt det venstre undertræ.
- Flyt nu til venstre undertræ. For venstre undertræ er rodnoden 30. Udskriv 30 , og bevæg dig mod venstre undertræ på 30.
- I venstre undertræ på 30 er der et element 25, så print 25 , og kryds det venstre undertræ af 25.
- I venstre undertræ på 25 er der et element 15, og 15 har intet undertræ. Så, print 15 , og flyt til højre undertræ af 25.
- I højre undertræ på 25 er der 28, og 28 har intet undertræ. Så, print 28 , og flyt til højre undertræ af 30.
- I højre undertræ på 30 er der 35, der ikke har noget undertræ. Så print 35 , og kryds det højre undertræ af 40.
- I det højre undertræ af 40 er der 50. Udskriv 50 , og kryds det venstre undertræ på 50.
- I venstre undertræ af 50 er der 45, der ikke har noget barn. Så, print 45 , og kryds det højre undertræ af 50.
- I højre undertræ på 50 er der 60. Udskriv 60 og krydse det venstre undertræ på 60.
- I venstre undertræ af 60 er der 55, der ikke har noget barn. Så, tryk 55 og flyt til højre undertræ af 60.
- I det højre undertræ af 60 er der 70, der ikke har noget barn. Så, tryk 70 og stoppe processen.
Efter afslutningen af forudbestillingsgennemgangen er det endelige output -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Kompleksiteten af gennemløb af forudbestilling
Tidskompleksiteten af preorder traversal er På) , hvor 'n' er størrelsen af binært træ.
Hvorimod rumkompleksiteten af forudbestillingsgennemgang er O(1) , hvis vi ikke overvejer stakstørrelsen for funktionskald. Ellers er pladskompleksiteten af forudbestillingsgennemgang O(h) , hvor 'h' er højden af træet.
Implementering af Preorder traversal
Lad os nu se implementeringen af preorder traversal i forskellige programmeringssprog.
Program: Skriv et program til at implementere preorder traversal i C-sprog.
#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 udførelse af ovenstående kode vil outputtet være -
Program: Skriv et program til at implementere preorder 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 udførelse af ovenstående kode vil outputtet være -
Program: Skriv et program til at implementere preorder traversal 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 udførelse af ovenstående kode vil outputtet være -
Så det handler om artiklen. Håber artiklen vil være nyttig og informativ for dig.