Java：使用递归构建多叉树_技术教程

本文旨在讲解如何使用递归方法在 Java 中构建多叉树，尤其针对每个节点拥有固定数量子节点的情况。通过一个具体的示例，展示了如何将原本通过方法链式调用实现的多层子节点添加，转化为简洁高效的递归实现，并提供了优化后的代码示例和注意事项。

递归构建多叉树

多叉树是一种树状数据结构，其中每个节点可以拥有多个子节点。在某些情况下，我们需要按照特定的深度来构建这种树。传统的做法可能涉及多层嵌套循环或方法链式调用，这既不优雅也不易于维护。递归提供了一种更简洁、更易于理解的解决方案。

示例：构建七叉树

假设我们需要构建一棵特殊的七叉树，即每个节点都有 7 个子节点，并且我们需要控制树的深度。

首先，我们定义一个 MyTreeNode 类：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MyTreeNode {
    private int[][] grid;
    private List children = new ArrayList<>();
    private MyTreeNode parent = null;

    public MyTreeNode(int[][] grid) {
        this.grid = grid;
    }

    public void addChild(MyTreeNode child) {
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(int[][] grid) {
        MyTreeNode newChild = new MyTreeNode(grid);
        this.addChild(newChild);
    }

    public void addChildren(List children) {
        for (MyTreeNode t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

    public List getChildren() {
        return children;
    }

    public int[][] getGrid() {
        return grid;
    }

    public void setGrid(int[][] grid) {
        this.grid = grid;
    }

    private void setParent(MyTreeNode parent) {
        this.parent = parent;
    }

    public MyTreeNode getParent() {
        return parent;
    }
}

接下来，我们定义添加子节点的方法 addChildren：

import java.util.Arrays;
import java.util.List;

private static void addChildren(MyTreeNode root) {
    root.addChildren(Arrays.asList(
            new MyTreeNode(new int[6][7]),
            new MyTreeNode(new int[6][7]),
            new MyTreeNode(new int[6][7]),
            new MyTreeNode(new int[6][7]),
            new MyTreeNode(new int[6][7]),
            new MyTreeNode(new int[6][7]),
            new MyTreeNode(new int[6][7])
    ));
}

最后，我们使用递归方法 depth 来构建指定深度的树：

public static void depth(MyTreeNode root, int n) {
    if (n <= 0) return; // 递归终止条件
    addChildren(root);
    for (MyTreeNode child : root.getChildren()) {
        depth(child, n - 1); // 递归调用
    }
}

代码解释

递归终止条件： if (n
添加子节点： addChildren(root); 为当前节点添加 7 个子节点。
递归调用： depth(child, n - 1); 对每个子节点进行递归调用，深度 n 减 1。

使用示例

public static void main(String[] args) {
    MyTreeNode root = new MyTreeNode(new int[6][7]);
    depth(root, 3); // 构建深度为 3 的七叉树
    System.out.println("Tree built successfully.");
}