Šajā rakstā mēs apspriedīsim secības šķērsošanu datu struktūrā.
Ja vēlamies šķērsot mezglus augošā secībā, tad izmantojam inorder traversal. Tālāk ir norādītas darbības, kas jāveic pasūtījuma šķērsošanai:
- Apmeklējiet visus mezglus kreisajā apakškokā
- Apmeklējiet saknes mezglu
- Apmeklējiet visus mezglus labajā apakškokā
Lineārām datu struktūrām, piemēram, kaudze, masīvs, rinda utt., ir tikai viens veids, kā šķērsot datus. Bet hierarhiskās datu struktūrās, piemēram, koks, ir vairāki veidi, kā pārvietot datus. Šeit mēs apspriedīsim citu veidu, kā šķērsot koka datu struktūru, t.i., secības šķērsošanu.
Pasūtījuma šķērsošanai tiek izmantotas divas pieejas:
- Pasūtiet šķērsošanu, izmantojot Recursion
- Pasūtījuma šķērsošana, izmantojot iteratīvo metodi
Tiek ievērota kārtības šķērsošanas tehnika Kreisā sakne pa labi politiku. Šeit Left Root Right nozīmē, ka vispirms tiek šķērsots saknes mezgla kreisais apakškoks, pēc tam saknes mezgls un pēc tam tiek šķērsots saknes mezgla labais apakškoks. Šeit pats kārtas nosaukums liecina, ka saknes mezgls atrodas starp kreiso un labo apakškoku.
Mēs apspriedīsim secības šķērsošanu, izmantojot gan rekursīvus, gan iteratīvus paņēmienus. Vispirms sāksim ar inorder traversal, izmantojot rekursiju.
Kārtības šķērsošana, izmantojot rekursiju
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Kārtības šķērsošanas piemērs
Tagad apskatīsim inorder šķērsošanas piemēru. Izmantojot piemēru, būs vieglāk saprast inorder šķērsošanas procedūru.
par katru mašīnrakstu
Mezgli ar dzeltenu krāsu vēl nav apmeklēti. Tagad mēs šķērsosim iepriekš minētā koka mezglus, izmantojot inorder traversal.
- Šeit 40 ir saknes mezgls. Mēs pārejam uz kreiso apakškoku 40, tas ir 30, un tam ir arī apakškoks 25, tāpēc mēs atkal pārietam uz kreiso apakškoku 25, kas ir 15. Šeit 15 nav apakškoka, tāpēc drukāt 15 un virzieties uz tā vecākmezglu, 25.
- Tagad drukāt 25 un pārejiet uz 25 labo apakškoku.
- Tagad drukāt 28 un pārejiet uz 25 saknes mezglu, kas ir 30.
- Tātad tiek apmeklēts kreisais apakškoks no 30. Tagad drukāt 30 un pāriet pie labā 30 gadu bērna.
- Tagad drukāt 35 un pārejiet uz 30 saknes mezglu.
- Tagad drukāt saknes mezglu 40 un pārejiet uz tā labo apakškoku.
- Tagad rekursīvi šķērsojiet labo apakškoku 40, kas ir 50.
50 ir apakškoks, tāpēc vispirms šķērsojiet kreiso apakškoku no 50, kas ir 45. 45 nav bērnu, tāpēc drukāt 45 un pāriet uz tā saknes mezglu.
- Tagad drukāt 50 un pārejiet uz labo apakškoku 50, kas ir 60.
- Tagad rekursīvi šķērsojiet labo apakškoku 50, kas ir 60. 60 ir apakškoks, tāpēc vispirms šķērsojiet kreiso apakškoku 60, kas ir 55. 55 nav bērnu, tāpēc drukāt 55 un pāriet uz tā saknes mezglu.
- Tagad drukāt 60 un pārejiet uz labo apakškoku 60, kas ir 70.
- Tagad drukāt 70.
Pēc kārtas šķērsošanas pabeigšanas gala rezultāts ir -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Inorder šķērsošanas sarežģītība
Inorder šķērsošanas laika sarežģītība ir O(n), kur “n” ir binārā koka izmērs.
Savukārt inorder šķērsošanas sarežģītība ir O(1), ja neņemam vērā funkciju izsaukumu steka lielumu. Pretējā gadījumā inorder šķērsošanas telpa ir sarežģīta O(h), kur “h” ir koka augstums.
javascript onclick
Inorder traversal ieviešana
Tagad apskatīsim inorder traversal ieviešanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu inorder traversal ieviešanai C valodā.
#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 Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(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 Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; } Izvade
Programma: Uzrakstiet programmu inorder traversal ieviešanai C++ valodā.
#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 Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<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 inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder 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 traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Izvade
Programma: Uzrakstiet programmu, lai ieviestu inorder traversal Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } Izvade
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.