Árvore em Java

Afluentes: Estrutura de Dados

Classe do Nó

 1class Node {                    // Classe do nó
 2    int info;                   // Informação tipo inteiro
 3    Node left;                  // Filho à esquerda
 4    Node right;                 // FIlho à direita
 5
 6    Node(int info) {            // Inicializa os atributos da classe
 7        this.info = info;       // Inicializa a informação com o parâmetro recebido
 8        this.left = null;       // Inicializa o filho à esquerda como vazio
 9        this.right = null;      // Inicializa o filho à direita como vazio
10    }
11}

Casse da Árvore

 1class Tree {                                        // Classe da Árvore
 2    Node root = null;                               // Nó pai, ou raíz
 3
 4    void insert(int info, Node place) {             // algoritmo para inserir uma informação
 5        if (place == null) {                        // Se o local está vazio, então a árvore está vazia
 6            root = new Node(info);                  // e o root vai receber o novo nó
 7            System.out.print(" " + info);           // Imprime a informação inserida
 8        } else if (info < place.info) {             // Senão, se a informação é menor do que a do local
 9            if (place.left == null) {               // Se o filho da esquerda está vazio
10                place.left = new Node(info);        // Então insere à esquerda o novo nó
11                System.out.print(" " + info);       // Imprime a informação inserida
12            } else {                                // São, se não for vazio
13                insert(info, place.left);           // Pula para o filho à esquerda usando a recursividade
14            }
15        } else if (info > place.info) {             // Senão, se a informação é maior que a do local
16            if (place.right == null) {              // Se o filho à direita está vazio
17                place.right = new Node(info);       // Insere a informação em um novo nó à direita
18                System.out.print(" " + info);       // e imprime a informação
19            } else {                                // Senão, se o nó à direita não está vazio
20                insert(info, place.right);          // Pula para o filho à direita usando a recursividade
21            }
22        }
23    }
24
25    void preOrder(Node place) {                     // Algoritmo de navegação em pré ordem
26        System.out.print(" " + place.info);         // Primeiro imprime a informação do nó
27        if (place.left != null) {                   // Se o filho à esquerda não está vazio
28            preOrder(place.left);                   // Pula para o filho à esquerda pela recursividade
29        }
30        if (place.right != null) {                  // Se filho à direita não está vazio
31            preOrder(place.right);                  // Pula para o filho à direita pela recursividade
32        }
33    }
34
35    void inOrder(Node place) {                      // Algoritmo de navegação em ordem
36        if (place.left != null) {                   // Se o filho à esquerda não está vazio
37            inOrder(place.left);                    // Pula para o filho à esquerda pela recursividade
38        }
39        System.out.print(" " + place.info);         // Depois imprime a informação do nó
40        if (place.right != null) {                  // Se filho à direita não está vazio
41            inOrder(place.right);                   // Pula para o filho à direita pela recursividade
42        }
43    }
44
45    void postOrder(Node place) {                    // Algoritmo de navegação em pós ordem
46        if (place.left != null) {                   // Se o filho à esquerda não está vazio
47            postOrder(place.left);                  // Pula para o filho à esquerda pela recursividade
48        }
49        if (place.right != null) {                  // Se filho à direita não está vazio
50            postOrder(place.right);                 // Pula para o filho à direita pela recursividade
51        }
52        System.out.print(" " + place.info);         // Por último, imprime a informação do nó
53    }
54}

Programa exemplo

 1import java.util.Random;                                // Usa a biblioteca de randomização
 2
 3class Main {                                            // Classe do programa principal
 4    public static void main(String[] args) {            // função incial do programa
 5        Random rand = new Random();                     // Inicializa a randomização
 6        Tree tree = new Tree();                         // Cria uma árvore binária
 7
 8        for (int i = 0; i < 10; i++) {                  // Fazer 10 vezes
 9            tree.insert(rand.nextInt(100), tree.root);  // Insere um elemento aleatório de 0 até 99
10        }
11
12        System.out.println("\nPRE-ORDER:");
13        tree.preOrder(tree.root);                       // Navega a árvore em pré ordem
14
15        System.out.println("\nIN-ORDER:");
16        tree.inOrder(tree.root);                        // Navega a árvore em ordem
17
18        System.out.println("\nPOST-ORDER:");
19        tree.postOrder(tree.root);                      // Navega a árvore em pós ordem
20    }
21}