树生成器

这几天在写一个外快，而写之前的TT随笔比较耗时，故先搁着。

前天写了一个树生成器，感觉还是挺不错的，相对来说还是比较灵活的，代码也比较简单。

先贴上生成器的代码：

 

package com.tt.pub.utils;

import java.util.List;
import java.util.Stack;
/**
 * Desc:树生成工具。
 * @author Small
 * @Email [e-mail]
 * @since 2013-6-14
 *
 */
public class TreeGen {

	/**
	 * Desc:树生成模板。
	 * @author Small
	 * @Email [e-mail]
	 * @since 2013-6-14
	 *
	 * @param <E>
	 * @param <V>
	 */
	public static interface ITreeTmp<E, V> {
	
		/**
		 * Desc:将源对象转换为目标对象（树节点）。
		 * @author Small
		 * @Email [e-mail]
		 * @since 2013-6-14
		 * 
		 * @param src
		 * @return
		 */
		public V trans(E src);
		
		/**
		 * Desc:是否将当前node入栈？如果入栈，请记得为节点构造父子关系。
		 * @author Small
		 * @Email [e-mail]
		 * @since 2013-6-14
		 * 
		 * @param node
		 * @param lastNode
		 * @return
		 */
		public boolean isPush(V node, V lastNode);
	}

	/**
	 * Desc:通过有一定规律的数组（请先进行排序），构建树数组。
	 * @author Small
	 * @Email [e-mail]
	 * @since 2013-6-14
	 * 
	 * @param srcList
	 * @param tmp
	 * @return
	 */
	public static <E, V> List<V> gen(List<E> srcList, ITreeTmp<E, V> tmp){
		List<V> treeList = CollUtils.newArrayList();
		Stack<V> stack = CollUtils.newStack();
		for(int i = 0; i < srcList.size(); ++i){
			E src = srcList.get(i);
			V node = tmp.trans(src);
			if(stack.size() == 0){//如果栈为空，则为树根
				treeList.add(node);//添加为根节点
				stack.push(node);//当前元素进栈
				continue;
			}
			while(stack.size() > 0){//进行栈操作
				V lastNode = stack.lastElement();//取顶级元素进行比较
				if(tmp.isPush(node, lastNode)) {
					stack.push(node);//当前元素进栈
					break;
				}
				else stack.pop();//未匹配到则出栈
			}
		}
		return treeList;
	}
}

 

 

 所需要的数据格式如下：

var menuInfos = [{
	id : "menu001"
},{
	id : "menu001001"
},{
	id : "menu001002"
},{
	id : "menu001002001"
},{
	id : "menu002"
},{
	id : "menu002001"
}];

 数据按一定顺序排列，并且有一定规则。

使用的范例如下：

先创建一个模板，模板需要实现TreeGen中的ITreeTmp接口：

package com.tt.pvl.tmp;

import com.tt.pub.utils.TreeGen.ITreeTmp;
import com.tt.pvl.pojo.Pvl;
import com.tt.pvl.pojo.TreeNode4EUi;
/**
 * Desc:菜单树模板。
 * @author Small
 * @Email [e-mail]
 * @since 2013-6-14
 *
 */
public class MenuTreeTmp implements ITreeTmp<Pvl, TreeNode4EUi> {

	@Override
	public TreeNode4EUi trans(Pvl src) {
		TreeNode4EUi node = new TreeNode4EUi();
		node.setId(src.getCode());
		node.setText(src.getName());
		node.setUrl(src.getContent());
		return node;
	}

	@Override
	public boolean isPush(TreeNode4EUi node, TreeNode4EUi lastNode) {
		if(!node.getId().startsWith(lastNode.getId())) return false;
		lastNode.addChild(node);//构建树层级关系
		return true;
	}

}

 调用方式：

List<Pvl> menus = pvlService.getByType(PvlConst.PVL_TYPE_MENU);
List<TreeNode4EUi> treeList = TreeGen.gen(menus, new MenuTreeTmp());

 大概的思路是运用了栈来进行操作：

    如果栈为空，那么当前元素就作为根节点；

    如果当前元素是栈最后一个节点的子节点，则创建父子关系，并将当前节点推入栈；

    如果当前元素不是是栈最后一个节点的子节点，则将元素出栈，继续循环，知道创建父子关系或者栈为空。

 

 

 

后记：

 

实在惭愧，没有测试完整，指测试了树列表个数为1的，后面测试的时候才发现了bug。其实只要把TreeGen的gen方法中的循环部分的代码对调下就行了~~代码如下：

	public static <E, V> List<V> gen(List<E> srcList, ITreeTmp<E, V> tmp){
		List<V> treeList = CollUtils.newArrayList();
		Stack<V> stack = CollUtils.newStack();
		for(int i = 0; i < srcList.size(); ++i){
			E src = srcList.get(i);
			V node = tmp.trans(src);
			while(stack.size() > 0){//进行栈操作
				V lastNode = stack.lastElement();//取顶级元素进行比较
				if(tmp.isPush(node, lastNode)) {
					stack.push(node);//当前元素进栈
					break;
				}
				else stack.pop();//未匹配到则出栈
			}
			if(stack.size() == 0){//如果栈为空，则为树根
				treeList.add(node);//添加为根节点
				stack.push(node);//当前元素进栈
				continue;
			}
		}
		return treeList;
	}