1.需求描述
对于数据库设计中,对于层级结构的设计一般使用parentId对于Id的引用实现。令我们愉悦的是,Oracle还提供了关键字PRIOR查询树状结构的语句。下面是对于多级菜单的层级结构查询的Sql语句。具体语法大家可以自行学习,这里不对此做过多的解释。
-
SELECT
-
ID,
-
NVL(TO_CHAR(PARENT_ID),
'NULL') PARENT_ID,
-
MODULE_NAME,
-
BS_URL,
-
ICON,
-
ORDER_NO,
-
IS_VISIBLE,
-
SYS_CONNECT_BY_PATH(MODULE_NAME,
'/')
PATH
-
FROM
-
SM_MODULE
-
START
WITH
-
PARENT_ID
IS
NULL
-
CONNECT
BY
-
PRIOR
ID = PARENT_ID
查询的结果如下图:
通过上面的结果我们知道,通过此Sql语句查询到的数据是按先查询PARENT_ID == NULL(也就是START WITH PARENT_ID IS NULL)的记录,然后以每一条记录的ID作为父级ID执行查询,对于查询的结果集合再以次ID作为父级节点查询,依次递归查询。所以得到了上面的数据。而对于我们只要知道排在下面数据的父节点肯定在其上面存在(顶级节点除外)足以。
结果集查到了,那么接下来是如何将其按照层级结构存入到Java对象中。下面我们分别以HashMap和栈的方式实现需求,通过比较,你会深深体会到基于栈实现此需求是多么的香。
2.数据准备
为了便于测试研究,也为了照顾平时不怎么使用Oracle的伙伴,我们并没有直接连接Oracle查询数据,而是模拟通过Oracle获得的结果数据。
2.1 Model对象实现
-
package cn.surpass.jdk8newfuture.self.tree;
-
-
import java.util.ArrayList;
-
import java.util.List;
-
-
/**
-
* @Description
-
* @Author SurpassLiang
-
* @Version V1.0.0
-
* @Since 1.0
-
* @Date 2020/4/11
-
*/
-
public
class Model {
-
private String id;
-
private String parentId;
-
private List<Model> modelList=
new ArrayList<>();
-
public String getId() {
-
return id;
-
}
-
public void setId(String id) {
-
this.id = id;
-
}
-
public String getParentId() {
-
return parentId;
-
}
-
public void setParentId(String parentId) {
-
this.parentId = parentId;
-
}
-
public Model(String id, String parentId) {
-
this.id = id;
-
this.parentId = parentId;
-
}
-
-
@Override
-
public String toString() {
-
return
"Model{" +
-
"id='" + id +
'\'' +
-
", parentId='" + parentId +
'\'' +
-
", modelList=" + modelList +
-
'}';
-
}
-
-
public List<Model> getModelList() {
-
return modelList;
-
}
-
public void setModelList(List<Model> modelList) {
-
this.modelList = modelList;
-
}
-
}
2.2 测试数据
我们使用Junit测试工具测试,所以我们初始化数据有如下代码:
-
package cn.surpass.jdk8newfuture.self.tree;
-
import org.junit.Before;
-
import org.junit.Test;
-
import java.util.*;
-
-
/**
-
* @Description
-
* @Author SurpassLiang
-
* @Version V1.0.0
-
* @Since 1.0
-
* @Date 2020/4/11
-
*/
-
public
class TreeTest {
-
List<Model> modelList =
new ArrayList<>();
-
@Before
-
public void testTree(){
-
modelList.add(
new Model(
"1",
null));
-
modelList.add(
new Model(
"2",
"1"));
-
modelList.add(
new Model(
"3",
"1"));
-
modelList.add(
new Model(
"4",
"3"));
-
modelList.add(
new Model(
"5",
"1"));
-
modelList.add(
new Model(
"6",
null));
-
modelList.add(
new Model(
"7",
"6"));
-
modelList.add(
new Model(
"8",
"6"));
-
modelList.add(
new Model(
"9",
"6"));
-
modelList.add(
new Model(
"10",
"9"));
-
modelList.add(
new Model(
"11",
"9"));
-
modelList.add(
new Model(
"12",
"9"));
-
modelList.add(
new Model(
"13",
"12"));
-
}
-
}
3.基于HashMap实现需求
通过上面的数据我们分析到,针对当前的节点的父节点在上面的记录已经存在,所以我们这里引入HashMap记录已经处理的数据。对于HashMap,key为节点的ID,value为当前节点对象。另外我们引入一个存放顶级节点的集合。针对一个对象,如果父级节点为空,说明此节点为顶级节点,应该放到顶级节点的结合中;如果不为空,通过HashMap的get(Object key)方法查询到当前节点的父节点,然后将当前节点放到父节点的modelList当中。整个代码逻辑并不复杂。下面是代码实现:
-
@Test
-
public void test1(){
-
//根节点集合
-
List<Model> rootModules =
new ArrayList<>();
-
Map<String, Model> tempMap =
new HashMap<>();
-
Model curModel;
-
String parentId;
-
for (
int i =
0; i < modelList.size(); i++) {
-
curModel = modelList.get(i);
-
parentId = curModel.getParentId();
-
tempMap.put(curModel.getId(),curModel);
-
//HashMap的key是否包含当前节点的父级节点
-
if (tempMap.containsKey(parentId)) {
-
//包含,获取父级节点并将当前节点加入到ModelList集合中
-
tempMap.get(parentId).getModelList().add(curModel);
-
}
else {
-
//如果不存在,则加入根节点集合中
-
rootModules.add(curModel);
-
}
-
}
-
rootModules.forEach(System.out::println);
-
}
4.基于栈(Stack)实现需求
4.1 栈的简述
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。简而言之,就是先进后出。如果想不明白,可以想一下子弹夹,先摁进去的子弹最后一个弹出去。
4.2 业务逻辑
1.对于第一个数据,按照上面数据结果的分析,第一个数据肯定是根节点,所以压入栈顶。
2.对于第二个数据,通过其父节点与栈顶的元素ID进行比较,如果一样,则将当前元素放入栈顶元素的modleList集合中,同时将第二个元素压入栈顶。
3.对于第三个数据,通过其父节点与栈顶的元素ID进行比较,此时栈顶元素ID为2,当前节点父级节点ID为1,不满足条件,将栈顶元素弹出,在此通过其父节点与栈顶的元素ID进行比较,此时栈顶元素ID为1,满足条件,则将当前元素放入栈顶元素的modleList集合中,同时将第三个元素压入栈顶。
依次类推,最终遍历所有的元素,以下是处理流程图。
4.3.代码实现
-
@Test
-
public void test2(){
-
List<Model> rootModules =
new ArrayList<>();
-
Stack<Model> moduleStack =
new Stack<>();
-
Model curModule;
-
for (
int i =
0; i < modelList.size(); i++) {
-
curModule = modelList.get(i);
-
if(curModule.getParentId() ==
null){
-
rootModules.add(curModule);
-
moduleStack.push(curModule);
-
}
else{
-
while(moduleStack.peek().getId() != curModule.getParentId()){
-
moduleStack.pop();
-
}
-
moduleStack.peek().getModelList().add(curModule);
-
moduleStack.push(curModule);
-
}
-
}
-
rootModules.forEach(System.out::println);
-
}
5.测试
test1是基于HashMap实现的业务逻辑,test2是基于栈实现的业务逻辑,在耗时上基本是栈完虐HashMap。所以了解一下数据结构还是很有必要的。
转载:https://blog.csdn.net/oYinHeZhiGuang/article/details/105455379