多叉树的样例

工作中有关于菜单的处理,菜单即为多叉树的结构。该样例支持如下功能:
1.获取所有节点;
2.获取当前节点的所有子节点;
3. 获取当前节点的所有父节点 ;
4.获取同级字段;

package express.tree;


import com.alibaba.fastjson.JSONObject;

import java.io.Serializable;
import java.util.*;
import java.util.stream.Collectors;

public class NodeTreeTraversalDemo {
    public static void main(String[] args) {
        List<Node> allList=new ArrayList<>();
        Node node1=new Node();
        node1.setId(1);
        node1.setLevel(1);
        node1.setParentId(0);

        Node node2=new Node();
        node2.setId(2);
        node2.setLevel(2);
        node2.setParentId(1);

        Node node3=new Node();
        node3.setId(3);
        node3.setLevel(3);
        node3.setParentId(2);

        Node node4=new Node();
        node4.setId(4);
        node4.setLevel(2);
        node4.setParentId(1);


        Node node5=new Node();
        node5.setId(5);
        node5.setLevel(4);
        node5.setParentId(3);

        Node node6=new Node();
        node6.setId(6);
        node6.setLevel(4);
        node6.setParentId(3);


        allList.add(node1);
        allList.add(node2);
        allList.add(node3);
        allList.add(node4);
        allList.add(node5);
        allList.add(node6);

        System.out.println("--------------所有节点的节点树--------------");

        List<Node> treeList=getTree(allList);
        String jsonStr = JSONObject.toJSONString(treeList);
        System.out.println(jsonStr);

        System.out.println("--------------获取id为2的所有子节点--------------");

        List<Node> childNodeList=getChildrenNode(2,allList);
        String childJsonStr = JSONObject.toJSONString(childNodeList);
        System.out.println(childJsonStr);

        System.out.println("--------------向上追溯获取id为3的所有父节点--------------");
        Map<Integer, Node> maps = allList.stream().collect(Collectors.toMap(Node::getId, Node->Node));
        List<Node>  parentNodeList=findAllParent(node3,maps);
        String  parentJsonStr = JSONObject.toJSONString(parentNodeList);
        System.out.println(parentJsonStr);

        System.out.println("---------------获取第2层的同级节点--------------");
        List<Node> sameLevelTreesList=findSameLevelNode(2,allList);
        String  sameLevelTreesJsonStr = JSONObject.toJSONString(sameLevelTreesList);
        System.out.println(sameLevelTreesJsonStr);

    }

    /**
     * 获取所有节点
     * @param allList
     * @return
     */
    public static List<Node> getTree(List<Node> allList) {

        List<Node> treeList=new ArrayList<>();
        for (Node vo :allList){
            if (vo.getParentId()==0){
                vo.setChildren(getChildrenNode(vo.getId(), allList));
                treeList.add(vo);
            }
        }
        return treeList;
    }

    /**
     * 递归获取子节点下的子节点
     * @param id 父节点的ID
     * @param treesList 所有菜单树集合
     * @return
     */
    private static List<Node> getChildrenNode(Integer id, List<Node> treesList) {
        List<Node> newTrees = new ArrayList<Node>();
        for (Node tmpNode : treesList) {
                if ("0".equals(tmpNode.getParentId())) {
                    continue;
                }
                if (id.equals(tmpNode.getParentId())) {
                    // 递归获取子节点下的子节点,即设置树控件中的children
                    tmpNode.setChildren(getChildrenNode(tmpNode.getId(), treesList));
                    newTrees.add(tmpNode);
                }

        }
        return newTrees;
    }

    /**
     * 给定节点查找该节点的所有父节点
     * @param node
     * @param data 存储的是所有的节点数据,key为该节点的Id,value为该node
     * @return
     */
    public static List<Node> findAllParent(Node node, Map<Integer,Node> data) {

        List<Node> res = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while(!stack.isEmpty()){
            //弹出栈顶节点
            Node n  = stack.pop();
            if(n.getId().equals(n.getParentId())) {
                res.add(n);
                break;
            }
            if(data.containsKey(n.getParentId())){
                Node parent = data.get(n.getParentId());
                res.add(n);
                stack.push(parent);
            }else{
                res.add(n);
            }
        }
        return res;
    }

    public  static List<Node> findSameLevelNode(Integer level,List<Node> treesList){
        List<Node> sameLevelTreesList=new ArrayList<>();
        for (Node node: treesList){
            if(level.equals(node.getLevel())){
                sameLevelTreesList.add(node);
            }
        }
        return  sameLevelTreesList;
    }



}


/**
 * 节点实体类
 */
class Node implements Serializable {


    /**
     * 主键
     */
    private Integer id;
    /**
     * 节点名称
     */
    private String name;
    /**
     * 节点编码
     */
    private String code;
    /**
     * 父id[根节点为0]
     */
    private Integer parentId;
    /**
     * 等级 [递增 根节点为0]
     */
    private Integer level;

    /**
     *   子树列表  -- 原本没有值
     */
    private List<Node> children ;

    public Integer getId() {
        return id;
    }

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

    public String getName() {
        return name;
    }

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

    public String getCode() {
        return code;
    }

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

    public Integer getParentId() {
        return parentId;
    }

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

    public Integer getLevel() {
        return level;
    }

    public void setLevel(Integer level) {
        this.level = level;
    }

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

    public void setChildren(List<Node> children) {
        this.children = children;
    }

    @Override
    public boolean equals(Object obj) {
        if(this==obj)return  true;
        if(obj==null) return false;
        if(getClass()!=obj.getClass()) return false;
        Node node0bj=(Node) obj;
        if(id!=null)
        {
            if(id.equals(node0bj.getId())
            ){
                return  true;
            }else{
                return  false;
            }
        }else {
            return  false;
        }

    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }

    @Override
    public String toString(){

        return "id "+id+",name "+ name +",level " +level+",children "+children;

    }
}
--------------所有节点的节点树--------------
[{"children":[{"children":[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2}],"id":2,"level":2,"parentId":1},{"children":[],"id":4,"level":2,"parentId":1}],"id":1,"level":1,"parentId":0}]
--------------获取id为2的所有子节点--------------
[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2}]
--------------向上追溯获取id为3的所有父节点--------------
[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2},{"children":[{"$ref":"$[0]"}],"id":2,"level":2,"parentId":1},{"children":[{"$ref":"$[1]"},{"children":[],"id":4,"level":2,"parentId":1}],"id":1,"level":1,"parentId":0}]
---------------获取第2层的所有节点--------------
[{"children":[{"children":[{"children":[],"id":5,"level":4,"parentId":3},{"children":[],"id":6,"level":4,"parentId":3}],"id":3,"level":3,"parentId":2}],"id":2,"level":2,"parentId":1},{"children":[],"id":4,"level":2,"parentId":1}]
上一篇:Django models 的增删改查


下一篇:【Java】树状节点结构的数据