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

Кроме того, у меня есть геттеры и сеттеры для каждого поля.

После двух полных вечеров я придумал такой код:

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 и выполнять различные упражнения. Вы можете поместить их в качестве окончательной статики в определение Autonode.

Если вы хотите нагреть систему, вызовите root с помощью = new AutoNode (-40); но сначала вычислите 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 параметр массива частного конструктора - это "обходной путь" для отправки int аргумент по ссылке. Аргумент массива (как предусмотрено public constructor) состоит из одного массива элементов, который отслеживает количество дочерних элементов, созданных на данный момент для установки nodeID к уникальной ценности.