在 Java 中實現樹

Rupam Yadav 2023年1月30日 2021年10月2日

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

Author: 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` 建立樹