Neste artigo, discutiremos a travessia de pré-ordem na estrutura de dados. Estruturas de dados lineares, como pilha, array, fila, etc., só têm uma maneira de percorrer os dados. Mas em uma estrutura de dados hierárquica como árvore , existem várias maneiras de percorrer os dados.
Na travessia de pré-ordem, primeiro o nó raiz é visitado, depois a subárvore esquerda e depois a subárvore direita é visitada. O processo de passagem da pré-encomenda pode ser representado como -
root → left → right
O nó raiz é sempre percorrido primeiro na travessia de pré-ordem, enquanto é o último item da travessia de pós-ordem. A travessia de pré-ordem é usada para obter a expressão de prefixo de uma árvore.
As etapas para realizar a passagem da pré-encomenda estão listadas a seguir -
travessia de pré-encomenda de uma árvore
- Primeiro, visite o nó raiz.
- Então, visite a subárvore esquerda.
- Por fim, visite a subárvore certa.
A técnica de passagem de pré-ordem segue o Raiz Esquerda Direita política. O próprio nome pré-encomenda sugere que o nó raiz seria percorrido primeiro.
Algoritmo
Agora, vamos ver o algoritmo de travessia de pré-ordem.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
Exemplo de passagem de pré-encomenda
Agora, vamos ver um exemplo de passagem de pré-encomenda. Será mais fácil entender o processo de passagem da pré-encomenda usando um exemplo.
Os nós com cor amarela ainda não foram visitados. Agora, percorreremos os nós da árvore acima usando travessia de pré-ordem.
- Comece com o nó raiz 40. Primeiro, imprimir 40 e então percorrer recursivamente a subárvore esquerda.
- Agora, vá para a subárvore esquerda. Para a subárvore esquerda, o nó raiz é 30. Imprimir 30 e vá em direção à subárvore esquerda de 30.
- Na subárvore esquerda de 30, existe um elemento 25, então imprimir 25 e percorra a subárvore esquerda de 25.
- Na subárvore esquerda de 25, existe um elemento 15 e 15 não possui subárvore. Então, imprimir 15 e vá para a subárvore direita de 25.
- Na subárvore direita de 25, há 28 e 28 não tem subárvore. Então, imprimir 28 e vá para a subárvore direita de 30.
- Na subárvore direita de 30, há 35 que não possui subárvore. Então imprimir 35 e percorra a subárvore direita de 40.
- Na subárvore direita de 40, há 50. Imprimir 50 e percorra a subárvore esquerda de 50.
- Na subárvore esquerda de 50, há 45 que não têm filhos. Então, imprimir 45 e percorra a subárvore direita de 50.
- Na subárvore direita de 50, há 60. Imprimir 60 e atravesse a subárvore esquerda de 60.
- Na subárvore esquerda de 60, há 55 que não tem nenhum filho. Então, imprimir 55 e vá para a subárvore direita de 60.
- Na subárvore direita de 60, há 70 que não têm filhos. Então, imprimir 70 e pare o processo.
Após a conclusão da passagem da pré-encomenda, o resultado final é -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
java matemática aleatória
Complexidade da travessia da pré-encomenda
A complexidade de tempo da passagem da pré-encomenda é Sobre) , onde 'n' é o tamanho da árvore binária.
Considerando que a complexidade espacial da travessia da pré-ordem é O(1) , se não considerarmos o tamanho da pilha para chamadas de função. Caso contrário, a complexidade espacial da travessia da pré-ordem é Oh) , onde 'h' é a altura da árvore.
Implementação de travessia de pré-pedido
Agora, vamos ver a implementação do percurso de pré-ordem em diferentes linguagens de programação.
Programa: Escreva um programa para implementar a travessia de pré-ordem em linguagem C.
feijão java
#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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(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 Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } Saída
Após a execução do código acima, a saída será -
Programa: Escreva um programa para implementar a travessia de pré-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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->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 preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder 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 traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-16.webp" alt="Preorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Saída
Após a execução do código acima, a saída será -
Programa: Escreva um programa para implementar a travessia de pré-ordem em Java.
10 milhões
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } Saída
Após a execução do código acima, a saída será -
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.