带权树形结构的过滤
1. 带权树
1.1. 树的概念
树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 每个节点有零个或多个子节点。
- 没有父节点的节点称为根节点。
- 每一个非根节点有且只有一个父节点。
1.2 带权树的概念
在数的基础上，每个节点都都带有权重，也就是数值。
2. 树的生成(将集合转化为树)
2.1 数据库对象
用来接收数据库中的数据，一般称为DO对象。
public class Node {
private Integer id;
private Integer weight; // 权重
private Integer pid; //父级id
public Node(Integer id, Integer weight, Integer pid) {
this.id = id;
this.weight = weight;
this.pid = pid;
}
public static Node createRootNode(){
return new Node(0,0,null);
}
}
2.2 树形节点结构
表示树中的每一个节点，用于将DO对象转化为节点。
public class NodeTree {
private Integer id;
private Integer weight;
private Integer pid;
private List<NodeTree> childrens;
public NodeTree(Node node) {
this.id = node.getId();
this.weight = node.getWeight();
this.pid = node.getPid();
}
}
2.3 生成树
因为我们一般的数据都保存在数据库库中，查询出来的数据是按行分布的，通常都使用 List 集合来接收，也就是说我们需要将在代码中将其转化为树形结构。一共有如下几步：
- 将 List 集合 转化为 Map 集合，方便我们随机读取，同时每行数据转化为树形节点。
- 通过 Map 集合生成树。
- 通过 DFS 遍历树添加权重。
代码如下：
public static void main(String[] args) {
//初始数据
ArrayList<Node> nodeList = new ArrayList<Node>(){{
add(new Node(1,1,0));
add(new Node(10,10,0));
add(new Node(2,2,1));
add(new Node(3,3,2));
add(new Node(4,4,10));
add(Node.createRootNode()); //添加根节点
}};
//转化为map方便随机读取
Map<Integer,NodeTree> nodeMap = new HashMap<>();
for(Node n : nodeList){
nodeMap.put(n.getId(),new NodeTree(n));
}
//转化链式结构为树形结构
for (Node n : nodeList) {
Integer pid = n.getPid();
if (Objects.nonNull(pid)) { //pid为null为根节点
NodeTree pTree = nodeMap.get(pid);
if (pTree.getChildrens() == null) { //childrens为null表示没有子节点
pTree.setChildrens(new ArrayList<>());
}
NodeTree currentNodeTree = nodeMap.get(n.getId());
pTree.getChildrens().add(currentNodeTree); //添加子节点到父节点中
}
}
//id为0的是根节点
//添加权重
dfsTree(nodeMap.get(0));
String jsonStr = JSONUtil.toJsonStr(nodeMap.get(0));
JSONObject jsonObject = new JSONObject(jsonStr);
System.out.println(JSONUtil.toJsonPrettyStr(jsonObject.toString()));
}
public static Integer dfsTree(NodeTree root){
if(root == null){
return 0;
}
if(root.getChildrens() != null){
for(NodeTree childe : root.getChildrens()){
root.setWeight(root.getWeight() + dfsTree(childe));
}
}
return root.getWeight();
}
输出如下：
{
"weight": 20,
"childrens": [
{
"weight": 6,
"pid": 0,
"childrens": [
{
"weight": 5,
"pid": 1,
"childrens": [
{
"weight": 3,
"pid": 2,
"id": 3
}
],
"id": 2
}
],
"id": 1
},
{
"weight": 14,
"pid": 0,
"childrens": [
{
"weight": 4,
"pid": 10,
"id": 4
}
],
"id": 10
}
],
"id": 0
}
3. 树的过滤
现在只想要目标集合的节点路径，不在目标集合中路径就不显示。之前我们是通过循环生成树，现在我们需要换一种思路，通过目标集合中的节点向上遍历，直到遇到根节点，来生成树。需要注意的时，当树的层数达到三层时，可能会重复添加子节点，所以子集合需要去重。
public static void main(String[] args) {
//初始数据
ArrayList<Node> nodeList = new ArrayList<Node>(){{
add(new Node(1,1,0));
add(new Node(10,10,0));
add(new Node(2,2,1));
add(new Node(3,3,2));
add(new Node(4,4,10));
add(Node.createRootNode()); //添加根节点
}};
//过滤数据
ArrayList<Node> nodeListFilter = new ArrayList<Node>(){{
add(new Node(3,3,2));
}};
//转化为map方便随机读取
Map<Integer,NodeTree> nodeMap = new HashMap<>();
for(Node n : nodeList){
nodeMap.put(n.getId(),new NodeTree(n));
}
//转化链式结构为树形结构
for(Node n : nodeListFilter){
dfsTreeFilterForm(nodeMap.get(n.getId()),nodeMap);
}
//id为0的是根节点
//添加权重
dfsTree(nodeMap.get(0));
String jsonStr = JSONUtil.toJsonStr(nodeMap.get(0));
JSONObject jsonObject = new JSONObject(jsonStr);
System.out.println(JSONUtil.toJsonPrettyStr(jsonObject.toString()));
}
public static Integer dfsTree(NodeTree root){
if(root == null){
return 0;
}
if(root.getChildrens() != null){
for(NodeTree childe : root.getChildrens()){
root.setWeight(root.getWeight() + dfsTree(childe));
}
}
return root.getWeight();
}
//向上遍历
private static void dfsTreeFilterForm(NodeTree n, Map<Integer, NodeTree> nodesMap){
NodeTree np = nodesMap.get(n.getPid());
if(np.getChildrens() == null){
np.setChildrens(new ArrayList<>());
}
List<NodeTree> children = np.getChildrens();
if (!children.contains(n)){ //避免重复添加子节点，因为在向上遍历时,其同级节点已经向上遍历过了，如果不做判断，其父级的往上的都会重复添加父级节点。
children.add(n);
}
if(np.getPid() != null){
dfsTreeFilterForm(np,nodesMap);//向上传递
}
}
输出如下
{
"weight": 6,
"childrens": [
{
"weight": 6,
"pid": 0,
"childrens": [
{
"weight": 5,
"pid": 1,
"childrens": [
{
"weight": 3,
"pid": 2,
"id": 3
}
],
"id": 2
}
],
"id": 1
}
],
"id": 0
}
4. 树过滤的优化
4.1 优化一：合并步骤2和步骤3
进行过滤的时候，因为是向上遍历的，完全可以将步骤2和步骤3合并起来，将构建树的过程中同时加上权重。修改上面方法,添加np.setWeight(np.getWeight()+n.getWeight());到 dfsTreeFilterForm() 中，不需要调用 dfsTree() 了;
public static void main(String[] args) {
//初始数据
ArrayList<Node> nodeList = new ArrayList<Node>(){{
add(new Node(1,1,0));
add(new Node(10,10,0));
add(new Node(2,2,1));
add(new Node(3,3,2));
add(new Node(4,4,10));
add(Node.createRootNode()); //添加根节点
}};
//过滤数据
ArrayList<Node> nodeListFilter = new ArrayList<Node>(){{
add(new Node(3,3,2));
}};
//转化为map方便随机读取
Map<Integer,NodeTree> nodeMap = new HashMap<>();
for(Node n : nodeList){
nodeMap.put(n.getId(),new NodeTree(n));
}
//转化链式结构为树形结构
for(Node n : nodeListFilter){
dfsTreeFilterForm(nodeMap.get(n.getId()),nodeMap);
}
String jsonStr = JSONUtil.toJsonStr(nodeMap.get(0));
JSONObject jsonObject = new JSONObject(jsonStr);
System.out.println(JSONUtil.toJsonPrettyStr(jsonObject.toString()));
}
//向上遍历
private static void dfsTreeFilterForm(NodeTree n, Map<Integer, NodeTree> nodesMap){
NodeTree np = nodesMap.get(n.getPid());
if(np.getChildrens() == null){
np.setChildrens(new ArrayList<>());
}
List<NodeTree> children = np.getChildrens();
if (!children.contains(n)){ //避免重复添加子节点，因为在向上遍历时,其同级节点已经向上遍历过了，如果不做判断，其父级的往上的都会重复添加父级节点。
children.add(n);
}
if(np.getPid() != null){
dfsTreeFilterForm(np,nodesMap);//向上传递
}
}
4.2 优化二：取消 contains() 的遍历，修改 list 为 set。
再重复添加子节点的判断这里之前使用的 contains()，每次都要遍历 list。现在改为 set 集合，每次 add() 时，如果返回 false 就表明之前已经添加过了，我们就不在添加权重，同时也避免了循环。
private static void dfsTreeFilterForm(NodeTree n, Map<Integer, NodeTree> nodesMap){
NodeTree np = nodesMap.get(n.getPid());
if(np.getChildrens() == null){
np.setChildrens(new HashSet<>());
}
Set<NodeTree> children = np.getChildrens();
if(children.add(n)){ //避免重复添加子节点，因为在向上遍历时,其同级节点已经向上遍历过了，如果不做判断，其父级的往上的都会重复添加父级节点。
np.setWeight(np.getWeight()+n.getWeight());
}
if(np.getPid() != null){
dfsTreeFilterForm(np,nodesMap);//向上传递
}
}