在 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` 创建树