U ovom ćemo članku raspravljati o obilasku po redoslijedu u strukturi podataka.
Ako želimo obići čvorove uzlaznim redoslijedom, tada koristimo obilazak po redoslijedu. Slijede koraci potrebni za obilazak po redoslijedu:
- Posjetite sve čvorove u lijevom podstablu
- Posjetite korijenski čvor
- Posjetite sve čvorove u desnom podstablu
Linearne podatkovne strukture kao što su stog, niz, red čekanja itd. imaju samo jedan način za prolazak kroz podatke. Ali u hijerarhijskim strukturama podataka kao što su drvo, postoji više načina za prelazak podataka. Ovdje ćemo raspravljati o drugom načinu prelaska strukture podataka stabla, tj. obilasku po redoslijedu.
Postoje dva pristupa koji se koriste za obilazak po redoslijedu:
- Prolazak po neredu korištenjem rekurzije
- Prolazak po redoslijedu korištenjem iterativne metode
Slijedi tehnika neurednog obilaska Lijevo Koren Desno politika. Ovdje Lijevi korijenski desni znači da se prvo prelazi lijevo podstablo korijenskog čvora, zatim korijenski čvor, a zatim se prelazi desno podstablo korijenskog čvora. Ovdje sam naziv reda sugerira da korijenski čvor dolazi između lijevog i desnog podstabla.
Raspravljat ćemo o obilasku po neredu koristeći i rekurzivne i iterativne tehnike. Počnimo prvo s obilaskom po redoslijedu pomoću rekurzije.
Prolazak po neredu korištenjem rekurzije
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Primjer neurednog obilaženja
Sada, da vidimo primjer obilaženja po neredu. Na primjeru ćemo lakše razumjeti proceduru obilaska po neredu.
java vizualizator
Čvorovi sa žutom bojom još nisu posjećeni. Sada ćemo preći čvorove gornjeg stabla koristeći obilazak po redoslijedu.
- Ovdje je 40 korijenski čvor. Premještamo se na lijevo podstablo od 40, to je 30, a ono također ima podstablo 25, tako da se ponovno pomičemo na lijevo podstablo od 25, to je 15. Ovdje 15 nema podstablo, tako da ispis 15 i pomaknuti se prema roditeljskom čvoru, 25.
- Sada, ispis 25 i pomaknite se na desno podstablo od 25.
- Sada, ispis 28 i pomaknite se na korijenski čvor od 25, to jest 30.
- Dakle, posjećeno je lijevo podstablo od 30. Sada, ispis 30 i pomaknite se na desno dijete od 30.
- Sada, ispis 35 i pomaknite se na korijenski čvor od 30.
- Sada, ispis korijenskog čvora 40 i pomaknite se na njegovo desno podstablo.
- Sada rekurzivno prijeđite desnim podstablom od 40, odnosno 50.
50 ima podstablo pa prvo prijeđi lijevo podstablo 50 koje je 45. 45 nema djece, pa ispis 45 i pomaknite se na svoj korijenski čvor.
- Sada ispis 50 i pomaknite se na desno podstablo od 50, to jest 60.
- Sada rekurzivno prijeđite desnim podstablom od 50 koje je 60. 60 ima podstablo pa prvo prijeđite lijevom podstablom od 60 koje je 55. 55 nema djece, tako da ispis 55 i pomaknite se na svoj korijenski čvor.
- Sada ispis 60 i pomaknite se na desno podstablo od 60, to jest 70.
- Sada ispis 70.
Nakon završetka obilaska po redu, konačni izlaz je -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Složenost obilaska Inordera
Vremenska složenost obilaska Inordera je Na), gdje je 'n' veličina binarnog stabla.
Dok je prostorna složenost neurednog obilaženja O(1), ako ne uzmemo u obzir veličinu stoga za pozive funkcija. U suprotnom, prostorna složenost neurednog obilaska je Oh), gdje je 'h' visina stabla.
ako po Rudyardu Kiplingu sažetak
Implementacija obilaska reda
Pogledajmo sada implementaciju obilaska po redoslijedu u različitim programskim jezicima.
Program: Napišite program za implementaciju obilaska po redoslijedu u C jeziku.
#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; } Izlaz
Program: Napišite program za implementaciju obilaska po redoslijedu u 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></'
></'> Izlaz
Program: Napišite program za implementaciju obilaska po redoslijedu u 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(); } } Izlaz
Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.