向树节点插入子树

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

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

如果这还不够，请询问更多。

Answer 2

问题出在这个函数中：

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 时，您检查匹配节点名称代码的逻辑就会发挥作用。对于条目循环运行良好：Person、Manager、Hourly、New 直到它为 NULL 节点运行。在内部 for 循环 for (Node node : children) 中，您有此调试器日志：LOG.debug("HERE --> " + node.name);。此时你得到 NullPointerException 因为你的 node 是 null.

向树节点插入子树

Inserting sub-trees to a tree node

java

hierarchy