Java树形数据的面试题

在平时开发、学习、面试中，经常会遇到树形结构数据的地方。比如常见的树形结构的菜单。

博主最近遇到了一个数据结构的面试的，分享出来大家探讨学习下。

题目如下:

​

是一个典型的无限级的树结构

1.解题思路

我的思路是

第一步获取所有数据

​

第二步遍历得到父节点为0的数据(父层数据)

​

第三步遍历父层数据得到子层数据

​

第四步打印父层数据

​

第五步打印子层数据

​

结果如下

​

话不多说，以下是代码:

1.Emp

package pojo;

/**
 * @作者: tjx
 * @描述: 员工对象
 * @创建时间: 创建于11:30 2018/9/5
 **/
public class Emp {

    private Integer ID;

    private Integer Parent_ID;

    private String Name;

    public Integer getID() {
        return ID;
    }

    public void setID(Integer ID) {
        this.ID = ID;
    }

    public Integer getParent_ID() {
        return Parent_ID;
    }

    public void setParent_ID(Integer parent_ID) {
        Parent_ID = parent_ID;
    }

    public String getName() {
        return Name;
    }

    public void setName(String name) {
        Name = name;
    }
}
复制代码

2.EmpTree.java

package pojo;

import java.util.List;

/**
 * @作者: tjx
 * @描述: 树
 * @创建时间: 创建于11:34 2018/9/5
 **/
public class EmpTree extends Emp{

    private List<EmpTree> childrens;

    public List<EmpTree> getChildrens() {
        return childrens;
    }

    public void setChildrens(List<EmpTree> childrens) {
        this.childrens = childrens;
    }
}
复制代码

3.EmpDAO.java

package dao;

import pojo.EmpTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @作者: tjx
 * @描述: 模拟dao层
 * @创建时间: 创建于11:38 2018/9/5
 **/
public class EmpDAO {

    public List<EmpTree> selectAll(){
        List<EmpTree> list = new ArrayList<EmpTree>();
        EmpTree emp = new EmpTree();
        emp.setID(1);
        emp.setParent_ID(0);
        emp.setName("CEO");
        EmpTree emp2 = new EmpTree();
        emp2.setID(2);
        emp2.setParent_ID(1);
        emp2.setName("CTO");

        EmpTree emp3 = new EmpTree();
        emp3.setID(3);
        emp3.setParent_ID(2);
        emp3.setName("Eng1");

        EmpTree emp4 = new EmpTree();
        emp4.setID(4);
        emp4.setParent_ID(5);
        emp4.setName("Finance1");

        EmpTree emp5 = new EmpTree();
        emp5.setID(5);
        emp5.setParent_ID(1);
        emp5.setName("CFO");

        EmpTree emp6 = new EmpTree();
        emp6.setID(6);
        emp6.setParent_ID(5);
        emp6.setName("Finance2");

        EmpTree emp7 = new EmpTree();
        emp7.setID(7);
        emp7.setParent_ID(2);
        emp7.setName("Eng2");

        EmpTree emp8 = new EmpTree();
        emp8.setID(8);
        emp8.setParent_ID(1);
        emp8.setName("Assistant1");

        EmpTree emp9 = new EmpTree();
        emp9.setID(9);
        emp9.setParent_ID(3);
        emp9.setName("DevSupport1");

        EmpTree emp10 = new EmpTree();
        emp10.setID(10);
        emp10.setParent_ID(8);
        emp10.setName("Intern1");

        list.add(emp);
        list.add(emp2);
        list.add(emp3);
        list.add(emp4);
        list.add(emp5);
        list.add(emp6);
        list.add(emp7);
        list.add(emp8);
        list.add(emp9);
        list.add(emp10);
        return list;
    }

}
复制代码

4.TreeUtils.java

package utils;

import dao.EmpDAO;
import pojo.EmpTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @作者: tjx
 * @描述: 用于树形结构转换
 * @创建时间: 创建于11:45 2018/9/5
 **/
public class TreeUtils {


    /** 获取 顶级菜单集合
     * @param data   原始数据
     * @param pid    父类编号
     * @return
     */
    public static List<EmpTree> getParentTree(List<EmpTree> data,int pid){
        if (data == null) {
            return null;
        }
        List<EmpTree> empTreeList = new ArrayList<EmpTree>();
       data.forEach(empTree -> {
            if(pid == empTree.getParent_ID()){
                empTreeList.add(empTree);
            }
       });
       return empTreeList;
    }

    /**
     * 根据 PID  得到出现个数
     * @param data
     * @param pid
     * @return
     */
    public static int getSizeByPid(List<EmpTree> data,int pid){
        return (int) data.stream().filter(empTree -> empTree.getParent_ID() == pid).count();
    }

    /**
     * 获取 子节点
     * @param data
     * @param parent
     * @return
     */
    public static List getChildrens(List<EmpTree> data,EmpTree parent){
        List<EmpTree> result = new ArrayList<EmpTree>();
        //找到该菜单下的所有员工
        data.forEach(empTree -> {
            if(empTree.getParent_ID() == parent.getID()){
                result.add(empTree);
            }
        });
        //遍历子菜单
        result.forEach(empTree -> {
            int count = getSizeByPid(data, parent.getID());
            if(count>0){
                //递归调用
                empTree.setChildrens(getChildrens(data,empTree));
            }
        });
        return result;

    }

    /**
     * 打印子菜单
     * @param data
     */
    public static void printChildrens(List<EmpTree> data,String oldStr){
        if(oldStr == null){
            oldStr = "-->";
        }
        String finalOldStr = oldStr;
        data.forEach(empTree -> {
            System.out.println(finalOldStr +empTree.getName() );
            if(empTree.getChildrens()!=null){
                printChildrens(empTree.getChildrens(),finalOldStr+"-->");
            }
        });
    }

    /**
     * 打印父层数据
     * @param data  原始数据
     */
    public static void print(List<EmpTree> data){
        data.forEach(empTree -> {
            System.out.println(empTree.getName());
            if(empTree.getChildrens()!=null){
                printChildrens(empTree.getChildrens(),null);
            }
        });
    }


    public static void main(String[] args) {
        EmpDAO empDAO = new EmpDAO();
        //此处模拟DB操作
        List<EmpTree> rootData = empDAO.selectAll();

        //获取父类菜单
        List<EmpTree> parentTree = getParentTree(rootData, 0);

        //遍历
        parentTree.forEach(empTree -> {
            empTree.setChildrens(getChildrens(rootData,empTree));
        });

        print(parentTree);


    }

}
复制代码

欢迎多多评论，多多留言，不足地方还请业内高手指点，鸣谢！！！