Neste artigo, discutiremos o percurso inorder na estrutura de dados.
Se quisermos percorrer os nós em ordem crescente, usamos o percurso em ordem. A seguir estão as etapas necessárias para a passagem em ordem:
- Visite todos os nós na subárvore esquerda
- Visite o nó raiz
- Visite todos os nós na subárvore certa
Estruturas de dados lineares, como pilha, array, fila, etc., só têm uma maneira de percorrer os dados. Mas em estruturas de dados hierárquicas como árvore, existem várias maneiras de percorrer os dados. Aqui discutiremos outra maneira de percorrer a estrutura de dados em árvore, ou seja, travessia em ordem.
Existem duas abordagens usadas para a travessia em ordem:
- Travessia em ordem usando recursão
- Travessia Inorder usando um método iterativo
Uma técnica de travessia em ordem segue o Raiz Esquerda Direita política. Aqui, Left Root Right significa que a subárvore esquerda do nó raiz é percorrida primeiro, depois o nó raiz e, em seguida, a subárvore direita do nó raiz é percorrida. Aqui, o próprio nome da ordem sugere que o nó raiz está entre as subárvores esquerda e direita.
Discutiremos o percurso em ordem usando técnicas recursivas e iterativas. Vamos primeiro começar com a travessia em ordem usando recursão.
Travessia em ordem usando recursão
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Exemplo de passagem em ordem
Agora, vamos ver um exemplo de travessia em ordem. Será mais fácil entender o procedimento de passagem inorder usando um exemplo.
programas de amostra java
Os nós com cor amarela ainda não foram visitados. Agora, percorreremos os nós da árvore acima usando travessia em ordem.
- Aqui, 40 é o nó raiz. Passamos para a subárvore esquerda de 40, que é 30, e ela também tem a subárvore 25, então passamos novamente para a subárvore esquerda de 25, que é 15. Aqui, 15 não tem subárvore, então imprimir 15 e vá em direção ao seu nó pai, 25.
- Agora, imprimir 25 e vá para a subárvore direita de 25.
- Agora, imprimir 28 e vá para o nó raiz de 25 que é 30.
- Portanto, a subárvore esquerda de 30 é visitada. Agora, imprimir 30 e passar para o filho certo de 30.
- Agora, imprimir 35 e vá para o nó raiz de 30.
- Agora, imprimir nó raiz 40 e vá para sua subárvore direita.
- Agora percorra recursivamente a subárvore direita de 40 que é 50.
50 tem subárvore, então primeiro percorra a subárvore esquerda de 50 que é 45. 45 não tem filhos, então imprimir 45 e vá para seu nó raiz.
- Agora imprimir 50 e vá para a subárvore direita de 50 que é 60.
- Agora percorra recursivamente a subárvore direita de 50 que é 60. 60 tem subárvore, então primeiro percorra a subárvore esquerda de 60 que é 55. 55 não tem filhos, então imprimir 55 e vá para seu nó raiz.
- Agora imprimir 60 e vá para a subárvore direita de 60 que é 70.
- Agora imprimir 70.
Após a conclusão da passagem em ordem, o resultado final é -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Complexidade da travessia Inorder
A complexidade de tempo da travessia Inorder é Sobre), onde 'n' é o tamanho da árvore binária.
Considerando que a complexidade espacial da travessia em ordem é O(1), se não considerarmos o tamanho da pilha para chamadas de função. Caso contrário, a complexidade espacial da travessia em ordem é Oh), onde 'h' é a altura da árvore.
mostrar aplicativos ocultos
Implementação de travessia Inorder
Agora, vamos ver a implementação do percurso inorder em diferentes linguagens de programação.
Programa: Escreva um programa para implementar travessia em ordem em linguagem 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; } Saída
Programa: Escreva um programa para implementar travessia em ordem em 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></'
></'> Saída
Programa: Escreva um programa para implementar travessia em ordem em 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(); } } Saída
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.