在项目开发过程中，我们经常会遇到树形数据结构的设计，例如菜单树，地区树和类别树等等。一般而言，我们需要把数据库中记录全取出来，然后构建树（注意的是，最好是一次性取出来，如果是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
     
       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
      
        getChildren() {		return children;	}	public void setChildren(List
       
         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
     
       nodes = new ArrayList<>();		List
      
        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
       
         nodes) {		Map
        
          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
     
       buildByRecursive(List
      
        Nodes) {        List
       
         trees = new ArrayList
        
         ();        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
         
           Nodes) {        for (Node it : Nodes) {            if(Node.getId().equals(it.getParentId())) {                if (Node.getChildren() == null) {                    Node.setChildren(new ArrayList
          
           ()); } Node.getChildren().add(findChildren(it,Nodes)); } } return Node; } public static void main(String[] args) throws IOException { List
           
             list = new ArrayList
            
             (); List
             
               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
              
                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); } }
              
             
            
           
          
         
        
       
      
     

　　上述方法的测试数据是世界地区数据，下载地址是：

　　经过测试，如果不打印树的话，非递归方法构建树是非常快的，远少于递归方法。打印树的话，非递归的方法的性能是略微优于递归的。

　　因为非递归方法构建的时候，只是构建child，parent之间的引用，在真正打印的时候，会调用toString方法对child进行打印，这个时候也是一个遍历的过程。在项目中还是推荐使用非递归方法，非递归方法比较可控。

　　该方法继承至AbstractCollection中的toString方法。

　　

public String toString() {        Iterator
     
       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(' ');        }    }