Implementar árbol en Java

1. Implementar un árbol mediante el método de recursividad
2. Cree un árbol en Java usando el método genérico y ArrayList

En este tutorial, veremos dos formas de hacer una estructura de árbol en Java. Una estructura de árbol puede resultar útil de varias formas, como crear un directorio de carpetas y nombres de archivos.

Implementar un árbol mediante el método de recursividad

En este ejemplo, creamos un árbol binario con dos hijos como máximo, uno a la izquierda y otro a la derecha. El nodo raíz es el padre de todos los nodos hijos. Cada nodo almacena un valor. A continuación, tomamos dos clases; uno es Node que representa un nodo en el árbol, y el otro es la clase JavaTree que realiza operaciones en los nodos.

La clase Node tiene tres variables, la primera es el valor a almacenar en el nodo que es del tipo de datos int. Luego tomamos dos variables, para los nodos hijos izquierdo y derecho; ambas variables son de tipo Node. Hacemos un constructor de la clase Node e inicializamos el valor del parámetro; las variables izquierda y derecha se establecen como null.

En la clase JavaTree, tomamos una variable de tipo Node y la llamamos root. Luego creamos un método traverseRecursionTree() que toma un Node como parámetro, y dentro del método, verificamos si el Node es null; si no es así, llamamos al método traverseRecursionTree() desde sí mismo y pasamos la parte izquierda de Node. Después de eso, imprimimos el value del Node y de nuevo llamamos al método desde sí mismo y pasamos el Node derecho. El proceso de llamar a la función desde sí mismo se llama recursividad.

En el método main(), creamos un objeto de javaTree y luego inicializamos todas las variables como la raíz, el hijo izquierdo de la raíz y el hijo derecho. También hacemos un hijo izquierdo del hijo de la raíz. Imprimimos el árbol completo usando javaTree.root que contiene todos los hijos.

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);
  }
}

Producción :

Binary Tree:  3 6 10 5

Cree un árbol en Java usando el método genérico y ArrayList

En el método anterior, estábamos limitados a un solo tipo de datos como valor en los nodos int. En este programa, usamos el método genérico que nos permite usar cualquier tipo de datos de nuestra elección. Tenemos una clase Node<T>, aquí <T> dice que podemos usar cualquier tipo de datos como String. En la clase declaramos tres variables, primero es la root que es de tipo T, luego tenemos parent de tipo Node<T> y finalmente una ArrayList de Node<T> denominada como niños.

En el constructor de Node, tomamos root de tipo T y lo asignamos a la variable de clase root. Luego inicializamos el ArrayList children. Ahora, para agregar hijos en el parent creamos una función addChild() que toma un hijo de tipo T. En la función addChild(), creamos un objeto de Node<T> - childNode y establecemos el contexto de su padre como el contexto de la clase actual usando la palabra clave this. A continuación, tomamos el ArrayList children, agregamos el childNode y devolvemos el childNode.

Tenemos varios métodos en la clase Node<T> que podemos usar para realizar operaciones como el método getRoot() que devuelve la root, la función isRoot() comprueba si el nodo actual es un root. Creamos una función getLevel() que devuelve el nivel del nodo en el árbol. Por último, anulamos un método toString() para devolver el árbol completo si no es nulo.

Ahora creamos la clase Javatree que tiene el método main(). Creamos x e y de Node<String> en la clase. Aquí, usamos String como tipo. En ambos constructores, pasamos la raíz de cada árbol. Imprimimos la root usando getRoot() y luego creamos un objeto de Node<String> llamado child1 y llamamos al método addChild() usando el objeto x, aquí pasamos el valor de child1 como argumento. En el bloque de child1, creamos tres hijos de child1 usando su objeto y llamamos a addChild().

Usamos el mismo proceso para crear otro árbol con el nombre niño2.

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());
    }
  }
}

Producción :

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