多叉树的查找及转换

方法一：

 

1. 带有父节点信息的节点：

 

public class FlatNode {
    private Integer path;
    private String name;
    private Integer parent;

    public Integer getPath() {
        return path;
    }

    public void setPath(Integer path) {
        this.path = path;
    }

    public Integer getParent() {
        return parent;
    }

    public void setParent(Integer parent) {
        this.parent = parent;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "FlatNode{" +
                "path=" + path +
                ", name='" + name + '\'' +
                ", parent=" + parent +
                '}';
    }
}

 

2. 多叉树的节点：

public class MulNode {

    private Integer path;
    private String name;
    private List<MulNode> childList;

    public Integer getPath() {
        return path;
    }

    public void setPath(Integer path) {
        this.path = path;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public List<MulNode> getChildList() {
        return childList;
    }

    public void setChildList(List<MulNode> childList) {
        this.childList = childList;
    }

    public boolean hasChildren(MulNode node) {
        return node.getChildList() != null && node.getChildList().size() > 0;
    }

    @Override
    public String toString() {
        return "MulNode{" +
                "path=" + path +
                ", name='" + name + '\'' +
                ", childList=" + childList +
                '}';
    }
}

 

3.工具类，包括多叉树遍历查找节点方法（利用队列进行递归层序遍历 PS :从二叉树层序遍历得到的灵感）

                 二叉树转换成带有父节点信息的一位数组方法（同样是利用递归）

                 测试方法--main函数。

 

public class NodeUtils {

    public static MulNode find(MulNode root, Integer value) {
        Queue<MulNode> queue = new LinkedList<MulNode>();
        queue.add(root);
        return find(queue, value);
    }

    // 层序遍历
    private static MulNode find(Queue<MulNode> queue, Integer value) {
        MulNode res = null;
        while (!queue.isEmpty()) {
            MulNode node = queue.peek();
            if (node.getPath().equals(value)) {
                res = node;
                break;
            } else {
                queue.remove();
                if (node.hasChildren(node)) {
                    for (MulNode child : node.getChildList()) {
                        queue.add(child);
                    }
                } else {
                    find(queue, value);
                }
            }
        }
        return res;
    }

    public static List<FlatNode> transfer(MulNode root) {
        Queue<MulNode> queue = new LinkedList<MulNode>();
        queue.add(root);
        Queue<MulNode> parent = new LinkedList<MulNode>();
        List<FlatNode> nodeList = new ArrayList<FlatNode>();
        return transfer(queue, parent, nodeList);
    }

    private static List<FlatNode> transfer(Queue<MulNode> queue, Queue<MulNode> parent, List<FlatNode> nodeList) {
        while (!queue.isEmpty()) {
            MulNode node = queue.peek();
            MulNode father = parent.peek();
            FlatNode flatNode = new FlatNode();
            flatNode.setName(node.getName());
            flatNode.setPath(node.getPath());
            if (father == null) {
                flatNode.setParent(null);
            } else {
                flatNode.setParent(father.getPath());
                parent.remove();
            }
            queue.remove();
            nodeList.add(flatNode);
            if (node.hasChildren(node)) {
                for (MulNode child : node.getChildList()) {
                    queue.add(child);
                    parent.add(node);
                }
            } else {
                transfer(queue, parent, nodeList);
            }
        }
        return nodeList;
    }

    public static void main(String[] args) {
        MulNode root = new MulNode();
        root.setPath(0);
        root.setName("root");
        MulNode node1 = new MulNode();
        node1.setPath(1);
        node1.setName("Clothes");
        MulNode node2 = new MulNode();
        node2.setPath(2);
        node2.setName("food");
        MulNode node3 = new MulNode();
        node3.setPath(3);
        node3.setName("Animal");
        MulNode node10 = new MulNode();
        node10.setPath(10);
        node10.setName("shoe");
        MulNode node11 = new MulNode();
        node11.setPath(11);
        node11.setName("skirt");
        MulNode node12 = new MulNode();
        node12.setPath(12);
        node12.setName("jacket");
        MulNode node20 = new MulNode();
        node20.setPath(20);
        node20.setName("pizza");
        MulNode node21 = new MulNode();
        node21.setPath(21);
        node21.setName("noodle");
        MulNode node30 = new MulNode();
        node30.setPath(30);
        node30.setName("hen");
        MulNode node31 = new MulNode();
        node31.setPath(31);
        node31.setName("pig");
        MulNode node32 = new MulNode();
        node32.setPath(32);
        node32.setName("wolf");
        MulNode node200 = new MulNode();
        node200.setPath(200);
        node200.setName("Italy Pizza");
        List<MulNode> list1 = new ArrayList<MulNode>();
        List<MulNode> list10 = new ArrayList<MulNode>();
        List<MulNode> list20 = new ArrayList<MulNode>();
        List<MulNode> list30 = new ArrayList<MulNode>();
        List<MulNode> list200 = new ArrayList<MulNode>();
        list200.add(node200);
        node20.setChildList(list200);

        list20.add(node20);
        list20.add(node21);
        node2.setChildList(list20);

        list30.add(node30);
        list30.add(node31);
        list30.add(node32);
        node3.setChildList(list30);

        list10.add(node10);
        list10.add(node11);
        list10.add(node12);
        node1.setChildList(list10);

        list1.add(node1);
        list1.add(node2);
        list1.add(node3);

        root.setChildList(list1);

        System.out.println(root);
        System.out.println(find(root, 32));
        System.out.print(transfer(root));
    }
}

 

 

 

方法二：利用map来构造树形结构：

 

public class MulNode {
    private int id;
    private int parentId;
    MulNode parent;
    List<MulNode> childList;
    String code;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getParentId() {
        return parentId;
    }

    public void setParentId(int parentId) {
        this.parentId = parentId;
    }

    public MulNode getParent() {
        return parent;
    }

    public void setParent(MulNode parent) {
        this.parent = parent;
    }

    public List<MulNode> getChildList() {
        return childList;
    }

    public void setChildList(List<MulNode> childList) {
        this.childList = childList;
    }

    public String getCode() {
        return code;
    }

    public void setCode(String code) {
        this.code = code;
    }


    public MulNode(int id, int parentId, MulNode parent, List<MulNode> childList, String code) {
        this.id = id;
        this.parentId = parentId;
        this.parent = parent;
        this.childList = childList;
        this.code = code;
    }

    //根据List构造树形结构

    public Map<Integer, MulNode> generateTree(List<MulNode> nodeList) {
        Map<Integer, MulNode> treeMap = new HashMap<Integer, MulNode>();
        for (MulNode node : nodeList) {
            treeMap.put(node.getId(), node);
        }
        for (MulNode value : treeMap.values()) {
            MulNode parent = treeMap.get(value.getParentId());
            if (parent != null) {
                parent.getChildList().add(value);
                value.setParent(parent);
            }
        }
        return treeMap;
    }

    //构造path结构
    public Map<String, MulNode> generateTreePath(Map<Integer, MulNode> treeMap) {
        Map<String, MulNode> pathMap = new HashMap<String, MulNode>();
        for (MulNode value : treeMap.values()) {
            pathMap.put(generateTreePath(value), value);
        }
        return pathMap;
    }

    /**
     * 生成 具体配置 Path
     *
     * @param node
     * @return
     */
    public String generateTreePath(MulNode node) {
        if (null == node.getParent()) {
            return node.getCode();
        } else {
            return generateTreePath(node.getParent()) + "/" + node.getCode();
        }
    }
}