Java:如何递归填充树节点

Question

对于一个项目，我想生成一个树结构，它有 x 个子节点，深度为 n “层”。下图可以最好地描述一个层:

                  0
           1            1
        2     2      2     2

每行的数字等于层数。

我得到了以下名为 Node 的类:

public class Node {

    private String nodeName;
    private List<Node> children;
    private int layer;

    /**
     * A node with a name and a list of children on a given layer in a tree or
     * web
     *
     * @param nodeName the name of the node
     * @param children the list of children of this node
     * @param layer the layer in which this node exists
     */
    public Node(String nodeName, List<Node> children, int layer) {
        this.nodeName = nodeName;
        this.children = children;
        this.layer = layer;
    }
}

此外，我为每个字段都有 getter 和 setter。

经过整整两个晚上的努力，我想出了这个代码:

private static Node createTree() {
        Node masterNode = new Node();
        int childsPerNode = 3;
        int amountOfLayers = 5; //meaning 6 layers, 0 is included
        //Output = 364
        int totalNodeAmount = calculateNodeAmount(childsPerNode, amountOfLayers);

        //Loop for each layer, form bottom to top
        for (int currentLayer = 5; currentLayer > amountOfLayers; currentLayer--) {
            /**
             * For each layer, calculate the nodes for this layer, add children
             * to each node
             */
            int nodesThisLayer = calculateNodeAmount(childsPerNode, amountOfLayers) - calculateNodeAmount(childsPerNode, currentLayer);
            for (int nodeCount = 0; nodeCount < nodesThisLayer; nodeCount++) {
                List<Node> children = new ArrayList<>();
                for (int childCount = 0; childCount < childsPerNode; childCount++) {
                    String childFunctionName = "name";
                    Node childNode = new Node(childFunctionName, null, currentLayer);
                    children.add(childNode);
                }
                String parentFunctionName = "parent name";
                Node parentNode = new Node(parentFunctionName, children, currentLayer);
            }

        }
        return masterNode;
    }

任何关于我如何最终得到一个节点，其中包含其子节点中的整个树的帮助，我都非常感激，因为我没有想法。我没有找到具有 x 个子级和 n 层(或深度)的树的良好来源，因此我潜在的双重问题。

亲切的问候!

编辑:根据lexcore的评论，我想出了这个函数:

 private static void createTree(Node currentNode, int childrenPerNode, int numberOfLayers) {
    if (numberOfLayers == 0) {
        //Something is off here
        return;
    } else if (numberOfLayers > 0) {
        //Create sub nodes
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < childrenPerNode; i++) {
            Node childNode = new Node("name", nodes, numberOfLayers);
            nodes.add(childNode);
        }
        //Add the children to the current node
        currentNode.setChilderen(nodes);
        for (int i = 0; i < childrenPerNode; i++) {
            //For each of the children per node, call this function again until the number of layers equals zero
            createTree(currentNode.getChildren().get(i), childrenPerNode, numberOfLayers - 1);
        }
    }

然而，这确实循环得太“深”(层数太多)。我实在是想不通这是为什么。

我现在会寻找其他答案。感谢您抽出时间!

Answer 1

标题说“递归”，所以我假设您确实想编写一个递归方法。要写一个，你必须学会​​递归思考。

对于构建树的任务来说，这非常简单。树是递归定义的:树可能是空的，也可能是一个以树为子节点的节点。

就您而言，定义有点复杂。 N 层树可能是空的(如果 N 大于或等于最大所需层数)，否则它是层数为 N 的节点和层数为 N+1 的 K 个子树。

这转化为一种算法:

Node buildTree(int N) {
  // A layer N tree may be empty (if N is more than the max desired layer number)
  if (L >= maxLayerNumber) {
    return new Node with no children
  }
  // ... or else it's a node with layer number N and K subtrees with layer number N+1
  Let C be an initially empty list of children
  for i = 1 to K {
    Let c = buildTree(N + 1)  
    Add c to C
  }
  return new Node with layer number N and children C
}

要获取整个树，请调用buildTree(0)。

我故意不提供 Java 代码。自己解决问题很重要。