Java：如何递归填充一个树节点

Question

对于一个项目，我想生成一个树结构，它有 x 个子节点，深度为 n 'layers'。一层最好用下图来描述：

                  0
           1            1
        2     2      2     2

每一行的数字等于层数。

我得到以下 class 命名节点：

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 层（或深度）的树的良好来源，因此我可能会提出双重问题。

亲切的问候！

编辑：根据lexicore的评论，我想出了这个功能：

 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);
        }
    }

然而，这确实会继续循环 'deep'（太多层）。我很想知道为什么会这样。

我现在会查看其他答案。已经谢谢你的时间了！

Answer 1

您可能希望通过使用评论中建议的递归或遍历树的底部节点并将它们保存在单独的集合中来避免计算需要创建的子节点的数量。

List<Node> children = new ArrayList<Node>(); 
children.add(masterNode);
int layer = amountOfLayers;

while (layer > 0) {
  List<Node> allBottomChildren = new ArrayList<Node>();
  for (Node child : children) {
    List<Node> nextLevelChildren = new ArrayList<Node>();
    for (int i = 0;i<childsPerNode;i++) {
      Node node = new Node("name", new ArrayList<Node>(), layer - 1);
      nextLevelChildren.add(node);
    }
    child.setChildren(nextLevelChildren);
    allBottomChildren.addAll(nextLevelChildren);
  }
  children = allBottomChildren;
  layer = layer - 1;
}

Answer 2

标题说 "recursive," 所以我假设你真的想写一个递归方法。要写一个，你必须学会递归思考。

对于构建树的任务，这非常简单。树是递归定义的：一棵树可以是空的，也可以是一个有树的节点 children。

在你的例子中，定义有点复杂。第 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 代码。自己解决问题很重要。

Answer 3

这显然不是最好的设计，而是一个非常简短的解决方案：

int childsPerNode = 3;
int amountOfLayers = 5;

class AutoNode {

    int layer;
    List <AutoNode> childs;

    public AutoNode (int n) {
        layer = n;
        if (layer < amountOfLayers) {
            childs = new ArrayList<AutoNode> ();

            for (int i = 0; i < childsPerNode; ++i) {
                childs.add (new AutoNode (n + 1));
            }
        }
    }
    public String toString () {return ("layer: " + layer + " <" + ((layer < 5) ? childs.toString () : "()") + ">" );}
}

AutoNode root = new AutoNode (0);

界限：

int childsPerNode = 3;
int amountOfLayers = 5;

对节点来说有些陌生。但它是第一个快速原型。

您可以在Autonode中添加方法，进行不同的练习。您可以将它们作为最终静态放入自动节点定义中。

如果你想升温系统，调用root with = new AutoNode (-40);但先计算 3^45。

Answer 4

这是一个完全封装的 object-oriented 设计示例（即递归构造函数）：

public class Tree
{
    private int layer;
    private int nodeID;
    private List<Tree> children;

    public Tree(int numOfchildren, int numOfLayers)
    {
        this(numOfchildren, numOfLayers, 0, new int[1]);
    }

    private Tree(int numOfchildren, int numOfLayers, int layerIndex, int[] nodeIndex)
    {
        layer = layerIndex;
        nodeID = nodeIndex[0]++;

        if (numOfLayers > 0 && numOfchildren > 0) {
            children = new ArrayList<Tree> ();
            for (int i = 0; i < numOfchildren; i++) {
                children.add(new Tree(numOfchildren, numOfLayers - 1, layer + 1, nodeIndex));
            }
        }
    }
}

一些值得注意的概念：

Treeclass包含一个public constructor和一个private constructor。 public 构造函数仅在 "clean" 接口中。私有的完成所有 "dirty" 工作。
私有构造函数的layerIndex参数设置了根节点的偏移量。最好将其设置为 0（与 public 构造函数一样）。
私有构造函数的int[] nodeIndex数组参数是一个"workaround"，用于通过引用发送int参数。数组参数（由 public constructor 提供）由单个元素数组组成，该数组跟踪到目前为止创建的子项数量，以便将 nodeID 设置为唯一值。

Java：如何递归填充一个树节点

Java: how to recursively fill a tree node

java

tree

recursion

fill