对于一个项目,我想生成一个树结构,它有 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);
}
}
然而,这确实循环得太“深”(层数太多)。我实在是想不通这是为什么。
我现在会寻找其他答案。感谢您抽出时间!
最佳答案
标题说“递归”,所以我假设您确实想编写一个递归方法。要写一个,你必须学会递归思考。
对于构建树的任务来说,这非常简单。树是递归定义的:树可能是空的,也可能是一个以树为子节点的节点。
就您而言,定义有点复杂。 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 代码。自己解决问题很重要。
关于Java:如何递归填充树节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49017936/