У овом чланку ћемо разговарати о обиласку у нередовном реду у структури података.
Ако желимо да пређемо чворове у растућем редоследу, онда користимо прелазак у нередовном реду. Следе кораци који су потребни за прелазак по редоследу:
- Посетите све чворове у левом подстаблу
- Посетите основни чвор
- Посетите све чворове у десном подстаблу
Линеарне структуре података као што су стек, низ, ред, итд., имају само један начин да прелазе податке. Али у хијерархијским структурама података као нпр дрво, постоји више начина да се пређу подаци. Овде ћемо разговарати о другом начину преласка структуре података стабла, тј.
Постоје два приступа која се користе за прелазак у редослед:
- Прелазак у ред помоћу рекурзије
- Прелазак у редослед коришћењем Итеративне методе
Техника преласка у редослед прати Лево Роот Десно политика. Овде, Лефт Роот Ригхт значи да се прво прелази лево подстабло коренског чвора, затим коренски чвор, а затим се прелази десно подстабло коренског чвора. Овде, само име у реду сугерише да се коренски чвор налази између левог и десног подстабла.
Разговараћемо о обиласку у нередовном реду користећи и рекурзивне и итеративне технике. Почнимо са обиласком у нередовном реду користећи рекурзију.
Прелазак у редослед коришћењем рекурзије
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Пример преласка у редослед
Сада, хајде да видимо пример преласка у неред. Биће лакше разумети процедуру обилажења по редоследу користећи пример.
иф елсе изјаве јава
Чворови жуте боје још нису посећени. Сада ћемо прећи преко чворова горњег стабла користећи прелазак у редослед.
- Овде, 40 је основни чвор. Прелазимо на лево подстабло од 40, то је 30, и оно такође има подстабло 25, па се поново крећемо на лево подстабло од 25 што је 15. Овде 15 нема подстабло, тако да штампа 15 и помери се ка свом родитељском чвору, 25.
- Сада, штампа 25 и померите се на десно подстабло од 25.
- Сада, штампа 28 и пређите на основни чвор од 25, што је 30.
- Дакле, посећено је лево подстабло од 30. Сада, штампа 30 и пређите на десно дете од 30 година.
- Сада, штампа 35 и пређите на основни чвор од 30.
- Сада, штампај основни чвор 40 и померите се на његово десно подстабло.
- Сада рекурзивно пређите десно подстабло од 40 што је 50.
50 има подстабло, тако да прво пређите лево подстабло од 50 које је 45. 45 нема деце, па штампа 45 и померите се до његовог коренског чвора.
- Сада штампа 50 и померите се на десно подстабло од 50, односно 60.
- Сада рекурзивно пређите десно подстабло од 50 које је 60. 60 има подстабло, тако да прво пређите лево подстабло од 60 које је 55. 55 нема деце, тако да штампа 55 и помери се на његов коренски чвор.
- Сада штампа 60 и померите се на десно подстабло од 60, односно 70.
- Сада штампа 70.
Након завршетка обиласка по редоследу, коначни излаз је -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Сложеност обиласка Инордер-а
Временска сложеност обиласка Инордер-а је На), где је 'н' величина бинарног стабла.
Док је просторна сложеност нередовног преласка О(1), ако не узмемо у обзир величину стека за позиве функција. Иначе, просторна сложеност обилажења у нередовном реду је О(х), где је 'х' висина дрвета.
маркдовн прецртано
Имплементација преласка Инордер-а
Сада, хајде да видимо имплементацију обиласка по редоследу у различитим програмским језицима.
Програм: Написати програм за имплементацију обиласка у нередовном реду у језику Ц.
#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; } Излаз
Програм: Напишите програм за имплементацију обиласка у нередовном реду у Ц++.
#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></'
></'> Излаз
Програм: Напишите програм за имплементацију обилажења нередом у Јави.
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(); } } Излаз
Дакле, то је све о чланку. Надамо се да ће вам чланак бити користан и информативан.