Introduction:
In daily development, we often encounter the need to convert the data returned from the database into a tree structure, or need to bind the hierarchical relationship of the data converted into the tree structure and then return it. For example, we need to count the number of data under the current node. How many nodes, etc., so we need to encapsulate a ListToTree tool class and learn how to traverse the data through depth first.
Data preparation:
First, briefly prepare the data with a parent-child relationship.
package data;
/**
* @author sinder
* @date 2023/11/8 21:40
*/
public class OrgData {
private String id;
private String pId;
private String orgName;
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getpId() {
return pId;
}
public void setpId(String pId) {
this.pId = pId;
}
public String getOrgName() {
return orgName;
}
public void setOrgName(String orgName) {
this.orgName = orgName;
}
}
package data;
import java.util.ArrayList;
import java.util.List;
/**
* Generate data and simulate database queries
* @author sinder
* @date 2023/11/8 22:17
*/
public class SingData {
public static List<OrgData> getData() {
OrgData orgData1 = new OrgData();
orgData1.setId("1");
orgData1.setpId("root");
orgData1.setOrgName("Root Node A");
OrgData orgData2 = new OrgData();
orgData2.setId("2");
orgData2.setpId("root");
orgData2.setOrgName("Root Node B");
OrgData orgData3 = new OrgData();
orgData3.setId("3");
orgData3.setpId("1");
orgData3.setOrgName("A directory");
OrgData orgData4 = new OrgData();
orgData4.setId("4");
orgData4.setpId("2");
orgData4.setOrgName("B directory");
List<OrgData> list = new ArrayList<>();
list.add(orgData1);
list.add(orgData2);
list.add(orgData3);
list.add(orgData4);
return list;
}
}
Under normal circumstances, we will choose to encapsulate a tool class that converts List to Tree, and traverses Tree data through chained sequential LinkedList storage. Here we use stream to implement it, as follows:
package data;
import java.util.List;
/**
* Build tree data
* @author sinder
* @date 2023/11/8 22:30
*/
public class TreeBean {
private String treeId;
private String treePid;
private String orgName;
private Integer flag = 0;
private List<TreeBean> children;
private OrgData orgData;
public String getTreeId() {
return treeId;
}
public void setTreeId(String treeId) {
this.treeId = treeId;
}
public String getOrgName() {
return orgName;
}
public void setOrgName(String orgName) {
this.orgName = orgName;
}
public String getTreePid() {
return treePid;
}
public void setTreePid(String treePid) {
this.treePid = treePid;
}
public List<TreeBean> getChildren() {
return children;
}
public void setChildren(List<TreeBean> children) {
this.children = children;
}
public OrgData getOrgData() {
return orgData;
}
public void setOrgData(OrgData orgData) {
this.orgData = orgData;
}
public Integer getFlag() {
return flag;
}
public void setFlag(Integer flag) {
this.flag = flag;
}
@Override
public String toString() {
return "TreeBean{" +
"treeId='" + treeId + '\'' +
", treePid='" + treePid + '\'' +
", orgName='" + orgName + '\'' +
", children=" + children +
'}';
}
}
package utils;
import data.OrgData;
import data.SingData;
import data.TreeBean;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.stream.Collectors;
/**
* Convert List to Tree
*
* @author sinder
* @date 2023/11/8 22:28
*/
public class ListToTreeUtil {
public static List<TreeBean> toTree(List<OrgData> list, String root) {
if (list.isEmpty()) {
return new ArrayList<>();
}
// Build data
List<TreeBean> treeBeans = list.stream().map(item -> {
TreeBean treeBean = new TreeBean();
treeBean.setTreeId(item.getId());
treeBean.setTreePid(item.getpId());
treeBean.setOrgName(item.getOrgName());
return treeBean;
}).collect(Collectors.toList());
//Construct Map data
Map<String, List<TreeBean>> treeMap = treeBeans.stream().collect(Collectors.groupingBy(item -> {
if (item.getTreePid().isEmpty()) {
item.setTreePid(root);
}
return item.getTreePid();
}));
//Group data
return treeBeans.stream().peek(data -> {
List<TreeBean> children = treeMap.get(data.getTreeId());
if (children != null & amp; & amp; !children.isEmpty()) {
data.setChildren(children);
}
}).filter(data -> data.getTreePid().equals(root)).collect(Collectors.toList());
}
}
Results of the:
Traverse the tree data in the form of a linked list:
import data.OrgData;
import data.SingData;
import data.TreeBean;
import utils.ListToTreeUtil;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
/**
* @author sinder
* @date 2023/11/8 20:44
*/
public class Main {
public static void main(String[] args) {
// Simulate query data
List<OrgData> orgDataList = SingData.getData();
//Construct tree data
List<TreeBean> treeBean = ListToTreeUtil.toTree(orgDataList, "root");
//Use LinkedList to implement chained queue and achieve deep traversal
LinkedList<TreeBean> stack = new LinkedList<>();
stack.addAll(treeBean);
while (!stack.isEmpty()) {
//Start accessing from the top of the stack
TreeBean pop = stack.peek();
// Flag=1 indicates that it has been traversed once and the node has child nodes
if (pop.getFlag() == 1) {
OrgData orgData =pop.getOrgData();
List<TreeBean> children = pop.getChildren();
// Get the node name of the child node, and you can also perform other operations
List<String> collect = children.stream().map(TreeBean::getOrgName).collect(Collectors.toList());
StringBuilder builder = new StringBuilder();
for (String s : collect) {
builder.append(s);
builder.append(">");
}
pop.setOrgName(builder.toString());
orgData.setOrgName(pop.getOrgName());
// Pop off the stack. The current node has been counted. Pop off the stack to get the next peek at the top of the stack.
stack.pop();
} else {
// The flag is 0, indicating that it has not been traversed. Determine whether the leaf node (the bottom) has been traversed.
if (pop.getChildren()!= null & amp; & amp; !pop.getChildren().isEmpty()) {
// non-leaf nodes
pop.setFlag(1);
List<TreeBean> children = pop.getChildren();
for (TreeBean child : children) {
// Push the leaf node into the stack and put it on the top of the stack to achieve depth traversal, next
stack.push(child);
}
} else {
//The leaf node can be popped directly from the stack, and cnt is itself
stack.pop();
}
}
}
// Traverse the final data
for (OrgData orgData : orgDataList) {
System.out.println(orgData.toString());
}
}
}
But now there is a problem. When the data we respond to changes from OrgData to other types, we need to encapsulate it into a generic class to make our tree data generation class a universal one. The complete code is as follows:
Complete code: JAVA converts List to Tree and depth-first traversal
package data;
import java.util.List;
/**
* Define an interface so that each response data entity can implement it
* @author sinder
* @date 2023/11/9 0:31
*/
public interface Tree<T> {
String getTreeId();
String getTreePid();
void setChild(List<T> list);
}
package data;
import java.util.List;
/**
* Implement Tree<OrgData> and define the response type as itself
* Define the parameters returned to be converted into a tree
* @author sinder
* @date 2023/11/8 21:40
*/
public class OrgData implements Tree<OrgData>{
private String id;
private String pId;
private String orgName;
// Parameters required to convert to tree
private Integer flag = 0;
private List<OrgData> child;
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getpId() {
return pId;
}
public void setpId(String pId) {
this.pId = pId;
}
public String getOrgName() {
return orgName;
}
public void setOrgName(String orgName) {
this.orgName = orgName;
}
public Integer getFlag() {
return flag;
}
public void setFlag(Integer flag) {
this.flag = flag;
}
public List<OrgData> getChild() {
return child;
}
@Override
public String toString() {
return "OrgData{" +
"id='" + id + '\'' +
", pId='" + pId + '\'' +
", orgName='" + orgName + '\'' +
'}';
}
@Override
public String getTreeId() {
return id;
}
@Override
public String getTreePid() {
return pId;
}
@Override
public void setChild(List<OrgData> list) {
this.child = list;
}
}
ListToTree method
package utils;
import data.OrgData;
import data.SingData;
import data.Tree;
import data.TreeBean;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.stream.Collectors;
/**
* Convert List to Tree
* <T extends Tree> tells the compiler that there is a get method of Tree
*
* @author sinder
* @date 2023/11/8 22:28
*/
public class ListToTreeUtil {
public static <T extends Tree> List<T> toTree(List<T> list, String root) {
// When the root node is null, define an initial value to prevent null
String treeRoot = "treeRoot";
String finalRoot = root;
if (list.isEmpty()) {
return new ArrayList<>();
}
//Construct Map data
//Group by pid and get all child node sets
Map<String, List<T>> childMap =
list.stream()
.collect(Collectors.groupingBy(item -> {
String treePid = item.getTreePid();
if (treePid == null) {
treePid = treeRoot;
}
return treePid;
}));
return list.stream().peek(
data -> {
List<T> children = childMap.get(data.getTreeId());
if (children != null & amp; & amp; !children.isEmpty()) {
data.setChild(children);
}
})
.filter(data -> data.getTreePid().equals(finalRoot))
.collect(Collectors.toList());
}
}
Depth-first traversal
import data.OrgData;
import data.SingData;
import data.TreeBean;
import utils.ListToTreeUtil;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
/**
* @author sinder
* @date 2023/11/8 20:44
*/
public class Main {
public static void main(String[] args) {
// Simulate query data
List<OrgData> orgDataList = SingData.getData();
//Construct tree data
List<OrgData> treeBean = ListToTreeUtil.toTree(orgDataList, "root");
//Use LinkedList to implement chained queue and achieve deep traversal
LinkedList<OrgData> stack = new LinkedList<>();
stack.addAll(treeBean);
while (!stack.isEmpty()) {
//Start accessing from the top of the stack
OrgData pop = stack.peek();
// Flag=1 indicates that it has been traversed once and the node has child nodes
if (pop.getFlag() == 1) {
List<OrgData> children = pop.getChild();
// Get the node name of the child node, and you can also perform other operations
List<String> collect = children.stream().map(OrgData::getOrgName).collect(Collectors.toList());
StringBuilder builder = new StringBuilder();
for (String s : collect) {
builder.append(s);
builder.append(">");
}
pop.setOrgName(builder.toString());
// Pop off the stack. The current node has been counted. Pop off the stack to get the next peek at the top of the stack.
stack.pop();
} else {
// The flag is 0, indicating that it has not been traversed. Determine whether the leaf node (the bottom) has been traversed.
if (pop.getChild()!= null & amp; & amp; !pop.getChild().isEmpty()) {
// non-leaf nodes
pop.setFlag(1);
List<OrgData> children = pop.getChild();
for (OrgData child : children) {
// Push the leaf node into the stack and put it on the top of the stack to achieve depth traversal, next
stack.push(child);
}
} else {
//The leaf node can be popped directly from the stack, and cnt is itself
stack.pop();
}
}
}
// Traverse the final data
for (OrgData orgData : orgDataList) {
System.out.println(orgData.toString());
}
}
}
The article mainly talks about the tree data generation strategy and the in-depth traversal of tree data. Overall, a tree data is constructed first. In order to be compatible with the traversal after converting multiple Object data into trees, generics are used and the Tree interface is defined. , providing getid, getPid, setChild and other operation methods. After the entity class implements the Tree interface, it can use the corresponding methods to operate the ip and pid related to the parent-child relationship and the child nodes to build related tree data. This is also convenient in Using LinkedList to deeply traverse the tree can more flexibly operate the data of parent and child nodes. Deep traversal is mainly achieved by popping and pushing the stack, traversing all the way from the parent node to the leaf node before stopping.
The article is only a reference example. For more and better implementation methods, please leave comments!