在项目开发过程中，我们经常会遇到树形数据结构的设计，例如菜单树，地区树和类别树等等。一般而言，我们需要把数据库中记录全取出来，然后构建树（注意的是，最好是一次性取出来，如果是ajax按需拉数据则不需要）。下面分享了递归和非递归两种方式：
package test.tree;
import java.util.ArrayList;
import java.util.List;
public class Node {
private String id;
private String parentId;
private String value;
private Node parent;
private List<Node> children;
public Node() {
super();
this.children = new ArrayList<>();
}
public Node(String value, String id, String parentId) {
this.value = value;
this.id = id;
this.parentId = parentId;
this.children = new ArrayList<>();
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
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 Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
public void addChild(Node child) {
if (!this.children.contains(child) && child != null)
this.children.add(child);
}
@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
if(obj instanceof Node) {
if(this.id.equals(((Node) obj).getId())) {
return true;
}
}
return false;
}
@Override
public String toString() {
return "Node [id=" + id + ", parentId=" + parentId + ", value=" + value + ", children=" + children + "]";
}
}
非递归的方式
package test.tree;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ListToTreeNoRecurse {
public static void main(String[] args) throws IOException {
List<Node> nodes = new ArrayList<>();
List<String> lines = Files
.readAllLines(Paths.get("C:\\Users\\95\\Desktop\\leetCode\\src\\test\\tree\\jsontest.txt"));
nodes.add(new Node("all", "0", null));
for (String line : lines) {
String[] values = line.split(",");
Node node = new Node(values[1].trim(), values[0].trim(), values[3].trim());
nodes.add(node);
}
long start = System.currentTimeMillis();
createTree(nodes);
long end = System.currentTimeMillis();
System.err.println((end - start));
}
private static void createTree(List<Node> nodes) {
Map<String, Node> mapTmp = new HashMap<>();
// Save all nodes to a map
for (Node current : nodes) {
mapTmp.put(current.getId(), current);
}
// loop and assign parent/child relationships
for (Node current : nodes) {
String parentId = current.getParentId();
if (parentId != null) {
Node parent = mapTmp.get(parentId);
if (parent != null) {
current.setParent(parent);
parent.addChild(current);
mapTmp.put(parentId, parent);
mapTmp.put(current.getId(), current);
}
}
}
System.out.println(mapTmp.get("0"));
}
}
递归的方法来
package test.tree;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import test.tree.Node;
public class TreeBuilder {
/**
* 使用递归方法建树
* @param Nodes
* @return
*/
public static List<Node> buildByRecursive(List<Node> Nodes) {
List<Node> trees = new ArrayList<Node>();
for (Node Node : Nodes) {
if ("0".equals(Node.getParentId())) {
trees.add(findChildren(Node,Nodes));
}
}
return trees;
}
/**
* 递归查找子节点
* @param Nodes
* @return
*/
public static Node findChildren(Node Node,List<Node> Nodes) {
for (Node it : Nodes) {
if(Node.getId().equals(it.getParentId())) {
if (Node.getChildren() == null) {
Node.setChildren(new ArrayList<Node>());
}
Node.getChildren().add(findChildren(it,Nodes));
}
}
return Node;
}
public static void main(String[] args) throws IOException {
List<Node> list = new ArrayList<Node>();
List<String> lines = Files.readAllLines(Paths.get("C:\\Users\\95\\Desktop\\leetCode\\src\\test\\tree\\jsontest.txt"));
for(String line:lines) {
String[] values = line.split(",");
Node node = new Node(values[1], values[0], values[3]);
list.add(node);
}
long beforeUsedMem=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
long start = System.currentTimeMillis();
List<Node> trees_ = TreeBuilder.buildByRecursive(list);
long afterUsedMem=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
long actualMemUsed=afterUsedMem-beforeUsedMem;
long end = System.currentTimeMillis();
System.out.println(trees_);
System.err.println((end - start));
System.err.println(actualMemUsed);
}
}
上述方法的测试数据是世界地区数据，下载地址是：https://epubi.oss-cn-shanghai.aliyuncs.com/jsontest.txt
经过测试，如果不打印树的话，非递归方法构建树是非常快的，远少于递归方法。打印树的话，非递归的方法的性能是略微优于递归的。
因为非递归方法构建的时候，只是构建child，parent之间的引用，在真正打印的时候，会调用toString方法对child进行打印，这个时候也是一个遍历的过程。在项目中还是推荐使用非递归方法，非递归方法比较可控。
该方法继承至AbstractCollection中的toString方法。
public String toString() {
Iterator<E> it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
