I den här artikeln kommer vi att diskutera trädgenomgången i datastrukturen. Termen 'trädpassering' betyder att korsa eller besöka varje nod i ett träd. Det finns ett enda sätt att gå igenom den linjära datastrukturen såsom länkad lista, kö och stack. Medan det finns flera sätt att korsa ett träd som är listade enligt följande -

• Förbeställ genomgång
• Inorder genomgång
• Postorder traversal

Så i den här artikeln kommer vi att diskutera de ovan listade teknikerna för att korsa ett träd. Låt oss nu börja diskutera sätten för trädpassering.

Förbeställ genomgång

Denna teknik följer 'root left right'-policyn. Det betyder att den första rotnoden besöks efter att det vänstra underträdet korsas rekursivt, och slutligen korsas det högra underträdet rekursivt. Eftersom rotnoden korsas före (eller före) det vänstra och högra underträdet, kallas det förbeställningsgenomgång.

Så, i en förbeställnings-traversering, besöks varje nod före båda dess underträd.

Tillämpningarna av förbeställningsövergång inkluderar -

• Den används för att skapa en kopia av trädet.
• Den kan också användas för att få prefixuttrycket för ett uttrycksträd.

Algoritm

 Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively. 

Exempel

Låt oss nu se exemplet på förbeställnings-traversaltekniken.

Börja nu tillämpa förbeställningsövergången på ovanstående träd. Först korsar vi rotnoden A; efter det, flytta till dess vänstra underträd B , som också kommer att passeras i förbeställning.

Så, för vänster underträd B, först rotnoden B genomkorsas sig själv; efter det, dess vänstra underträd D är genomkorsad. Sedan nod D inte har några barn, flytta till höger underträd OCH . Eftersom nod E inte heller har några barn, är genomgången av det vänstra underträdet av rotnod A slutförd.

konvertera strin till int

Gå nu mot det högra underträdet av rotnod A, det vill säga C. Så för höger underträd C, först rotnoden C har korsat sig själv; efter det, dess vänstra underträd F är genomkorsad. Sedan nod F inte har några barn, flytta till höger underträd G . Eftersom nod G inte heller har några barn, är genomgången av det högra underträdet av rotnod A slutförd.

Därför korsas alla noder i trädet. Så utdata från förbeställningsgenomgången av ovanstående träd är -

A → B → D → E → C → F → G

körtidsfel

För att veta mer om förbeställningsgenomgången i datastrukturen kan du följa länken Förbeställ genomgång .

Postorder traversal

Denna teknik följer 'vänster-höger rot'-policyn. Det betyder att det första vänstra underträdet av rotnoden korsas, därefter korsar det högra underträdet rekursivt, och slutligen korsas rotnoden. Eftersom rotnoden korsas efter (eller postar) det vänstra och högra underträdet, kallas det postorder-traversal.

Så, i en postorder-traversering, besöks varje nod efter båda dess underträd.

Tillämpningarna av postordertraversering inkluderar -

• Den används för att ta bort trädet.
• Den kan också användas för att få postfix-uttrycket för ett uttrycksträd.

Algoritm

 Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node. 

Exempel

Låt oss nu se exemplet på postorder-traversaltekniken.

Börja nu tillämpa postorder-traversalen på ovanstående träd. Först korsar vi det vänstra underträdet B som kommer att korsas i postorder. Efter det kommer vi att korsa det högra underträdet C i postorder. Och slutligen, rotnoden för ovanstående träd, dvs. A , korsas.

Så, för vänster underträd B, först dess vänstra underträd D är genomkorsad. Sedan nod D inte har några barn, gå igenom höger underträd OCH . Eftersom nod E inte heller har några barn, flytta till rotnoden B. Efter att ha korsat nod B, korsningen av det vänstra underträdet av rotnod A är slutförd.

Gå nu mot det högra underträdet av rotnod A, det vill säga C. Så för höger underträd C, först dess vänstra underträd F är genomkorsad. Sedan nod F inte har några barn, gå igenom höger underträd G . Eftersom nod G inte heller har några barn, därför slutligen rotnoden för det högra underträdet, dvs. C, är genomkorsad. Genomgången av det högra underträdet av rotnod A är slutförd.

Gå till sist genom rotnoden för ett givet träd, dvs. A . Efter att ha korsat rotnoden är postorder-genomgången av det givna trädet slutfört.

Därför korsas alla noder i trädet. Så utdata från postorder-genomgången av ovanstående träd är -

D → E → B → F → G → C → A

För att veta mer om postordertraverseringen i datastrukturen kan du följa länken Postorder traversal .

Inorder genomgång

Denna teknik följer policyn för 'vänster rot höger'. Det betyder att det första vänstra underträdet besöks efter att rotnoden har passerats, och slutligen korsas det högra underträdet. När rotnoden korsas mellan det vänstra och högra underträdet, kallas det inorder-traversal.

Så, i den inordnade genomgången, besöks varje nod mellan dess underträd.

Tillämpningarna av Inorder-traversal inkluderar -

år månad

• Den används för att få BST-noderna i ökande ordning.
• Den kan också användas för att få prefixuttrycket för ett uttrycksträd.

Algoritm

 Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively. 

Exempel

Låt oss nu se exemplet på Inorder-traversaltekniken.

Börja nu tillämpa den inordnade traverseringen på ovanstående träd. Först korsar vi det vänstra underträdet B som kommer att passeras i oordning. Efter det kommer vi att korsa rotnoden A . Och slutligen det rätta underträdet C passeras i oordning.

Så, för vänster underträd B , först dess vänstra underträd D är genomkorsad. Sedan nod D har inga barn, så efter att ha korsat den, node B kommer att korsas, och till sist, höger underträd av nod B, det vill säga OCH , korsas. Nod E har inte heller några barn; därför fullbordas genomgången av det vänstra underträdet av rotnod A.

Efter det, korsa rotnoden för ett givet träd, dvs. A .

Gå till sist mot det högra underträdet av rotnod A, det vill säga C. Så, för höger underträd C; först dess vänstra underträd F är genomkorsad. Sedan nod F har inga barn, nod C kommer att korsas, och till sist, ett höger underträd av nod C, det vill säga, G , korsas. Nod G har inte heller några barn; därför är genomgången av det högra underträdet av rotnod A fullbordad.

När alla noder i trädet korsas, fullbordas den inordnade genomgången av det givna trädet. Utdata från inordnande genomgång av ovanstående träd är -

D → B → E → A → F → C → G

sträng i c

För att veta mer om ordningsgenomgången i datastruktur kan du följa länken Inorder Traversal .

Komplexiteten hos trädgenomgångstekniker

Tidskomplexiteten för trädgenomgångstekniker som diskuterats ovan är På) , var 'n' är storleken på ett binärt träd.

Medan rymdkomplexiteten för trädgenomgångstekniker som diskuterats ovan är O(1) om vi inte tar hänsyn till stackstorleken för funktionsanrop. Annars är utrymmeskomplexiteten för dessa tekniker Åh) , var 'h' är trädets höjd.

Genomförande av trädpassering

Låt oss nu se implementeringen av de ovan diskuterade teknikerna med hjälp av olika programmeringsspråk.

Program: Skriv ett program för att implementera trädgenomgångstekniker i C.

 #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); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
 The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
 The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
 The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } 

Produktion

Program: Skriv ett program för att implementera trädgenomgångstekniker i C#.

 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 traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } 

Produktion

Program: Skriv ett program för att implementera trädgenomgångstekniker i C++.

hur man uppdaterar i java

 #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-&gt;element = val; Node-&gt;left = NULL; Node-&gt;right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout&lt;<' '<element<left); traversepreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root-&gt;left); cout&lt;<' '<element<right); } *function to traverse the nodes of binary tree in postorder* void traversepostorder(struct node* root) { if (root="=" null) return; traversepostorder(root->left); traversePostorder(root-&gt;right); cout&lt;<' '<element<left="createNode(28);" root->right = createNode(48); root-&gt;left-&gt;left = createNode(23); root-&gt;left-&gt;right = createNode(33); root-&gt;left-&gt;left-&gt;left = createNode(13); root-&gt;left-&gt;left-&gt;right = createNode(26); root-&gt;right-&gt;left = createNode(43); root-&gt;right-&gt;right = createNode(58); root-&gt;right-&gt;right-&gt;left = createNode(53); root-&gt;right-&gt;right-&gt;right = createNode(68); cout&lt;<'
 the preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
 inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + &apos; &apos;); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + &apos; &apos;); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + &apos; &apos;); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println(&apos;The Preorder traversal of given binary tree is - &apos;); pt.traversePreorder(); System.out.println(&apos;
&apos;); System.out.println(&apos;The Inorder traversal of given binary tree is - &apos;); pt.traverseInorder(); System.out.println(&apos;
&apos;); System.out.println(&apos;The Postorder traversal of given binary tree is - &apos;); pt.traversePostorder(); 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/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that&apos;s all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'>

Produktion

Efter exekvering av ovanstående kod kommer utgången att vara -

Slutsats

I den här artikeln har vi diskuterat de olika typerna av trädgenomgångstekniker: förbeställningstraversal, inorder-traversal och postorder-traversal. Vi har sett dessa tekniker tillsammans med algoritm, exempel, komplexitet och implementering i C, C++, C# och java.

Så det handlar om artikeln. Hoppas det kommer att vara till hjälp och informativt för dig.