Neste tutorial, você aprenderá sobre diferentes técnicas de travessia de árvore. Além disso, você encontrará exemplos funcionais de diferentes métodos de travessia de árvore em C, C ++, Java e Python.
Percorrer uma árvore significa visitar todos os nós da árvore. Você pode, por exemplo, querer adicionar todos os valores na árvore ou encontrar o maior. Para todas essas operações, você precisará visitar cada nó da árvore.
Estruturas de dados lineares como matrizes, pilhas, filas e lista vinculada têm apenas uma maneira de ler os dados. Mas uma estrutura de dados hierárquica como uma árvore pode ser percorrida de maneiras diferentes.
Travessia de árvore
Vamos pensar em como podemos ler os elementos da árvore da imagem mostrada acima.
Começando de cima, da esquerda para a direita
1 -> 12 -> 5 -> 6 -> 9
Começando de baixo, da esquerda para a direita
5 -> 6 -> 12 -> 9 -> 1
Embora esse processo seja um tanto fácil, ele não respeita a hierarquia da árvore, apenas a profundidade dos nós.
Em vez disso, usamos métodos de passagem que levam em consideração a estrutura básica de uma árvore, ou seja,
struct node ( int data; struct node* left; struct node* right; )
O nó de estrutura apontado por left e right pode ter outros filhos esquerdo e direito, então devemos pensar neles como subárvores em vez de subnós.
De acordo com esta estrutura, cada árvore é uma combinação de
- Um nó carregando dados
- Duas subárvores
Subárvore Esquerda e Direita
Lembre-se de que nosso objetivo é visitar cada nó, portanto, precisamos visitar todos os nós na subárvore, visitar o nó raiz e visitar todos os nós na subárvore certa.
Dependendo da ordem em que fazemos isso, pode haver três tipos de travessia.
Travessia em ordem
- Primeiro, visite todos os nós na subárvore esquerda
- Então o nó raiz
- Visite todos os nós na subárvore certa
inorder(root->left) display(root->data) inorder(root->right)
Pré-encomenda de travessia
- Visite o nó raiz
- Visite todos os nós na subárvore esquerda
- Visite todos os nós na subárvore certa
display(root->data) preorder(root->left) preorder(root->right)
Postorder traversal
- Visite todos os nós na subárvore esquerda
- Visite todos os nós na subárvore certa
- Visite o nó raiz
postorder(root->left) postorder(root->right) display(root->data)
Vamos visualizar o percurso em ordem. Começamos do nó raiz.
Subárvore Esquerda e Direita
Atravessamos a subárvore esquerda primeiro. Também precisamos nos lembrar de visitar o nó raiz e a subárvore correta quando esta árvore estiver pronta.
Vamos colocar tudo isso em uma pilha para que possamos lembrar.
Pilha
Agora, vamos até a subárvore apontada no topo da pilha.
Novamente, seguimos a mesma regra de ordem
Subárvore esquerda -> raiz -> subárvore direita
Depois de atravessar a subárvore esquerda, ficamos com
Pilha Final
Como o nó "5" não possui subárvores, nós o imprimimos diretamente. Depois disso, imprimimos seu pai "12" e o filho certo "6".
Colocar tudo em uma pilha foi útil porque agora que a subárvore esquerda do nó raiz foi percorrida, podemos imprimi-la e ir para a subárvore direita.
Depois de passar por todos os elementos, obtemos a travessia em ordem como
5 -> 12 -> 6 -> 1 -> 9
Não precisamos criar a pilha porque a recursão mantém a ordem correta para nós.
Exemplos de Python, Java e C / C ++
Python Java C C + # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
// Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);
