`
james_lover
  • 浏览: 44332 次
社区版块
存档分类
最新评论

通用树

阅读更多
package com.test.me;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.locks.ReentrantLock;

public class Tree<T> {
	
	class TreeNode {
		private TreeNode parent;
		private volatile Set<TreeNode> children;
		private T attachment;

		public TreeNode(T attach) {
			attachment = attach;
		}

		@Override
		public int hashCode() {
			return attachment.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			TreeNode other = (TreeNode) obj;
			if (attachment == null) {
				if (other.attachment != null)
					return false;
			} else if (!attachment.equals(other.attachment))
				return false;
			return true;
		}
	}

	public Tree(T attach) {
		this.root = new TreeNode(attach);
	}

	private TreeNode root;

	private ReentrantLock lock = new ReentrantLock();

	public T getRoot() {
		return root.attachment;
	}

	/**
	 * 在parent下增加一个子节点,
	 *
	 * @return 只有parent存在于树内,且将要插入的不在tree内,插入成功才返回true
	 */
	public boolean addchild(T parent, T attachment) {
		TreeNode parentNode = findTreeNode(parent);

		// 只有attachment不存的时才加入
		if (parentNode != null) {

			// 新增children的List ,保证线程安全
			if (parentNode.children == null) {
				try {
					lock.lock();
					if (parentNode.children == null) {
						parentNode.children = Collections.synchronizedSet(new HashSet<TreeNode>());
					}
				} finally {
					lock.unlock();
				}
			}

			TreeNode node = new TreeNode(attachment);
			node.parent = parentNode;
			
			return parentNode.children.add(node);
		}
		return false;
	}

	/**
	 * 删除对应节点 只有当节点存在才返回true.
	 * 该方法暂时不提供外部使用。所有数据都要从新生成,然后获取
	 * @param 是否级联删除
	 *            ,如果为true执行级连删除;false,如果有child则不执行删除
	 * */
	protected boolean remove(T attachment, boolean cascade) {
		TreeNode node = findTreeNode(attachment);
		if (node != null) {
			// 如果不是级联删除 ,并且 有子级节,则返回false
			if (!cascade && node.children != null && node.children.size() > 0) {
				return false;
			}
			TreeNode parent = node.parent;
			return parent.children.remove(node);
		} else {
			return false;
		}
	}

	/**
	 * 获取node下所有后代节点
	 */
	public List<T> getDescendants(T attachment) {
		TreeNode node = findTreeNode(attachment);
		if (node != null) {
			List<T> list = new ArrayList<T>();
			Stack<TreeNode> set = new Stack<TreeNode>();
			if(node.children!=null && node.children.size()>0)
			{
				for (TreeNode children : node.children) {
					set.push(children);
				}
			}
			// 开始遍历当前结果下所有 子孙节点
			while (!set.isEmpty()) {
				TreeNode cur = set.pop();
				list.add(cur.attachment);

				if (cur.children != null && cur.children.size() > 0) {
					for (TreeNode children : cur.children) {
						set.push(children);
					}
				}
			}

			return list;
		}
		return null;
	}

	/**
	 * 查询所有父级节点。从root向下排序,第一个是root
	 * */
	public List<T> getAncestors(T attach) {
		TreeNode node = findTreeNode(attach);
		if (node != null && node.parent!=null) {
			List<T> list = new ArrayList<T>();
			TreeNode cur = node.parent;
			while (cur != root && cur != null) {
				list.add(cur.attachment);
				cur = cur.parent;
			}
			//如果是root
			if (cur == root) {
				list.add(root.attachment);
				Collections.reverse(list);
				return list;
			} else {
				return null;
			}
		} else {
			return null;
		}
	}

	/**
	 * 获取子树,不包含孙级节点
	 */
	public List<T> getChild(T attachment) {
		TreeNode node = findTreeNode(attachment);
		if (node != null && node.children!=null) {
			List<T> list = new ArrayList<T>();
			
			for(TreeNode child : node.children)
			{
				list.add(child.attachment);
			}
			return list;
		}
		return null;
		
	}

	/**
	 * 获得父级节点。
	 */
	public T getFather(T attachment) {
		TreeNode node = findTreeNode(attachment);
		if (node != null && node != this.root) {
			return node.parent.attachment;
		}
		return null;
	}
	
	/**
	 * 查找对象,如果存在测返回对象,否则返回null
	 * */
	private TreeNode findTreeNode(T attachment) {

		Stack<TreeNode> set = new Stack<TreeNode>();
		set.push(root);

		// 下面开始遍历tree
		TreeNode cur = root;
		while ((!set.empty()) && attachment != cur.attachment && (!attachment.equals(cur.attachment))) {
			cur = set.pop();
			if (cur.children != null && cur.children.size() > 0) {
				for (TreeNode children : cur.children) {
					set.push(children);
				}
			}
		}

		if (attachment.equals(cur.attachment)) {
			return cur;
		} else {
			return null;
		}
	}
}

 

分享到:
评论

相关推荐

    用Java集合递归实现通用树Tree

    总的来说,使用Java集合和递归实现通用树结构需要理解数据结构的基本原理,熟练掌握Java集合框架,以及掌握递归的概念和应用。通过这个资源,你可以学习到如何在实际项目中构建和操作自定义的树数据结构,为你的编程...

    数据结构通用树tree的实现-可用demo

    在这个"数据结构通用树tree的实现-可用demo"中,我们很可能会找到一个实现树数据结构的代码示例,这对于理解和操作树结构至关重要。 树数据结构具有以下基本概念: 1. **根节点**:树的顶部节点,没有父节点,但...

    通用树形目录生成

    一个用于生成树形目录的工程。需要修改Hibernate的配置信息,并创建一个与数据库表同名的Java Bean类和一个Vo类并继承Vo(类名:数据库表名+Vo) 将代码部署在服务器上后,访问index.jsp,输入类名和分页大小,就...

    Flex通用树结构

    NULL 博文链接:https://yxddevelop.iteye.com/blog/1296576

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

    本主题将深入探讨如何使用Java集合、JSP和JSTL来递归地创建并输出树形结构(Tree),特别是用于前端展示。 首先,我们要理解Java集合在构建树结构中的作用。在Java中,可以使用ArrayList、LinkedList或者自定义的...

    js+css网站通用的树形结构

    在压缩包文件"**d300**"中,可能包含了实现这一通用树形结构的源代码,包括JavaScript文件(可能包含自定义的树形组件实现)和CSS文件(用于定制样式)。具体代码实现细节需查看文件内容以获取更多信息。 总的来说...

    Generic-Tree:通用树下的基本程序

    "Generic-Tree-main"可能是这个压缩包的主要代码文件,包含了通用树的基本操作函数实现,如插入、删除、遍历等。通过阅读和理解这段代码,可以深入学习树数据结构的实现细节和操作技巧。 综上所述,通用树在编程中...

    device_xiaomi_sm8250_common:小米sm8250的通用树

    小米SM8250通用树,正如标题和描述所提及,是为小米基于高通骁龙SM8250处理器的设备定制的一套设备树。骁龙SM8250,也称为骁龙865,是一款高性能的移动处理器,广泛应用于旗舰级智能手机。本文将深入探讨设备树、...

    PowerGrid:使用通用树结构表示电网基础设施的基本系统

    "PowerGrid"项目就是一个基于Java语言的解决方案,它使用通用树结构来表示电网基础设施,旨在提供一种高效、灵活的方式来处理复杂的电网系统。 1. **通用树结构**: 树结构是一种数据组织形式,它反映了层次关系,...

    device_oneplus_sdm845-common:OnePlus 66T设备的通用树

    标题中的"device_oneplus_sdm845-common:OnePlus 66T设备的通用树"指的是OnePlus 66T智能手机的硬件平台抽象层(HAL)代码库,它基于高通骁龙845(SDM845)芯片组。这个通用树包含了与设备驱动、系统配置和优化相关...

    android_device_xiaomi_sm8250-common:适用于Xiaomi SM8250设备的开源软件通用树

    《Xiaomi SM8250设备的开源软件通用树详解》 在移动操作系统的世界里,Android以其开源性吸引了大量的开发者和爱好者。Xiaomi SM8250是一款由小米公司推出的高端智能手机平台,它基于高通骁龙865处理器,提供了强大...

    device_asus_common-X01BD-Enforcing:X01BD的通用树实际上以一种非常不常见的方式起作用....因为它们正在使用新的ZenParts进行强制...对SonalSingh18表示感谢

    接着,“通用树(common-trees)”是设备树概念的一个扩展,它旨在创建一个可跨多个设备复用的共享设备树结构。这样的设计有助于减少代码重复,简化维护,并提高兼容性。对于ASUS设备来说,这意味着这个设备树不仅...

    左孩子右兄弟树的基本实现

    这是数据结构中树的基本实现,用C++实现的,其结构是左孩子右兄弟,里面包括了树的各种操作的类成员函数。

    树-通用树数据结构-Rust开发

    该项目提供了用于通用目的的树的各种实现。 遍历功能树中的每个节点都提供标准的转发i该项目提供了用于一般目的的树的各种实现。 遍历功能树中的每个节点都提供了用于访问其子节点的标准正向迭代器。 可以在递归函数...

    Linux内核红黑树封装的通用红黑树

    通用红黑树 说明: 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树: 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者:rcyh 日期:2011年7月21日 ---------------------------------...

    树结构操作CD代码实现

    通用树结构的基本操作,包含如下操作: 1. 创建树; 2. 销毁树; 3. 清空树; 4. 插入结点; 5. 删除结点; 6. 获取结点; 7. 获取根结点; 8. 获取树的结点数; 9. 获取树的高度; 10. 获取树的度。 11.显示树结构...

    左侧通用js菜单树

    "左侧通用js菜单树"是一个专门设计用于实现这一目标的组件。它通常被用在网站的左侧栏,提供一种清晰、直观的方式来展示多级菜单,帮助用户快速定位到他们需要的信息或功能。这种菜单树设计为天蓝色背景,给人一种...

    如何:使用TreeView控件实现树结构显示及快速查询

    #### 通用树结构的数据结构存储 为了有效地存储和管理树结构数据,我们需要设计一种合理的数据结构。通常,我们会使用带有父节点ID的表格来存储树节点。 **数据表设计:** 1. **表结构:** 设计一张包含ID、Text、...

    数据结构教学课件:chapter6.ppt

    在本章“数据结构教学课件:Chapter6.ppt”中,主要讲解了通用树(General Trees)的相关知识,包括其定义、节点、遍历以及使用父指针实现的树结构,并涉及到了并查集(Union/Find)的操作。 1. 通用树(General ...

    数据结构英文教学课件:16_Trees_04.pdf

    在本教学课件“16_Trees_04”中,主要探讨了树(Tree)与二叉树(Binary Trees)的相关知识,特别是通用树(General Tree)的遍历方法和实现方式。 首先,我们关注的是通用树的遍历。在二叉树中,有三种常见的遍历...

Global site tag (gtag.js) - Google Analytics