В тази статия ще обсъдим обхождането по ред в структурата на данните.
изпитване и видове изпитване
Ако искаме да обходим възлите във възходящ ред, тогава използваме обхождането по ред. Следват стъпките, необходими за преминаване по ред:
- Посетете всички възли в лявото поддърво
- Посетете основния възел
- Посетете всички възли в дясното поддърво
Линейните структури от данни като стек, масив, опашка и т.н. имат само един начин за преминаване през данните. Но в йерархични структури от данни като напр дърво, има множество начини за преминаване на данните. Тук ще обсъдим друг начин за преминаване през дървовидната структура на данните, т.е. преминаване по ред.
Има два подхода, използвани за преминаване по ред:
- Обхождане по ред с помощта на рекурсия
- Обхождане по ред с помощта на итеративен метод
Следва техника на нередовно преминаване Ляво коренно дясно политика. Тук Left Root Right означава, че първо се преминава през лявото поддърво на основния възел, след това през основния възел и след това се преминава през дясното поддърво на основния възел. Тук самото име на ред подсказва, че коренният възел идва между лявото и дясното поддървета.
Ще обсъдим преминаването по ред, използвайки както рекурсивни, така и итеративни техники. Нека първо започнем с обхождане по ред, използвайки рекурсия.
Обхождане по ред с помощта на рекурсия
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}
Сложност на обхождането на Inorder
Времевата сложност на Inorder traversal е На), където 'n' е размерът на двоичното дърво.
Докато пространствената сложност на преминаването по ред е O(1), ако не вземем предвид размера на стека за извиквания на функции. В противен случай пространствената сложност на преминаването по ред е O(h), където 'h' е височината на дървото.
Внедряване на Inorder traversal
Сега, нека видим изпълнението на обхождането по ред в различни езици за програмиране.
програма: Напишете програма за реализиране на обхождане по ред на език 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; } Изход
програма: Напишете програма за прилагане на обхождане по ред в 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></'
></'> Изход
програма: Напишете програма за прилагане на обхождане по ред в 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(); } } Изход
И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.