使用递归创建子节点

Question

我正在尝试从平面数据创建层次结构。我有以下 Node 定义：

public class Node {
        public String name;
        public List<Node> children = new ArrayList<>();
    }

鉴于此数据：[Person,Manager,Hourly,New]，树应该像这样：

Person
  |--Manager
       |--Hourly
            |--New

我试过以下方法：

public void run()
    {
        List<List<String>> objects = new ArrayList<>();

        String[] str = {"Person","Manager","Hourly","New"};
        objects.add(Arrays.asList(str)) ;

        String[] str2 = {"Person","Manager","Salary"};
        objects.add(Arrays.asList(str2)) ;

        String[] str3 = {"Person","Manager","Salary", "New"};
        objects.add(Arrays.asList(str3)) ;

        // Create a Node with the sequence
        myNode = new Node();
        createNode(objects.get(0), 0, myNode, myNode);
        LOG.debug(myNode.name);
}

而我的createNode方法是：

public Node createNode(List<String> seq, Integer start, Node parentNode, Node childNode)
    {
      // do something and return a Node?
    }

但从概念上讲，如果 Java 是 return 按值，我不明白如何维护结构。我要向 createNode 添加什么，以便我可以将 Manager->Hourly->New hierarchy 作为子级添加到 Person

Answer 1

您的方法不需要 Node return 类型和 Node 参数。

这是一种方法：

//in run()
myNode = new Node();
myNode.name = "Root";
createNode(objects.get(0), 0, myNode, myNode);



public void createNode(List<String> seq, Integer start, Node parentNode)
{
    Node childNode = new Node();
    childNode.name = seq[start];
    parentNode.children.Add(childNode);
    createNode(seq, start+1, childNode);
}

您不需要 return 来自 createNode() 的任何内容——因为您有 parentNode 作为变量，您可以向它的 children 成员添加内容。调用 createNode() 将递归地添加子节点，在您的字符串数组之后。

另一种方法是这样的：

public Node createNode(List<String> seq, Integer start)
{
    if (start >= seq.Length) {
        return null;
    }
    Node node = new Node();
    node.name = seq[start];
    node.children.Add(createNode(seq, start+1);

    return node;
}

在这种情况下，根本不需要传入node引用；调用 createNode() 将生成一个新的节点对象，递归填充其 children 树，并 return 新生成的节点结构。

Answer 2

据我所知，您对节点的定义有点类似于图中的邻接表。在目标节点中，将关联节点添加到与目标节点关联的列表中。对于属于所有节点的每个节点都是如此。

对于属于您的createNode 方法中的objects 数组（数组参数）的每个对象，您需要创建Node 对象。只需传递一个字符串数组和 taeget 节点。迭代列表并创建一个节点。在列表中添加节点。

为了在创建节点时避免重复，将它们添加到映射中。地图的键应该是字符串，值应该是节点对象。在创建节点对象之前，只需尝试从地图中获取对象，仅当在地图中找不到对象时才创建对象（在这种情况下创建并将其添加到地图中）。如果在地图上找到对象，我们同样不会重新创建它。

使用递归创建子节点

Create child nodes using recursion

java

hierarchy