如果根据递归表高效的生成树

由如下一个递归表数据结构，UpBranchNo为该节点的父亲节点，如果为1代表该节点为根节点。
注意： 递归表大家都比较熟悉，如果保存在数据库表中的话， 操作起来会比较方便， 但是这里请注意 该结构是通过一个外部程序返回的一个数据集合，不是在数据库中的。 这样的话如何生成树结构才高效呢。

*********************************************
No.   BranchNo.   Label        UpBranchNo.
1     6666        test6          1           
2     11          1234567890     6666        
3     22          测试2002       6666        
4     44          44             6666        
5     55          55             6666        
6     66          66             6666        
7     77          7              6666        
8     101         测试2027       11        
9     223         测试2027d      11        
10     302         chi           6666        
11     403         测试2027      6666        
12     500         测试202       6666        
13     801         测试17        6666        
14     802         测试16        6666        
15     803         测试15        6666        
16     805         0805          6666        
17     829         测试132       77        
18     830         0830          77        
19     831         0831          6666        
20     866         测试12        6666        
21     995         测试1         6666        
22     1110        测试          829        
23     1234        xym           829        
24     1982        zhouxin       829        
25     2001        测试2001      6666        
26     2002        测试2002      6666        
27     2003        测试2003      1982        
28     2004        测试2004      1982 
********************************************* 

下面是一个实现， 在测试的时候发现数据很多的话， 效率不是很高。
节点实现类： Branch

public class Branch {
	
	private int branchNo;
	private String branchName; 
	private int upBranchNo ;

   ... getter and setter 函数省略
}

构造树：Tree

public class Tree {
//ds 为包含该数据集合的一个数据集
	public Branch normalOrganization(ds) {
		 
		List<Branch> branchs = new ArrayList<Branch>(ds.getRows());
		while (!ds.end()) {

			Branch branch = new Branch();
			branch.setBranchName(ds.value("branch_name"));
			branch.setBranchNo(ds.value("branch_no"));
			branch.setUpBranchNo(ds.value("up_branch_no"));
			branchs.add(branch);
			ds.next();
			
		}

		System.out.println("*********************************************");

		// 利用得到的branchs 构造一棵树结构
		return buildBranchTree(branchs);
	}

	private Branch buildBranchTree(List<Branch> branchs) {
		Branch topBranch = null;
		for (Iterator iterator = branchs.iterator(); iterator.hasNext();) {
			Branch branch = (Branch) iterator.next();
			if (1 == branch.getUpBranchNo()) {
				topBranch = branch;
				topBranch.setBranchs(new ArrayList<Branch>());
				// branchs.remove(branch); // 删除该数据， 减少下次的查询时间
				iterator.remove();
				buildTree(topBranch, branchs);

			}
			break;
		}
		
		return topBranch;

	}

	private void buildTree(Branch parent, List<Branch> branchs) {
		for (Iterator iterator = branchs.iterator(); iterator.hasNext();) {
			Branch branch = (Branch) iterator.next();
			if (branch.getUpBranchNo() == parent.getBranchNo()) {
				if (null == parent.getBranchs())
					parent.setBranchs(new ArrayList<Branch>());
				parent.getBranchs().add(branch);
				iterator.remove();
			}
		}
		if (branchs.size() == 0)
			return;
		if (null != parent.getBranchs()) {

			for (Branch branch2 : parent.getBranchs()) {
				if (1 == branch2.getBranchType()) {
					buildTree(branch2, branchs);
				}
			}
		}

	}

}

大家有什么更高效的实现， 欢迎拍砖。

评论

5 楼 ray_linn 2007-09-21  

可以在id上下功夫


10--->root 1
1001-->子类1
1002--->子类2
10010001--->子类1的商品A
10010002---->子类1的商品B

4 楼 rinapt 2007-09-21  

是啊一般都会用map

3 楼 baallee 2007-09-20  

这种问题我比较喜欢用map，首先map本身就是个树型结构，可以用他的实现类treeMap.还能帮你排续。而且map可以帮你高效的完成查找和插入的操作。

2 楼 icess 2007-09-19  

第二步 好像一次遍历也完不成吧。

1 楼 Zmud 2007-09-18  

大体思路没问题，感觉效率上有点……遍历的次数过多。

我觉得大概的算法可以是:
1、new所有的节点，并以No为key加入到一个Map中；
2、遍历Map，每个节点根据UpNo找自己的爹，没爹的就是根节点；
3、返回Tree；