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