将子树插入树节点

Question

我有以下代码（抱歉有点长），它有效：

public class Node {
        public String name;
        public List<Node> children = new ArrayList<>();
    }
    private Node root = new Node();
    public static void main(String[] args)
    {
        TestCreateHierarchy obj = new TestCreateHierarchy();
        obj.run();
    }
    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","Hello"};
        objects.add(Arrays.asList(str2)) ;
        String[] str3 = {"Person","Manager","Salary", "New"};
        objects.add(Arrays.asList(str3)) ;
//        String[] str4 = {"Person","Manager","Salary", "New", "John"};
//        objects.add(Arrays.asList(str4)) ;
        root.name = "ROOT";
        for (List<String> seq : objects) {
            LOG.debug("------------- NEW SEQUENCE -----------");
            LOG.debug(seq);
            LOG.debug("--------------------------------------");
            insert(seq);
//            break;
        }
        LOG.debug(root.children.size() + " <-- should be 1 ");
    }
    public Node createNode(List<String> seq, Integer start)
    {
        if (start >= seq.size())
            return null;
        Node node = new Node();
        node.name = seq.get(start);
        node.children.add(createNode(seq, start+1));
        return node;
    }

    public void insert(List<String> seq) {
        List<Node> children = root.children;
        // Where should we start to build the tree (how
        // deep into the sequence?)
        int start = 0 ;
        // Find the right place to add
        for (int i=0; i<seq.size(); i++) {
            boolean foundMatchingNode = false;
//            if (children.size() == 0)
//                continue;
            if (children.size() > 0) {
                for (Node node : children) {
                    LOG.debug("HERE --> " + node.name);
                    if (node.name.equals(seq.get(i))) {
                        children = node.children;
                        foundMatchingNode = true;
                        break;
                    }
                }
            }
            if (!foundMatchingNode) {
                children.add(createNode(seq,i));
                break;
            }
        }
    }

我的问题是，当我取消注释str4部分时，我得到一个NullPointerException，指的是insert方法，特别是for (Node node : children)部分。

我需要更改哪些内容才能使此代码适用于不同的层次结构深度？

Answer 1

问题出在这个函数上：

public Node createNode(List<String> seq, Integer start)
{
    if (start >= seq.size())
        return null;
    Node node = new Node();
    node.name = seq.get(start);
    node.children.add(createNode(seq, start+1));
    return node;
}

您将递归地向

每个新创建的节点添加一个子节点，对于满足此条件(start >= seq.size())的最后一个函数调用，您将创建一个null子节点。

因此，插入 str1 后，您的树如下所示： ROOT->Person->Manager->Hourly->New->NULL .现在，当您尝试输入 str4 时，检查匹配节点名称代码的逻辑开始发挥作用。循环对于条目运行良好：人员、经理、每小时、新建，直到它为NULL节点运行。在内部 for 循环for (Node node : children)中，您有以下调试器日志：LOG.debug("HERE --> " + node.name); .正是在这一点上，你得到了NullPointerException，因为你的node null。

Answer 2

您的 createNode 方法正在创建向叶中添加一个空子项。 发生 NullPointerException 是因为当您到达树的底部时，节点本身为空。

如果这还不够提示，请要求更多。