Baidu Encyclopedia recursion Description:
The programming skill of the program calling itself is called recursion. Recursion as a algorithm stay Programming language Widely used in. A process or function In its definition or description, there is a method that directly or indirectly calls itself. It usually transforms a large and complex problem layer by layer into a smaller problem similar to the original problem. The recursive strategy can describe the multiple repeated calculations required in the problem-solving process with only a small number of programs, which greatly reduces the amount of code of the program. The power of recursion lies in using limited sentence To define the of the object Infinite set . Generally speaking, recursion needs boundary conditions, recursive forward segment and recursive return segment. When the boundary conditions are not satisfied, recursively advance; When the boundary conditions are met, it returns recursively.
preface:
In the process of system development, you may encounter some requirements. You need to build a tree structure. The database is generally represented by the parent id, such as building a menu, building a regional cascade, building a department hierarchy, and so on. Although we can query through database SQL, we generally query all data at one time through SQL and process it into a tree structure in the program. This article describes how to process a list < T > into a desired tree structure.
1. Object
@Data
public class Tree {
// id
private Integer id;
// Folder name
private String name;
// Number of files in folder
private Integer count;
// Parent folder ID
private Integer parentId;
// Subfolder object
private List<Tree> children;
}The easiest tree to think of is actually the folder of our operating system. Let's take the folder as an example:
2. list to tree structure
According to the above folder structure, simulate the object list queried in the database to build the data for test:
// Top level folder directory, parentId = 0 List<Tree> treeList = Arrays.asList(new Tree(1, "A", 2, 0, null), new Tree(2, "B", 1, 1, null), new Tree(3, "C", 0, 1, null), new Tree(4, "D", 1, 2, null), new Tree(5, "E", 1, 2, null), new Tree(6, "F", 0, 0, null), new Tree(7, "G", 1, 0, null) );
Here, according to the Java version, three methods are provided to turn the list into a tree:
1. for method to tree
public class TreeTest {
public static void main(String[] args) {
List<Tree> node = forMethod(treeList);
System.out.println(node);
}
/**
* The double for loop method is transformed into a tree structure
* @param treeList
* @return
*/
public static List<Tree> forMethod(List<Tree> treeList) {
List<Tree> rootTree = new ArrayList<>();
for (Tree tree : treeList) {
// The first step is to filter out the top-level parent node
if (0 == tree.getParentId()) {
rootTree.add(tree);
}
// Step 2: filter out the list of all child nodes under the parent node
for (Tree node : treeList) {
if (node.getParentId().equals(tree.getId())) {
if (CollectionUtils.isEmpty(tree.getChildren())) {
tree.setChildren(new ArrayList<>());
}
tree.getChildren().add(node);
}
}
}
return rootTree;
}
}2. Recursive method to tree
public class TreeTest {
public static void main(String[] args) {
List<Tree> node = recursionMethod(treeList);
System.out.println(node);
}
/**
* The recursive method is transformed into a tree structure
* @param treeList
* @return
*/
public static List<Tree> recursionMethod(List<Tree> treeList) {
List<Tree> trees = new ArrayList<>();
for (Tree tree : treeList) {
// Find parent node
if (0 == tree.getParentId()) {
// Call recursive methods to populate the child node list
trees.add(findChildren(tree, treeList));
}
}
return trees;
}
/**
* Recursive Method
* @param tree Parent node object
* @param treeList All lists
* @return
*/
public static Tree findChildren(Tree tree, List<Tree> treeList) {
for (Tree node : treeList) {
if (tree.getId().equals(node.getParentId())) {
if (tree.getChildren() == null) {
tree.setChildren(new ArrayList<>());
}
// Recursive call itself
tree.getChildren().add(findChildren(node, treeList));
}
}
return tree;
}
}3. stream method to tree
public class TreeTest {
public static void main(String[] args) {
List<Tree> node = recursionMethod(treeList);
System.out.println(node);
}
/**
* stream Method is converted to a tree structure
* @param treeList
* @return
*/
public static List<Tree> streamMethod(List<Tree> treeList) {
List<Tree> list = treeList.stream()
// Filter out parent nodes
.filter(t -> t.getParentId() == 0)
// Set the child node list of the parent node
.map(item -> {item.setChildren(streamGetChildren(item, treeList)); return item;})
.collect(Collectors.toList());
return list;
}
/**
* stream Recursively find the list of child nodes
* @return
*/
public static List<Tree> streamGetChildren(Tree tree, List<Tree> treeList) {
List<Tree> list = treeList.stream()
.filter(t -> t.getParentId().equals(tree.getId()))
.map(item -> {item.setChildren(streamGetChildren(item, treeList)); return item;})
.collect(Collectors.toList());
return list;
}
}summary
It can be seen from the above three methods that they are actually the same routine. No matter how they are written, the core idea remains the same. We can summarize the following rules:
1. Find all root parent nodes
2. Compare the parent node with the whole set list to find out the child nodes under the parent node (recursion is required here, constantly adjust yourself, filter all the parent nodes and set the child node list under the parent node)
3. Assemble into a tree List and return.
It can be seen that in the method of converting stream to tree, there are similar parts between streamMethod and streamGetChildren methods:
-
Filter and compare parent nodes every time;
-
Set the child node list of the parent node every time,
Moreover, there is a problem that the root parent node ID is written dead, which cannot be applied flexibly. We extract the public part and can optimize it like this.
4. stream to tree optimization
// In the first optimization, we combine the same parts of the above two methods
public class TreeTest {
public static void main(String[] args) {
List<Tree> node = streamMethod(0, treeList);
System.out.println(node);
}
/**
* stream Optimization of method transformation tree structure method
* @param parentId
* @param treeList
* @return
*/
public static List<Tree> streamMethod(Integer parentId, List<Tree> treeList) {
List<Tree> list = treeList.stream()
// Filter parent nodes
.filter(t -> t.getParentId().equals(parentId))
// Recursively set child nodes
.map(item -> {
item.setChildren(streamMethod(item.getId(), treeList));
return item;
})
.collect(Collectors.toList());
return list;
}
}// The second optimization is just different in writing, and the core idea remains the same
public class TreeTest {
public static void main(String[] args) {
List<Tree> node = streamMethod(0, treeList);
System.out.println(node);
}
/**
* stream Optimization of method transformation tree structure method
* @param parentId
* @param treeList
* @return
*/
public static List<Tree> streamMethod(Integer parentId, List<Tree> treeList) {
List<Tree> list = new ArrayList<>();
Optional.ofNullable(treeList).orElse(new ArrayList<>())
.stream()
// The list of primary and parent nodes is filtered for the first time and enters the loop. The loop enters recursion and filters the list of secondary and parent nodes passed recursively
.filter(root -> root.getParentId().equals(parentId))
// Recursion, the last parent node filters out its child node list from the whole list and assembles it in turn
.forEach(tree -> {
List<Tree> children = streamMethod(tree.getId(), treeList);
tree.setChildren(children);
list.add(tree);
});
return list;
}
}3. The attribute values of the child nodes of the tree structure are accumulated to the parent node
Through the above code, we have successfully converted the list < T > into the tree structure we want, but at this time, we are required to attach the number of files contained in the folder after the folder name,
The number of files in the database or constructed collection data only counts the number of files under the folder itself, not all folders in the subfolder. We need to set the count attribute of subfolders one by one
Level is added to the count attribute of the parent node to update it.
public class TreeTest {
public static void main(String[] args) {
// treeList is a collection of processed tree structures
countHandler(treeList);
System.out.println(treeList);
}
/**
* Recursively accumulate the attribute values of child nodes to parent nodes
* @param treeList
* @return
*/
private int countHandler(List<Tree> treeList) {
int count = 0;
if(CollectionUtil.isEmpty(treeList)){
return count;
}
for (Tree tree : treeList) {
count += tree.getCount();
if (CollectionUtil.isEmpty(tree.getChildren())) {
continue;
}
count += countHandler(tree.getChildren());
tree.setCount(count);
if (tree.getParentId() == null || tree.getParentId() == 0) {
count = 0;
}
}
return count;
}
}