Java:如何递归填充树节点

Question

对于一个项目，我想生成一个带有x子且深处的树结构。可以在下图中描述最好的一层：

                  0
           1            1
        2     2      2     2

每行的数字等于图层号。

我得到了以下类别名为节点的类：

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

此外，我有每个字段的人。

在两个完整的晚上挣扎后，我想到了这个代码：

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层(或深度(树的好来源，因此我的潜在双重问题。

善意！

编辑：根据词典的评论，我提出了此功能：

 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和k子树的节点，带有层号n 1。

。

这转化为算法：

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 2

您可能需要避免通过使用评论中建议的递归或通过树的底部节点迭代并将其保留并将其保留在内的递归来计算所需创建的孩子数量一个单独的集合。

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 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中添加方法，并执行不同的练习。您可以将它们作为最终静态定义。

如果您想加热系统，请使用= new Autonode(-40(的root调用root;但是先计算3^45。

Answer 4

以下是完全封装的面向对象设计(即递归构造函数(的示例：

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

一些值得注意的概念：

• Tree类包含一个public constructor和一个private constructor。仅在"干净"界面中的公共构造函数。私人做所有"肮脏"的工作。
• 私有构造函数的layerIndex参数设置了根节点的偏移。将其设置为0(公共构造函数也是最好的(。
• 私有构造函数的int[] nodeIndex数组参数是用于通过Reference 发送int参数的"解决方法"。数组参数(由public constructor提供(由一个单个元素数组组成，该数组跟踪迄今为止创建的孩子的数量，以将nodeID设置为唯一值。