package com.xxx.pojo;import java.util.ArrayList;import java.util.List;public class ComboTree{	private String id;	private String text;	private String state;	private String pid;	private String clickFlag;	private List<ComboTree> children;	public ComboTree()	{		super();		this.setState("closed");		this.setId("00");		this.setText(null);		this.setClickFlag("off");		this.setChildren(new ArrayList<ComboTree>());	}	public void clear()	{		this.setState("closed");		this.setId(null);		this.setText(null);		this.setChildren(null);	}	@Override	public String toString()	{		StringBuilder sb = new StringBuilder();		sb.append("{\"id\":\"");		sb.append(this.id);		sb.append("\",\"text\":\"");		sb.append(this.text);		sb.append("\",\"clickFlag\":\"");		sb.append("off");		sb.append("\"");		if (!this.children.isEmpty())		{			sb.append(",\"state\":\"");			sb.append(this.state);			sb.append("\",\"children\":[");			boolean flag = false;			for (ComboTree c : this.children)			{				if (flag)					sb.append(",");				else					flag = true;				sb.append(c.toString());			}			sb.append("]");		}		sb.append("}");		return sb.toString();	}	public String getPid()	{		return pid;	}	public void setPid(String pid)	{		this.pid = pid;	}	public void addChildren(ComboTree ct)	{		this.children.add(ct);		// System.out.println("add");	}	//添加一个节点	public boolean addNode(ComboTree ct){		//如果需要添加的节点的PID 为当前节点的ID, 则直接		//添加, 返回true		if(this.id == ct.pid ||				(this.id != null && ct.pid != null && this.id.equals(ct.pid))){			this.children.add(ct);			return true;		}		//委托给子节点		for(ComboTree cct: this.children){			if(cct.addNode(ct))				return true;		}		//无法添加成功		return false;	}	public String getId()	{		return id;	}	public void setId(String id)	{		this.id = id;	}	public String getText()	{		return text;	}	public void setText(String text)	{		this.text = text;	}	public String getState()	{		return state;	}	public void setState(String state)	{		this.state = state;	}	public List<ComboTree> getChildren()	{		return children;	}	public void setChildren(List<ComboTree> children)	{		this.children = children;	}	public String getClickFlag()	{		return clickFlag;	}	public void setClickFlag(String clickFlag)	{		this.clickFlag = clickFlag;	}}

package com.xxx.util;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.Queue;import java.util.Set;import com.abc.pojo.ComboTree;public class TreeHelper {	/**	 * 输入无序的ComboTree 获得 List 类型的森林	 * @param list0 无序ComboTree节点	 	 * @return List<ComboTree> 森林	 * */	@SuppressWarnings("null")	public static List<ComboTree> makeTree(List<ComboTree> list0) throws Exception{				//以pId为Key,而以pid为相同的ComboTree作为List为Value		Map<String,List<ComboTree>> mapForPid = new HashMap<String,List<ComboTree>>();		//以Id为Tree, 用来快速寻找到RootPID		Map<String,ComboTree> mapForId = new HashMap<String,ComboTree>();		//root pid set		Set<String> rps = new HashSet<String>();				//构造  两种类型的map		for(ComboTree ct : list0){			//构造ID Map			mapForId.put(ct.getId(), ct);						//PID Map 构造			String pid = ct.getPid();			List<ComboTree> lct = mapForPid.get(pid);			if(lct == null){				//构造 Value类型				lct = new LinkedList<ComboTree>();				mapForPid.put(pid, lct);			}			//添加这个节点			lct.add(ct);		}				//制作rootPidSet		{			//已经被寻找过的ID			Set<String> keySet = new HashSet<String>();			//寻找RootPID			for(String key : mapForId.keySet()){				//沿pid 直到rootPID				while(true){					//已经处理过这种节点, 					//那么可以肯定该节点所在的rootPid已经被添加					if(keySet.contains(key)){						break;					}					//添加到keySet中, 表示该节点已经被处理					keySet.add(key);					ComboTree ct = mapForId.get(key);					if(ct == null){						//如果ct为null, 则表示该Key就是一个rootPID						rps.add(key);						break;					}					//下一个Pid					key = ct.getPid();				}			}		}				//虚拟root结果树		List<ComboTree> vts = new LinkedList<ComboTree>();		//对所有的root Pid 进行处理		for(String key : rps){			List<String> queue = new LinkedList<String>();			ComboTree vt = new ComboTree();			vt.setId(key);			vt.setPid(null);			vt.setText("虚拟节点");			//添加根Id			queue.add(key);			while(!queue.isEmpty()){				String pid = queue.remove(0); 				List<ComboTree> list = mapForPid.get(pid);				//没有pid对应的子树				if(list == null)					continue;				for(ComboTree ct : list){					//添加到queue中					queue.add(ct.getId());					//插入到正确的位置					if(!vt.addNode(ct)){						throw new Exception(ct+"无法插入到Tree中");					}				}			}			vts.add(vt);		}		//整理res结果		List<ComboTree> res = new LinkedList<ComboTree>();		for(ComboTree vct : vts){			//虚拟PID节点不能作为真实根节点			for(ComboTree ct: vct.getChildren()){				//添加真实节点				res.add(ct);			}					}		return res;	}	public static ComboTree getComboTree(String id,String pid,String name){		ComboTree t = new ComboTree();		t.setId(id);		t.setPid(pid);		t.setText(name);		return t;	}	public static void main(String[] args) throws Exception {		List<ComboTree> list = new LinkedList<ComboTree>();		list.add(getComboTree("0",null,"root"));		list.add(getComboTree("1","0","root"));		list.add(getComboTree("2","0","root"));		list.add(getComboTree("3","2","root"));		list.add(getComboTree("4","3","root"));		list.add(getComboTree("5","4","root"));		list.add(getComboTree("6","2","root"));		list.add(getComboTree("A",null,"root"));		list.add(getComboTree("B","A","root"));		list.add(getComboTree("C","A","root"));		list.add(getComboTree("D","B","root"));				list.add(getComboTree("a","aaaaa","root"));		list.add(getComboTree("aa","a","root"));		System.out.println(makeTree(list));			}}