在 Java 中實現樹

Rupam Yadav 2023年10月12日

Java Java Tree Java Binary Tree

使用遞迴方法實現樹
在 Java 中使用通用方法和 ArrayList 建立樹

在本教程中，我們將看到兩種在 Java 中建立樹結構的方法。樹結構在多種方面都很有用，例如建立資料夾和檔名的目錄。

使用遞迴方法實現樹

在這個例子中，我們建立了最多有兩個子節點的二叉樹，一個在左邊，另一個在右邊。根節點是所有子節點的父節點。每個節點儲存一個值。下面，我們上兩節課；一個是代表樹中節點的 Node，另一個是對節點執行操作的 JavaTree 類。

Node 類具有三個變數，第一個是要儲存在 int 資料型別的節點中的值。然後我們取兩個變數，分別用於 left 和 right 子節點；兩個變數都是 Node 型別。我們建立 Node 類的建構函式並從引數初始化 value；左右變數設定為空。

在 JavaTree 類中，我們採用一個 Node 型別的變數並將其命名為 root。然後我們建立一個方法 traverseRecursionTree()，它以 Node 作為引數，在該方法中，我們檢查 node 是否為 null；如果不是，那麼我們從自身呼叫 traverseRecursionTree() 方法並傳遞 node 的 left 部分。之後，我們列印 node 的 value 並再次從自身呼叫該方法並傳遞 right node。從自身呼叫函式的過程稱為遞迴。

在 main() 方法中，我們建立了一個 javaTree 物件，然後初始化所有變數，如根、根的左孩子和右孩子。我們還製作了根的孩子的左孩子。我們使用包含所有子節點的 javaTree.root 列印整個樹。

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

輸出：

Binary Tree:  3 6 10 5

在 Java 中使用通用方法和 `ArrayList` 建立樹

在前面的方法中，我們僅限於一種型別的資料作為 int 節點中的值。在這個程式中，我們使用泛型方法，允許我們使用我們選擇的任何資料型別。我們有一個類 Node<T>，這裡 <T> 告訴我們可以使用任何資料型別作為字串。在類中，我們宣告瞭三個變數，首先是型別為 T 的 root，然後是型別為 Node<T> 的 parent，最後是名為 Node<T> 的 ArrayList 作為 child。

在 Node 的建構函式中，我們將 T 型別的 root 設定為類變數 root。然後我們初始化 children ArrayList。現在，為了在 parent 中新增孩子，我們建立了一個 addChild() 函式，該函式採用 T 型別的 child。在 addChild() 函式中，我們建立了一個 Node<T> - childNode 的物件，並使用 this 關鍵字將其父級的上下文設定為當前類的上下文。接下來，我們獲取 children ArrayList，新增 childNode，並返回 childNode。

我們在 Node<T> 類中有多個方法可以用來執行操作，例如返回 root 的 getRoot() 方法，isRoot() 函式檢查當前節點是否是 root。我們建立了一個 getLevel() 函式，它返回樹中節點的級別。最後，我們覆蓋了一個 toString() 方法，如果它不為空，則返回整個樹。

現在我們建立具有 main() 方法的 Javatree 類。我們在類中建立 Node<String> 的 x 和 y。在這裡，我們使用 String 作為型別。在兩個建構函式中，我們都傳遞了每棵樹的根。我們使用 getRoot() 列印 root，然後我們建立一個名為 child1 的 Node<String> 物件，並使用 x 物件呼叫 addChild() 方法，這裡我們傳遞的值 child1 作為引數。在 child1 塊中，我們使用其物件建立 child1 的三個孩子並呼叫 addChild()。

我們使用相同的過程建立另一個名為 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());
    }
  }
}

輸出：

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

作者： Rupam Yadav

Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.

使用遞迴方法實現樹

在 Java 中使用通用方法和 ArrayList 建立樹

相關文章 - Java Tree

在 Java 中使用通用方法和 `ArrayList` 建立樹