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 http://download.csdn.net/source/2864857 新增了jsp页面输出,用jstl递归输出。
一个用于生成树形目录的工程。需要修改Hibernate的配置信息,并创建一个与数据库表同名的Java Bean类和一个Vo类并继承Vo(类名:数据库表名+Vo) 将代码部署在服务器上后,访问index.jsp,输入类名和分页大小,就...
NULL 博文链接:https://yxddevelop.iteye.com/blog/1296576
数据结构、树的实现
不要分,要的是人气!资源很给力的!欢迎下载!
通用树 通用树下的基本程序
通用树枝模式(GTP)扩展了TPQ模型,使其包含与作为XQuery语言一部分的输出节点,可选节点和布尔表达式有关的语义。 预排序过滤整体算法(例如TwigStack)代表了重要的TPQ处理方法类,相对于某些查询类的输入和输出...
这是数据结构中树的基本实现,用C++实现的,其结构是左孩子右兄弟,里面包括了树的各种操作的类成员函数。
电网 基本系统,代表使用通用树结构的电网基础设施。
device_xiaomi_sm8250_common:小米sm8250的通用树
该项目提供了用于通用目的的树的各种实现。 遍历功能树中的每个节点都提供标准的转发i该项目提供了用于一般目的的树的各种实现。 遍历功能树中的每个节点都提供了用于访问其子节点的标准正向迭代器。 可以在递归函数...
节点反馈中时滞较小的通用树中变系数波动方程的指数镇定
通用红黑树 说明: 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树: 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者:rcyh 日期:2011年7月21日 ---------------------------------...
device_oneplus_sdm845-common:OnePlus 66T设备的通用树
通用树结构的基本操作,包含如下操作: 1. 创建树; 2. 销毁树; 3. 清空树; 4. 插入结点; 5. 删除结点; 6. 获取结点; 7. 获取根结点; 8. 获取树的结点数; 9. 获取树的高度; 10. 获取树的度。 11.显示树结构...
树是一种分层数据结构,其中每个节点都只有一个父级(期望根),没有或有几个子级。 随着这种关系结构,每个节点都可以存储任何类型的数据。 这个类使用普通的 MATLAB 语法和数组来实现它。 大多数有用的方法都是...
Ruby树描述: RubyTree是通用 的纯Ruby实现。 它提供了一个基于节点的模型来将命名节点存储在树中,并提供了简单的API来访问,修改和遍历该结构。 实现是以节点为中心的,其中树中的各个节点是主要的结构元素。 支持...
左侧通用js菜单树,天蓝色背景,动态收缩,兼容各种浏览器,实用
小米Redmi 6 Pro(樱花)的设备树规格表特征规格中央处理器八核2.0 GHz Cortex-A53 芯片组高通MSM8953金鱼草625 显卡阿德雷诺506 记忆3/4 GB 搭载Android版本8.1.0 贮存32/64 GB 微型SD 最高256 GB 电池4000 mAh(不...
主要目标是UD(通用依赖关系)树,但是该库却被设计为对于注释方案而言是完全通用的。 UD的简介,与GF的关系以及DBNF可以在手稿中找到 《兰塔语:计算语法:一种语言视角》, : GF转换基于论文中介绍的算法 P ...