V tem članku bomo razpravljali o prehodu po vrstnem redu v strukturi podatkov.
Če želimo prečkati vozlišča v naraščajočem vrstnem redu, potem uporabimo prečkanje po vrstnem redu. Za prehod po vrstnem redu so potrebni naslednji koraki:
- Obiščite vsa vozlišča v levem poddrevesu
- Obiščite korensko vozlišče
- Obiščite vsa vozlišča v desnem poddrevesu
Linearne podatkovne strukture, kot so sklad, niz, čakalna vrsta itd., imajo samo en način za prečkanje podatkov. Toda v hierarhičnih podatkovnih strukturah, kot je npr drevo, obstaja več načinov za prehod podatkov. Tukaj bomo razpravljali o drugem načinu prečkanja drevesne podatkovne strukture, tj. prečkanju po vrstnem redu.
Za prečkanje po vrstnem redu se uporabljata dva pristopa:
- Prehod po vrstnem redu z uporabo rekurzije
- Prehod po vrstnem redu z uporabo iterativne metode
Sledi tehnika neurejenega prehoda Levi koren Desni politika. Tukaj levo korensko desno pomeni, da se najprej prečka levo poddrevo korenskega vozlišča, nato korensko vozlišče in nato desno poddrevo korenskega vozlišča. Tu samo ime vrstnega reda nakazuje, da je korensko vozlišče med levim in desnim poddrevesom.
Razpravljali bomo o prehodu po vrstnem redu z uporabo rekurzivnih in iterativnih tehnik. Najprej začnimo s prehodom po vrstnem redu z uporabo rekurzije.
Prehod po vrstnem redu z uporabo rekurzije
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Primer neurejenega prehoda
Zdaj pa poglejmo primer prečkanja po nevrstnem redu. Na primeru bomo lažje razumeli postopek prečkanja po vrstnem redu.
abstraktni razred v Javi
Vozlišča z rumeno barvo še niso obiskana. Zdaj bomo prečkali vozlišča zgornjega drevesa z uporabo prečkanja po vrstnem redu.
- Tu je 40 korensko vozlišče. Premaknemo se na levo poddrevo 40, to je 30, in ima tudi poddrevo 25, tako da se spet premaknemo na levo poddrevo 25, to je 15. Tukaj 15 nima poddrevesa, torej natisni 15 in se pomaknite proti nadrejenemu vozlišču, 25.
- zdaj, natisni 25 in se pomaknite na desno poddrevo 25.
- zdaj, natisni 28 in se premaknite na korensko vozlišče 25, to je 30.
- Torej je obiskano levo poddrevo 30. zdaj, natisni 30 in se pomaknite k desnemu otroku 30.
- zdaj, natisni 35 in se premaknite na korensko vozlišče 30.
- zdaj, natisni korensko vozlišče 40 in se premakne na njegovo desno poddrevo.
- Zdaj rekurzivno prečkajte desno poddrevo 40, to je 50.
50 ima poddrevo, zato najprej prečkajte levo poddrevo 50, ki je 45. 45 nima otrok, torej natisni 45 in se premaknite na njegovo korensko vozlišče.
- Zdaj natisni 50 in se pomaknite na desno poddrevo 50, to je 60.
- Zdaj rekurzivno prečkajte desno poddrevo 50, ki je 60. 60 ima poddrevo, zato najprej prečkajte levo poddrevo 60, ki je 55. 55 nima otrok, torej natisni 55 in se premaknite na njegovo korensko vozlišče.
- Zdaj natisni 60 in se pomaknite na desno poddrevo 60, to je 70.
- Zdaj natisni 70.
Po zaključku prečkanja po vrstnem redu je končni rezultat -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Kompleksnost prečkanja Inorderja
Časovna zapletenost prečkanja Inorderja je O(n), kjer je 'n' velikost binarnega drevesa.
Medtem ko je prostorska zapletenost neurejenega prečkanja O(1), če ne upoštevamo velikosti sklada za klice funkcij. V nasprotnem primeru je prostorska kompleksnost neurejenega prehoda O(h), kjer je 'h' višina drevesa.
abecede do številk
Implementacija prečkanja Inorderja
Zdaj pa si oglejmo implementacijo prečkanja po vrstnem redu v različnih programskih jezikih.
Program: Napišite program za izvajanje prečkanja po vrstnem redu v jeziku 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 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; } Izhod
Program: Napišite program za izvajanje prečkanja po vrstnem redu v 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 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></'
></'> Izhod
Program: Napišite program za izvajanje prečkanja po vrstnem redu v Javi.
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(); } } Izhod
Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.