Implementar árvore em Java

1. Implementar uma árvore usando o método de recursão
2. Crie uma árvore em Java usando o método genérico e ArrayList

Neste tutorial, veremos duas maneiras de fazer uma estrutura em árvore em Java. Uma estrutura em árvore pode ser útil de várias maneiras, como criar um diretório de pastas e nomes de arquivos.

Implementar uma árvore usando o método de recursão

Neste exemplo, criamos uma árvore binária com no máximo dois filhos, um à esquerda e outro à direita. O nó raiz é o pai de todos os nós filhos. Cada nó armazena um valor. Abaixo, tomamos duas aulas; um é Node que representa um nó na árvore e o outro é a classe JavaTree que executa operações nos nós.

A classe Node tem três variáveis, a primeira é o valor a ser armazenado no nó que é do tipo de dados int. Em seguida, pegamos duas variáveis, para nós filhos left e right; ambas as variáveis ​​são do tipo Node. Fazemos um construtor da classe Node e inicializamos o value do parâmetro; as variáveis ​​esquerda e direita são definidas como null.

Na classe JavaTree, pegamos uma variável do tipo Node e a chamamos de root. Em seguida, criamos um método traverseRecursionTree() que recebe um Node como parâmetro e, dentro do método, verificamos se o Node é null; se não for, então chamamos o método traverseRecursionTree() dele mesmo e passamos a parte esquerda de Node. Depois disso, imprimimos o value do Node e chamamos novamente o método a partir dele próprio e passamos o Node certo. O processo de chamar a função por si só é chamado de recursão.

No método main(), criamos um objeto de javaTree e, em seguida, inicializamos todas as variáveis ​​como a raiz, o filho esquerdo da raiz e o filho direito. Também criamos um filho esquerdo do filho da raiz. Imprimimos a árvore inteira usando javaTree.root que contém todos os filhos.

class Node {
  int value;
  Node left;
  Node right;

  public Node(int value) {
    this.value = value;
    left = null;
    right = null;
  }
}

public class JavaTree {
  Node root;

  public void traverseRecursionTree(Node node) {
    if (node != null) {
      traverseRecursionTree(node.left);
      System.out.print(" " + node.value);
      traverseRecursionTree(node.right);
    }
  }

  public static void main(String[] args) {
    JavaTree javaTree = new JavaTree();

    javaTree.root = new Node(10);
    javaTree.root.left = new Node(6);
    javaTree.root.right = new Node(5);
    javaTree.root.left.left = new Node(3);

    System.out.print("Binary Tree: ");

    javaTree.traverseRecursionTree(javaTree.root);
  }
}

Produção:

Binary Tree:  3 6 10 5

Crie uma árvore em Java usando o método genérico e ArrayList

No método anterior, estávamos limitados a apenas um tipo de dados como o valor nos nós int. Neste programa, usamos o método genérico que nos permite usar qualquer tipo de dados de nossa escolha. Temos uma classe Node<T>, aqui <T> diz que podemos usar qualquer tipo de dados como String. Na classe, declaramos três variáveis, primeiro é a root que é do tipo T, então temos parent do tipo Node<T> e finalmente uma ArrayList de Node<T> nomeada como crianças.

No construtor de Node, pegamos root do tipo T e configuramos para a variável de classe root. Em seguida, inicializamos a ArrayList children. Agora, para adicionar filhos no parent, criamos uma função addChild() que recebe um filho do tipo T. Na função addChild(), criamos um objeto de Node<T> - childNode e definimos o contexto de seu pai como o contexto da classe atual usando a palavra-chave this. Em seguida, pegamos a ArrayList children, adicionamos childNode e retornamos childNode.

Temos vários métodos na classe Node<T> que podemos usar para realizar operações como o método getRoot() que retorna a root, a função isRoot() verifica se o nó atual é um root. Criamos uma função getLevel() que retorna o nível do nó na árvore. Por fim, substituímos um método toString() para retornar a árvore inteira se ela não for nula.

Agora criamos a classe Javatree que possui o método main(). Criamos x e y de Node <> na classe. Aqui, usamos String como o tipo. Em ambos os construtores, passamos a raiz de cada árvore. Imprimimos a root usando getRoot() e então criamos um objeto de Node<String> chamado child1 e chamamos o método addChild() usando o objeto x, aqui passamos o valor de Filho1 como argumento. No bloco de child1, criamos três filhos de child1 usando seu objeto e chamamos addChild().

Usamos o mesmo processo para criar outra árvore com o nome child2.

import java.util.ArrayList;

class Node<T> {
  private final T root;
  private Node<T> parent;
  private final ArrayList<Node<T>> children;

  public Node(T root) {
    this.root = root;
    children = new ArrayList<>();
  }

  public Node<T> addChild(T child) {
    Node<T> childNode = new Node<T>(child);
    childNode.parent = this;
    this.children.add(childNode);
    return childNode;
  }

  public T getRoot() {
    return root;
  }

  public boolean isRoot() {
    return parent == null;
  }

  public boolean isLeaf() {
    return children.size() == 0;
  }

  public int getLevel() {
    if (this.isRoot())
      return 0;
    else
      return parent.getLevel() + 1;
  }

  @Override
  public String toString() {
    return root != null ? root.toString() : "null";
  }
}

public class JavaTree {
  public static void main(String[] args) {
    Node<String> x = new Node<String>("parent1");
    Node<String> y = new Node<String>("parent2");

    System.out.println(x.getRoot());

    Node<String> child1 = x.addChild("child1");
    {
      Node<String> innerChild1 = child1.addChild("innerChild1OfChild1");
      Node<String> innerChild2 = child1.addChild("innerChild2OfChild1");
      Node<String> innerChild3 = child1.addChild("innerChild3OfChild1");

      System.out.println("-" + child1);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child1.getLevel());
      System.out.println("Level of innerChild2 in Child1: " + innerChild2.getLevel());
    }

    System.out.println();

    System.out.println(y.getRoot());

    Node<String> child2 = x.addChild("child2");
    {
      Node<String> innerChild1 = child2.addChild("innerChild2OfChild2");
      Node<String> innerChild2 = child2.addChild("innerChild3OfChild2");
      Node<String> innerChild3 = child2.addChild("innerChild4OfChild2");
      {
        Node<String> innerChild4 = innerChild3.addChild("innerChild4OfChild3");
        System.out.println(innerChild4.getLevel());
        System.out.println("\nIs inner Child4 Leaf? " + innerChild4.isLeaf());
      }

      System.out.println("-" + child2);

      System.out.println("--" + innerChild1);
      System.out.println("--" + innerChild2);
      System.out.println("--" + innerChild3);

      System.out.println("Level of child1: " + child2.getLevel());
      System.out.println("Level of innerChild2 in Child2: " + innerChild2.getLevel());
    }
  }
}

Produção:

parent1
-child1
--innerChild1OfChild1
--innerChild2OfChild1
--innerChild3OfChild1
Level of child1: 1
Level of innerChild2 in Child1: 2

parent2
3

Is inner Child4 Leaf? true
-child2
--innerChild2OfChild2
--innerChild3OfChild2
--innerChild4OfChild2
Level of child1: 1
Level of innerChild2 in Child2: 2