java - 递归地填充 TreeMap

Question

我有一个数据结构，其中节点可以有多个父节点。
我有一个要插入到树中的节点列表。列表中的节点包含数据和它的父节点的子列表。

我想根据这个列表构建一棵树。

private class Treenode {

        private List<Treenode> children;
        private List<Treenode> parents;

        public List<Treenode> getChildren() {
            return children;
        }

        public List<Treenode> getParents() {
            return parents;
        }

        private Info data;


        public Info getData() {
            return data;
        }

        public void setData(Info data) {
            this.data = data;
        }

        public Treenode() {
            children = new ArrayList<Treenode>();
            parents = new ArrayList<Treenode>();
        }

        public Treenode(Info data) {
            children = new ArrayList<Treenode>();
            parents = new ArrayList<Treenode>();
            this.data = data;
        }

        public boolean addChild(Treenode n) {
            return children.add(n);
        }

        public boolean removeChild(Treenode n) {
            return children.remove(n);
        }
        public boolean addParent(Treenode n) {
            return parents.add(n);
        }

        public boolean removeParent(Treenode n) {
            return parents.remove(n);
        }



    }


private void scanListAndAddToTree(final List list,Treenode parent){

        for (Iterator iter = list.iterator(); iter.hasNext();) {
            Info info = (Info) iter.next();
            String [] parents = info.getParents();
            if(parents==null){ //no parents
                Treenode newNode = new Treenode(info);
                parent.addChild(newNode);
                scanTree(list,newNode);
            } else

            for (int i = 0; i < parents.length; i++) {
                if (parents[i].getID.equals(parent.data.getID())){
                    Treenode newNode = new Treenode(info);
                    parent.addChild(newNode);
                    scanTree(list,newNode);
                }
            }           

但是我的代码是错误的:(

递归永远不会停止并重新添加相同的节点

Answer 1

如果您按如下方式制作您的类(class)防弹证明，则按项目完成的列表插入没有问题。

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class GraphNode<D> {

    private D data;
    private Set<GraphNode<D>> ins = new HashSet<>();
    private Set<GraphNode<D>> outs = new HashSet<>();

    public GraphNode(D data) {
        this.data = data;
    }

    public D getData() {
        return data;
    }

    public void setData(D data) {
        this.data = data;
    }

    public Set<GraphNode<D>> getIns() {
        return Collections.unmodifiableSet(ins);
    }

    public Set<GraphNode<D>> getOuts() {
        return Collections.unmodifiableSet(outs);
    }

    public void addIn(GraphNode<D> node) {
        if (node == null) {
            throw new NullPointerException(); // Never add null.
        }
        if (ins.add(node)) {
            node.outs.add(this);
        }
    }

    public void addOut(GraphNode<D> node) {
        if (node == null) {
            throw new NullPointerException(); // Never add null.
        }
        if (outs.add(node)) {
            node.ins.add(this);
        }
    }
}

注意事项

• 这是用 Java 7 编写的，用于较旧的 Java 更改 <>至 <GraphNode<D>> .
• 我使用了 Graph 这个名称，因为多父树是用词不当。
• 参数化 Info分类为 <D>这样就可以重用该类。
• 集合的 getters 不可修改。
• addIn 和 addOut 保证结构正确。
• removeIn/removeOut“留作练习”。
• 我用过Set s 依赖对象(指针)相等性。

---

public static class Info {
    private String id;
    private String[] parents;

    private String getID() {
        return id;
    }

    public String[] getParents() {
        return parents;
    }
}

public static class TreeNode extends GraphNode<Info> {
    public TreeNode(Info info) {
        super(info);
    }
}

private void insertGraph(Map<String, TreeNode> allNodes, List<Info> insertList) {
    for (Info info : insertList) {
        TreeNode newNode = new TreeNode(info);
        allNodes.put(info.getID(), newNode);
    }
    for (TreeNode node : allNodes.values()) {
        for (String parentID: node.getData().getParents()) {
            TreeNode parentNode = allNodes.get(parentID);
            parentNode.addOut(node);
        }
    }
}

private TreeNode scanTree(Info rootInfo, List<Info> insertList) {
    Map<String, TreeNode> allNodes = new HashMap<>();
    insertList.add(rootInfo);
    insertGraph(allNodes, insertList);
    return allNodes.get(rootInfo.getID());
}

由于无法保证拥有所有父树的单个树，并且 Info 已经包含该结构，因此不需要递归，但需要节点的集合。由于 Info 可能引用未定义 TreeNode 的 ID，因此需要两个阶段/fors。