Baum in Java implementieren

1. Implementieren eines Baums mit der Rekursionsmethode
2. Erstellen Sie einen Baum in Java mit der generischen Methode und ArrayList

In diesem Tutorial sehen wir zwei Möglichkeiten, eine Baumstruktur in Java zu erstellen. Eine Baumstruktur kann auf verschiedene Weise nützlich sein, z. B. beim Erstellen eines Verzeichnisses mit Ordnern und Dateinamen.

Implementieren eines Baums mit der Rekursionsmethode

In diesem Beispiel erstellen wir einen binären Baum mit höchstens zwei Kindern, einem links und einem rechts. Der Wurzelknoten ist der übergeordnete Knoten aller untergeordneten Knoten. Jeder Knoten speichert einen Wert. Unten nehmen wir zwei Klassen; eine ist Node, die einen Knoten im Baum darstellt, und die andere ist die Klasse JavaTree, die Operationen auf den Knoten ausführt.

Die Klasse Node hat drei Variablen, die erste ist der Wert, der im Knoten vom Datentyp int gespeichert werden soll. Dann nehmen wir zwei Variablen für left und right Kindknoten; beide Variablen sind vom Typ Node. Wir machen einen Konstruktor der Klasse Node und initialisieren den Wert aus dem Parameter; die linken und rechten Variablen werden auf null gesetzt.

In der Klasse JavaTree nehmen wir eine Variable vom Typ Node und nennen sie root. Dann erstellen wir eine Methode traverseRecursionTree(), die einen Node als Parameter übernimmt, und innerhalb der Methode prüfen wir, ob der node null ist; wenn nicht, dann rufen wir die Methode traverseRecursionTree() von sich selbst auf und übergeben den linken Teil von node. Danach geben wir den value des Knotens aus und rufen die Methode erneut von sich selbst auf und übergeben den richtigen Node. Der Vorgang des Aufrufens der Funktion von sich selbst wird als Rekursion bezeichnet.

In der Methode main() erstellen wir ein Objekt von javaTree und initialisieren dann alle Variablen wie root, linkes Kind von root und rechtes Kind. Wir machen auch ein linkes Kind aus dem Kind der Wurzel. Wir drucken den ganzen Baum mit javaTree.root, der alle Kinder enthält.

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

Ausgabe:

Binary Tree:  3 6 10 5

Erstellen Sie einen Baum in Java mit der generischen Methode und ArrayList

Bei der vorherigen Methode waren wir auf nur einen Datentyp als Wert in den int-Knoten beschränkt. In diesem Programm verwenden wir die generische Methode, die es uns ermöglicht, jeden Datentyp unserer Wahl zu verwenden. Wir haben eine Klasse Node<T>, hier sagt <T>, dass wir jeden Datentyp als String verwenden können. In der Klasse deklarieren wir drei Variablen, zuerst ist die root vom Typ T, dann haben wir parent vom Typ Node<T> und zum Schluss eine ArrayList von Node<T> namens als Kinder.

Im Konstruktor von Node nehmen wir root vom Typ T und setzen ihn auf die Klassenvariable root. Dann initialisieren wir die children ArrayList. Um nun Kinder zum Elternteil hinzuzufügen, erstellen wir eine addChild()-Funktion, die ein child vom Typ T annimmt. In der Funktion addChild() erstellen wir ein Objekt von Node<T> - childNode und setzen den Kontext seiner Eltern mit dem Schlüsselwort this als Kontext der aktuellen Klasse. Als nächstes nehmen wir die ArrayList children, fügen den childNode hinzu und geben den childNode zurück.

Wir haben mehrere Methoden in der Klasse Node<T>, mit denen wir Operationen wie die Methode getRoot() ausführen können, die die root zurückgibt, die Funktion isRoot() prüft, ob der aktuelle Knoten ein Wurzel. Wir erstellen eine Funktion getLevel(), die die Ebene des Knotens im Baum zurückgibt. Schließlich überschreiben wir eine Methode toString(), um den gesamten Baum zurückzugeben, wenn er nicht null ist.

Nun erstellen wir die Klasse Javatree mit der Methode main(). Wir erzeugen x und y von Node<String> in der Klasse. Hier verwenden wir String als Typ. In beiden Konstruktoren übergeben wir die Wurzel jedes Baums. Wir drucken die root mit getRoot() und erstellen dann ein Objekt von Node<String> namens child1 und rufen die Methode addChild() mit dem x-Objekt auf, hier übergeben wir den Wert von Kind1 als Argument. Im Block von child1 erzeugen wir mit seinem Objekt drei Kinder von child1 und rufen addChild() auf.

Wir verwenden das gleiche Verfahren, um einen weiteren Baum mit dem Namen child2 zu erstellen.

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

Ausgabe:

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