`
icess
  • 浏览: 252809 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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

阅读更多
由如下一个递归表数据结构,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;

相关推荐

    Java递归算法构造JSON树形结构

    Java 递归算法构造 JSON 树形结构是指通过 Java 语言使用递归算法将数据库中的菜单表构建成树形的 JSON 格式发送给第三方。这种方法可以将复杂的树形结构数据转换成易于理解和处理的 JSON 格式。 在 Java 中,使用...

    运用递归生成树形结构 Treeview

    它允许直接将数据源(如数据集、列表或实体)绑定到Treeview,自动根据数据结构生成树形结构,简化了开发过程。使用`BindingTreeView`,你可以省略手动创建和管理TreeNode的步骤,只需关注数据的准备和绑定。 总结...

    数据结构邻接矩阵DFS非递归算法以及PRIM算法最小生成树

    本篇文章将深入探讨如何利用邻接矩阵实现深度优先遍历(DFS)的非递归算法,并介绍PRIM算法构建最小生成树。 邻接矩阵是一个二维数组,其中的每个元素表示图中两个节点之间是否存在边。对于无向图,邻接矩阵是对称...

    最小生成树C实现

    Kruskal算法则是另一种贪心策略,它首先将所有边按权重从小到大排序,然后依次考虑每条边,如果这条边连接的两个顶点不在同一棵树中,就将其加入到最小生成树中。为了避免形成环路,需要使用并查集数据结构来维护每...

    WPF TreeView绑定集合生成树

    本篇文章将深入探讨如何利用WPF的`TreeView`控件结合数据绑定技术,从集合中动态生成树形结构。 一、`TreeView`控件的基本概念 `TreeView`控件是WPF中的一个视图控件,它可以显示一系列可展开和折叠的节点,每个...

    二叉树的生成以及非递归遍历C++实现

    ### 二叉树的生成及非递归遍历C++实现 #### 一、二叉树的基本概念 在深入探讨二叉树的生成与非递归遍历之前,我们先来了解一下二叉树的基本概念。 - **二叉树定义**:二叉树是一种树形结构,其中每个节点最多有两...

    根据数据库表结构自动生成产品结构树

    "根据数据库表结构自动生成产品结构树"这一技术,其核心是将数据库中的BOM数据转换成可视化、层次化的结构,以树形图的方式展示出来。这涉及到数据库查询、数据处理和图形化表示等多个方面的知识。 首先,我们需要...

    Tree(将数据库记录生成树)

    总之,"Tree(将数据库记录生成树)"是一个涉及数据结构、XML转换和递归算法的复杂任务。通过Java编程,我们可以高效地完成这个任务,将数据库的记录以层次结构的方式展现,从而提高数据的可读性和操作性。理解并...

    Spring+iBatis+JDom递归生成XML树

    在IT行业中,构建一个能够递归生成XML树的系统是一项常见的任务,特别是在处理复杂的数据结构时。本项目结合了Spring、iBatis和JDom这三个强大的技术,它们各自扮演着不同的角色来实现这一目标。 首先,Spring是一...

    生成树对象及读取操作

    生成树对象通常指的是在编程中构建和操作树结构的过程。在这个主题中,我们将深入探讨如何创建、操作以及读取树对象。 首先,我们需要理解树的基本概念。树由节点(或顶点)和边组成,其中每个节点可以有零个或多...

    jsp jstl 递归 输出树 Tree 后台 Java 集合 递归 实现通用 树Tree

    总结来说,通过Java集合构建树结构,结合JSP和JSTL的递归功能,我们可以高效地生成和展示复杂的树形数据。这种技术广泛应用于各种Web应用程序中,提供清晰、直观的用户界面,以呈现层级关系数据。

    数据结构 广度 深度 拓扑 最短路径 最小生成树

    在本主题中,我们将深入探讨“广度优先搜索”(BFS)、“深度优先搜索”(DFS)、“拓扑排序”、“最短路径算法”以及“最小生成树”这五个关键知识点,并以C语言作为实现工具。 首先,让我们从广度优先搜索开始。...

    学学Python_49类的成员08 生成器的使用:递归

    在Python编程中,生成器(Generator)是一种特殊的迭代器,它允许我们以声明式的方式编写代码,而不是使用传统的函数返回值。...在实际开发中,应根据具体需求选择合适的生成器和递归策略,以优化程序性能。

    ee.rar_最小生成树_最小生成树 课程设计_车站编码

    在IT领域,特别是数据结构与算法的学习中,"最小生成树"是一个至关重要的概念,它在图论中占据着核心地位。最小生成树是连接一个加权无向图中所有顶点的树形子图,使得该子图的边权重之和尽可能小。这个问题在实际...

    递归实现的 ADF Dynamic tree

    DFS常用于生成树的深度,而BFS则适用于生成层次结构。此外,优化是必要的,因为无限递归可能导致栈溢出。可以设置递归深度限制,或者使用迭代方法(如堆栈或队列)模拟递归。 总之,递归实现的ADF动态树是一种高效...

    图的遍历、最短路径、最小生成树

    2. **Kruskal算法** 则是按边的权重从小到大排序,依次考虑每条边,如果加入这条边不会形成环,则将其加入最小生成树。 以上所述的这些算法和概念在实际编程中常用于解决复杂问题,例如网络路由、交通规划等。通过...

    有向图生成树 MFC实现的

    有向图生成树是一种算法,用于从有向图中找到一棵子树,这棵子树包含原图的所有顶点,并且没有环路。这个过程在解决许多问题时非常有用,例如网络路由、任务调度等。 MFC(Microsoft Foundation Classes)是微软...

    C#利用 treeview生成树

    本篇将深入探讨如何利用C#和`TreeView`控件从数据库中读取数据并生成树形结构。 首先,我们需要理解`TreeView`控件的基本用法。`TreeView`控件由多个`TreeNode`对象组成,每个`TreeNode`代表树的一个节点,可以包含...

    生成JSON树型表结构

    总的来说,生成JSON树型表结构是将层级数据转换为易于EXT树组件解析的格式,通过合理的数据库查询和后端处理,结合前端EXT框架,可以实现高效且美观的树形数据展示。这个过程涉及到数据结构、JSON序列化、前端UI组件...

    不用递归实现的无限级树型菜单

    在不使用递归的情况下,我们可以利用迭代的方式来生成树结构的数据。这个Handler可能是从数据库(如`Menu.mdb`)中查询菜单项,然后将这些数据转换为XML格式,每条记录代表一个菜单节点,包含父节点ID和子节点列表。...

Global site tag (gtag.js) - Google Analytics