浏览 10435 次
|
锁定老帖子 主题：如果根据递归表高效的生成树
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-09-17
由如下一个递归表数据结构，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);
}
}
}
}
}
大家有什么更高效的实现， 欢迎拍砖。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2007-09-18
大体思路没问题，感觉效率上有点……遍历的次数过多。
我觉得大概的算法可以是: 1、new所有的节点，并以No为key加入到一个Map中； 2、遍历Map，每个节点根据UpNo找自己的爹，没爹的就是根节点； 3、返回Tree； |
| 返回顶楼 | |
|
发表时间：2007-09-19
第二步 好像一次遍历也完不成吧。
|
| 返回顶楼 | |
|
发表时间：2007-09-20
这种问题我比较喜欢用map，首先map本身就是个树型结构，可以用他的实现类treeMap.还能帮你排续。而且map可以帮你高效的完成查找和插入的操作。
|
| 返回顶楼 | |
|
发表时间：2007-09-21
是啊一般都会用map
|
| 返回顶楼 | |
|
发表时间：2007-09-21
可以在id上下功夫
10--->root 1 1001-->子类1 1002--->子类2 10010001--->子类1的商品A 10010002---->子类1的商品B |
| 返回顶楼 | |
