一）题目简介
一道层级数据转树形菜单面试题，如图：
二）题目分析
分析：
1、parent_id为null的节点为顶级节点，需考虑多个顶级节点处于同一层级的情况。
2、每一节点的id属性作为下一级节点的parent_id属性，构造成一个层级数据结构。
步骤：
1、先初始化一个数据结构类，再初始化数据，用List存储。
2、先找出数据中所有顶级节点，作为第一层级的数据。
3、循环顶级结点，根据id属性查找和parent_id相同数据，作为二级子节点。
4、在根据二级子结点，查找id和parent_id相同数据，作为三级子节点。
5、不断递归根据id和parent_id查找子节点，直到所有子节点查找完。
缺点：
如数据层次比较深，耗费的时间和空间会比较多。
三）题目源码
备注：用到了com.alibaba.fastjson.JSON转换成json数据，方便查看数据，这是alibaba第三方fastjson.jar，可网上下载。
第一步：初始化数据结构
/**
* 一道层级数据转树形菜单面试题
* @author ouyangjun
*/
public class DataChangeTree {
/** 初始化数据结构 */
static class Data {
private String parent_id;
private String id;
private String value;
public Data (String parent_id, String id, String value) {
this.parent_id = parent_id;
this.id = id;
this.value = value;
}
public String getParent_id() {
return parent_id;
}
public void setParent_id(String parent_id) {
this.parent_id = parent_id;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
}
}
第二步：初始化数据
/** 初始化数据 */
public List<Data> init() {
List<Data> dataList = new ArrayList<Data>();
Data data1 = new Data(null, "a", "1111");
Data data2 = new Data("a", "c", "2222");
Data data3 = new Data("d", "f", "3333");
Data data4 = new Data("c", "e", "4444");
Data data5 = new Data("b", "d", "5555");
Data data6 = new Data("a", "b", "6666");
dataList.add(data1);
dataList.add(data2);
dataList.add(data3);
dataList.add(data4);
dataList.add(data5);
dataList.add(data6);
return dataList;
}
第三步：根据层级数据构造树形菜单
// 创建树形菜单
public Map<String, Object> createTree(List<Data> datas) {
if (datas != null) {
// 顶级节点
Map<String, Object> rootMap = new HashMap<String, Object>();
// 循环比较
Iterator<Data> it = datas.iterator();
Data tempData = null;
while (it.hasNext()) {
tempData = it.next();
if (tempData.getParent_id() == null) {
rootMap.put(tempData.getId(), tempData.getValue()); // 先把顶级节点存储起来
// 顶级节点, 保存之后可以移除
it.remove();
}
}
// 根据顶级节点, 查找parent_id等于id的子节点
return addChildren(rootMap, datas);
}
return null;
}
private Map<String, Object> addChildren(Map<String, Object> rootMap, List<Data> datas) {
if (datas == null || datas.size()==0 || rootMap == null) {
return null;
}
// 初始化
Map<String, Object> newMap = null;
Map<String, Object> childrenMap = null;
// 循环key
for (Map.Entry<String, Object> key : rootMap.entrySet()) {
newMap = new HashMap<String, Object>();
childrenMap = new HashMap<String, Object>();
// 循环比较
Iterator<Data> it = datas.iterator();
Data tempData = null;
while (it.hasNext()) {
tempData = it.next();
if (key.getKey().equals(tempData.getParent_id())) {
// 保存
childrenMap.put(tempData.getId(), tempData.getValue());
// 不能移除数据的原因,因为菜单可能会相互嵌套
//it.remove();
}
}
// 没有子节点,就不添加了
if (childrenMap != null && childrenMap.size() > 0) {
newMap.put("children", childrenMap);
}
// 和父节点关联起来
rootMap.put(key.getKey(), newMap);
// 递归, 继续寻找下一级子节点
addChildren(childrenMap, datas);
}
// 返回
return rootMap;
}
第四步：main方法测试
public static void main(String[] args) {
DataChangeTree obj = new DataChangeTree();
// 初始化层级数据
List<Data> datas = obj.init();
// 根据层级数据转成树形菜单
Map<String, Object> treeMap = obj.createTree(datas);
System.out.println("根据层级数据转成树形菜单, 树结构为:\n "+ JSON.toJSON(treeMap));
}
第五步：打印效果图
识别二维码关注个人微信公众号
本章完结，待续，欢迎转载！
本文说明：该文章属于原创，如需转载，请标明文章转载来源！ | 
转播
