I denne artikkelen vil vi diskutere tregjennomgangen i datastrukturen. Begrepet 'trekryssing' betyr å krysse eller besøke hver node i et tre. Det er en enkelt måte å krysse den lineære datastrukturen på, for eksempel koblet liste, kø og stabel. Mens det er flere måter å krysse et tre på som er oppført som følger -
- Forhåndsbestill traversering
- Inorder kryssing
- Postordregjennomgang
Så i denne artikkelen vil vi diskutere de ovennevnte teknikkene for å krysse et tre. La oss nå begynne å diskutere måtene å krysse tre på.
Forhåndsbestill traversering
Denne teknikken følger 'root left right'-politikken. Det betyr at den første rotnoden besøkes etter at venstre undertre er krysset rekursivt, og til slutt krysses høyre undertre rekursivt. Ettersom rotnoden krysses før (eller før) venstre og høyre undertre, kalles det preorder traversal.
Så, i en forhåndsbestillingsgjennomgang, besøkes hver node før begge undertrærne.
Bruken av forhåndsbestillingsgjennomgang inkluderer -
- Den brukes til å lage en kopi av treet.
- Den kan også brukes til å få prefiksuttrykket til et uttrykkstre.
Algoritme
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.
Eksempel
La oss nå se eksemplet med preorder-traversalteknikken.
Begynn nå å bruke forhåndsbestillingen på treet ovenfor. Først krysser vi rotnoden EN; deretter flytter du til venstre undertre B , som også vil bli krysset i forhåndsbestilling.
Så, for venstre undertre B, først rotnoden B er krysset seg selv; etter det, venstre undertre D er krysset. Siden node D har ingen barn, flytt til høyre undertre OG . Siden node E heller ikke har noen barn, er kryssingen av det venstre undertreet til rotnoden A fullført.
sorter array liste
Beveg deg nå mot høyre undertre til rotnoden A som er C. Så for høyre undertre C, først rotnoden C har krysset seg selv; etter det, venstre undertre F er krysset. Siden node F ikke har noen barn, flytt til høyre undertre G . Siden node G heller ikke har noen barn, er kryssing av høyre undertre til rotnoden A fullført.
Derfor krysses alle nodene til treet. Så utdata fra forhåndsbestillingsgjennomgangen til treet ovenfor er -
A → B → D → E → C → F → G
For å vite mer om forhåndsbestillingsgjennomgangen i datastrukturen kan du følge lenken Forhåndsbestill traversering .
Postordregjennomgang
Denne teknikken følger 'venstre-høyre rot'-politikken. Det betyr at det første venstre undertreet til rotnoden krysses, deretter krysser det høyre undertreet rekursivt, og til slutt krysses rotnoden. Ettersom rotnoden krysses etter (eller poster) det venstre og høyre undertreet, kalles det postorder-traversering.
Så, i en postorder-gjennomgang, blir hver node besøkt etter begge undertrærne.
Bruken av postordreovergang inkluderer -
mysql vis alle brukere
- Den brukes til å slette treet.
- Den kan også brukes til å få postfix-uttrykket til et uttrykkstre.
Algoritme
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.
Eksempel
La oss nå se eksemplet på postorder-traversalteknikken.
Begynn nå å bruke postordre-traverseringen på treet ovenfor. Først krysser vi venstre undertre B som vil bli krysset i postordre. Etter det vil vi krysse det høyre undertreet C i postordre. Og til slutt, rotnoden til treet ovenfor, dvs. EN , krysses.
Så, for venstre undertre B, først, venstre undertre D er krysset. Siden node D ikke har noen barn, kryss det høyre undertreet OG . Siden node E heller ikke har noen barn, flytt til rotnoden B. Etter å ha krysset noden B, kryssingen av det venstre undertreet til rotnoden A er fullført.
Beveg deg nå mot høyre undertre av rotnoden A som er C. Så for høyre undertre C, først dets venstre undertre F er krysset. Siden node F ikke har noen barn, kryss det høyre undertreet G . Siden node G heller ikke har noen barn, vil derfor til slutt rotnoden til det høyre undertreet, dvs. C, er krysset. Traverseringen av det høyre undertreet til rotnoden A er fullført.
Til slutt, kryss rotnoden til et gitt tre, dvs. EN . Etter å ha krysset rotnoden, er postorder-gjennomgangen av det gitte treet fullført.
Derfor krysses alle nodene til treet. Så utgangen av postorder-gjennomgangen til treet ovenfor er -
D → E → B → F → G → C → A
For å vite mer om postordretraverseringen i datastrukturen kan du følge lenken Postordregjennomgang .
Inorder kryssing
Denne teknikken følger 'venstre rot høyre'-policyen. Det betyr at det første venstre undertreet besøkes etter at rotnoden er krysset, og til slutt krysses det høyre undertreet. Ettersom rotnoden krysses mellom venstre og høyre undertre, kalles den inorder-gjennomgang.
muserull fungerer ikke
Så, i inordre-gjennomgangen, besøkes hver node mellom undertrærne.
Applikasjonene til Inorder-traversal inkluderer -
- Den brukes til å få BST-nodene i økende rekkefølge.
- Den kan også brukes til å få prefiksuttrykket til et uttrykkstre.
Algoritme
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.
Eksempel
La oss nå se eksemplet på Inorder-traversalteknikken.
Begynn nå å bruke den inordnede traverseringen på treet ovenfor. Først krysser vi det venstre undertreet B som vil bli krysset i rekkefølge. Etter det vil vi krysse rotnoden EN . Og til slutt, det rette undertreet C krysses i uordnet rekkefølge.
Så, for venstre undertre B , først det venstre undertreet D er krysset. Siden node D har ingen barn, så etter å ha krysset den, node B vil bli krysset, og til slutt høyre undertre av node B, det vil si OG , krysses. Node E har heller ingen barn; derfor er kryssingen av det venstre undertreet til rotnoden A fullført.
Deretter krysser du rotnoden til et gitt tre, dvs. EN .
Til slutt, flytt mot høyre undertre av rotnoden A, som er C. Så, for høyre undertre C; først, venstre undertre F er krysset. Siden node F har ingen barn, node C vil bli krysset, og til slutt et høyre undertre av node C, det vil si, G , krysses. Node G har heller ingen barn; derfor er kryssingen av det høyre undertreet til rotnoden A fullført.
hva er regex java
Ettersom alle nodene til treet krysses, fullføres den uordnede kryssingen av det gitte treet. Utdataene fra den uordnede traverseringen av treet ovenfor er -
D → B → E → A → F → C → G
For å vite mer om inorder-gjennomgangen i datastruktur, kan du følge lenken Inorder Traversal .
Kompleksiteten til trekryssingsteknikker
Tidskompleksiteten til tretraverseringsteknikker diskutert ovenfor er På) , hvor 'n' er størrelsen på et binært tre.
Mens plasskompleksiteten til tretraverseringsteknikker diskutert ovenfor er O(1) hvis vi ikke vurderer stabelstørrelsen for funksjonskall. Ellers er plasskompleksiteten til disse teknikkene Åh) , hvor 'h' er treets høyde.
Gjennomføring av trekryssing
La oss nå se implementeringen av de ovenfor diskuterte teknikkene ved å bruke forskjellige programmeringsspråk.
Program: Skriv et program for å implementere tretraverseringsteknikker 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; } Produksjon
Program: Skriv et program for å implementere tretraverseringsteknikker i C#.
java skanner
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(); } } Produksjon
Program: Skriv et program for å implementere tretraverseringsteknikker 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); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<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->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
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 + ' '); 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 + ' '); 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 + ' '); } 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('The Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println('
'); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println('
'); System.out.println('The Postorder traversal of given binary tree is - '); 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's all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'> Produksjon
Etter utførelse av koden ovenfor, vil utgangen være -
Konklusjon
I denne artikkelen har vi diskutert de forskjellige typene tretraversalteknikker: preorder traversal, inorder traversal og postorder traversal. Vi har sett disse teknikkene sammen med algoritme, eksempel, kompleksitet og implementering i C, C++, C# og java.
Så det handler om artikkelen. Håper det vil være nyttig og informativt for deg.