精华内容
下载资源
问答
  • JavaScript 实现树结构 (一)JavaScript 实现树结构(一)一, 树结构简介1.1. 简单了解树结构什么是?真实的:的特点:一般都有一个根, 连接着根的是树干...树结构对比于数组 / 链表 / 哈希表有哪些优势呢:数组:优...

    JavaScript 实现树结构 (一)

    JavaScript 实现树结构(一)

    一, 树结构简介

    1.1. 简单了解树结构

    什么是树?

    真实的树:

    ab7653affab982b574eb7acc55df2e04.gif

    树的特点:

    树一般都有一个根, 连接着根的是树干;

    树干会发生分叉, 形成许多树枝, 树枝会继续分化成更小的树枝;

    树枝的最后是叶子;

    现实生活中很多结构都是树的抽象, 模拟的树结构相当于旋转 180° 的树.

    ab7653affab982b574eb7acc55df2e04.gif

    树结构对比于数组 / 链表 / 哈希表有哪些优势呢:

    数组:

    优点: 可以通过下标值访问, 效率高;

    缺点: 查找数据时需要先对数据进行排序, 生成有序数组, 才能提高查找效率; 并且在插入和删除元素时, 需要大量的位移操作;

    链表:

    优点: 数据的插入和删除操作效率都很高;

    缺点: 查找效率低, 需要从头开始依次查找, 直到找到目标数据为止; 当需要在链表中间位置插入或删除数据时, 插入或删除的效率都不高.

    哈希表:

    优点: 哈希表的插入 / 查询 / 删除效率都非常高;

    缺点: 空间利用率不高, 底层使用的数组中很多单元没有被利用; 并且哈希表中的元素是无序的, 不能按照固定顺序遍历哈希表中的元素; 而且不能快速找出哈希表中最大值或最小值这些特殊值.

    树结构:

    优点: 树结构综合了上述三种结构的优点, 同时也弥补了它们存在的缺点(虽然效率不一定都比它们高), 比如树结构中数据都是有序的, 查找效率高; 空间利用率高; 并且可以快速获取最大值和最小值等.

    总的来说: 每种数据结构都有自己特定的应用场景

    树结构:

    树 (Tree): 由 n(n ≥ 0) 个节点构成的有限集合. 当 n = 0 时, 称为空树.

    对于任一棵非空树(n> 0), 它具备以下性质:

    数中有一个称为根 (Root) 的特殊节点, 用 r 表示;

    其余节点可分为 m(m> 0)个互不相交的有限集合 T~1~,T~2~,...,T~m~, 其中每个集合本身又是一棵树, 称为原来树的子树(SubTree).

    树的常用术语:

    ab7653affab982b574eb7acc55df2e04.gif

    节点的度(Degree): 节点的子树个数, 比如节点 B 的度为 2;

    树的度: 树的所有节点中最大的度数, 如上图树的度为 2;

    叶节点(Leaf): 度为 0 的节点(也称为叶子节点), 如上图的 H,I 等;

    父节点(Parent): 度不为 0 的节点称为父节点, 如上图节点 B 是节点 D 和 E 的父节点;

    子节点(Child): 若 B 是 D 的父节点, 那么 D 就是 B 的子节点;

    兄弟节点(Sibling): 具有同一父节点的各节点彼此是兄弟节点, 比如上图的 B 和 C,D 和 E 互为兄弟节点;

    路径和路径长度: 路径指的是一个节点到另一节点的通道, 路径所包含边的个数称为路径长度, 比如 A->H 的路径长度为 3;

    节点的层次(Level): 规定根节点在 1 层, 其他任一节点的层数是其父节点的层数加 1. 如 B 和 C 节点的层次为 2;

    树的深度(Depth): 树种所有节点中的最大层次是这棵树的深度, 如上图树的深度为 4;

    1.2. 树结构的表示方式

    最普通的表示方法:

    ab7653affab982b574eb7acc55df2e04.gif

    如图, 树结构的组成方式类似于链表, 都是由一个个节点连接构成. 不过, 根据每个父节点子节点数量的不同, 每一个父节点需要的引用数量也不同. 比如节点 A 需要 3 个引用, 分别指向子节点 B,C,D;B 节点需要 2 个引用, 分别指向子节点 E 和 F;K 节点由于没有子节点, 所以不需要引用.

    这种方法缺点在于我们无法确定某一结点的引用数.

    儿子 - 兄弟表示法:

    ab7653affab982b574eb7acc55df2e04.gif

    这种表示方法可以完整地记录每个节点的数据, 比如:// 节点 A

    Node{

    // 存储数据

    this.data=data

    // 统一只记录左边的子节点

    this.leftChild=B

    // 统一只记录右边的第一个兄弟节点

    this.rightSibling=null

    }

    // 节点 B

    Node{

    this.data=data

    this.leftChild=E

    this.rightSibling=C

    }

    // 节点 F

    Node{

    this.data=data

    this.leftChild=null

    this.rightSibling=null

    }

    这种表示法的优点在于每一个节点中引用的数量都是确定的.

    儿子 - 兄弟表示法旋转

    以下为儿子 - 兄弟表示法组成的树结构:

    ab7653affab982b574eb7acc55df2e04.gif

    将其顺时针旋转 45° 之后:

    ab7653affab982b574eb7acc55df2e04.gif

    这样就成为了一棵二叉树, 由此我们可以得出结论: 任何树都可以通过二叉树进行模拟. 但是这样父节点不是变了吗? 其实, 父节点的设置只是为了方便指向子节点, 在代码实现中谁是父节点并没有关系, 只要能正确找到对应节点即可.

    二, 二叉树

    2.1. 二叉树简介

    二叉树的概念: 如果树中的每一个节点最多只能由两个子节点, 这样的树就称为二叉树;

    二叉树十分重要, 不仅仅是因为简单, 更是因为几乎所有的树都可以表示成二叉树形式.

    二叉树的组成:

    二叉树可以为空, 也就是没有节点;

    若二叉树不为空, 则它由根节点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成;

    二叉树的五种形态:

    ab7653affab982b574eb7acc55df2e04.gif

    上图分别表示: 空的二叉树, 只有一个节点的二叉树, 只有左子树 TL 的二叉树, 只有右子树 TR 的二叉树和有左右两个子树的二叉树.

    二叉树的特性:

    一个二叉树的第 i 层的最大节点树为: 2^(i-1)^,i>= 1;

    深度为 k 的二叉树的最大节点总数为: 2^k^ - 1 ,k>= 1;

    对任何非空二叉树, 若 n~0~ 表示叶子节点的个数, n~2~ 表示度为 2 的非叶子节点个数, 那么两者满足关系: n~0~ = n~2~ + 1; 如下图所示: H,E,I,J,G 为叶子节点, 总数为 5;A,B,C,F 为度为 2 的非叶子节点, 总数为 4; 满足 n~0~ = n~2~ + 1 的规律.

    ab7653affab982b574eb7acc55df2e04.gif

    2.2. 特殊的二叉树

    完美二叉树

    完美二叉树 (Perfect Binary Tree) 也成为满二叉树(Full Binary Tree), 在二叉树中, 除了最下一层的叶子节点外, 每层节点都有 2 个子节点, 这就构成了完美二叉树.

    ab7653affab982b574eb7acc55df2e04.gif

    完全二叉树

    完全二叉树(Complete Binary Tree):

    除了二叉树最后一层外, 其他各层的节点数都达到了最大值;

    并且, 最后一层的叶子节点从左向右是连续存在, 只缺失右侧若干叶子节点;

    完美二叉树是特殊的完全二叉树;

    ab7653affab982b574eb7acc55df2e04.gif

    在上图中, 由于 H 缺失了右子节点, 所以它不是完全二叉树.

    2.3. 二叉树的数据存储

    常见的二叉树存储方式为数组和链表:

    使用数组:

    完全二叉树: 按从上到下, 从左到右的方式存储数据.

    ab7653affab982b574eb7acc55df2e04.gif节点ABCDEFGH序号12345678

    使用数组存储时, 取数据的时候也十分方便: 左子节点的序号等于父节点序号 * 2, 右子节点的序号等于父节点序号 * 2 + 1 .

    非完全二叉树: 非完全二叉树需要转换成完全二叉树才能按照上面的方案存储, 这样会浪费很大的存储空间.

    ab7653affab982b574eb7acc55df2e04.gif节点ABC^^F^^^^^^M序号12345678910111213

    使用链表

    二叉树最常见的存储方式为链表: 每一个节点封装成一个 Node,Node 中包含存储的数据, 左节点的引用和右节点的引用.

    ab7653affab982b574eb7acc55df2e04.gif

    三, 二叉搜索树

    3.1. 认识二叉搜索树

    二叉搜索树(BST,Binary Search Tree), 也称为二叉排序树和二叉查找树.

    二叉搜索树是一棵二叉树, 可以为空;

    如果不为空, 则满足以下性质:

    条件 1: 非空左子树的所有键值小于其根节点的键值. 比如三中节点 6 的所有非空左子树的键值都小于 6;

    条件 2: 非空右子树的所有键值大于其根节点的键值; 比如三中节点 6 的所有非空右子树的键值都大于 6;

    条件 3: 左, 右子树本身也都是二叉搜索树;

    ab7653affab982b574eb7acc55df2e04.gif

    如上图所示, 树二和树三符合 3 个条件属于二叉树, 树一不满足条件 3 所以不是二叉树.

    总结: 二叉搜索树的特点主要是较小的值总是保存在左节点上, 相对较大的值总是保存在右节点上. 这种特点使得二叉搜索树的查询效率非常高, 这也就是二叉搜索树中 "搜索" 的来源.

    3.2. 二叉搜索树应用举例

    下面是一个二叉搜索树:

    ab7653affab982b574eb7acc55df2e04.gif

    若想在其中查找数据 10, 只需要查找 4 次, 查找效率非常高.

    第 1 次: 将 10 与根节点 9 进行比较, 由于 10> 9, 所以 10 下一步与根节点 9 的右子节点 13 比较;

    第 2 次: 由于 10 < 13, 所以 10 下一步与父节点 13 的左子节点 11 比较;

    第 3 次: 由于 10 < 11, 所以 10 下一步与父节点 11 的左子节点 10 比较;

    第 4 次: 由于 10 = 10, 最终查找到数据 10 .

    ab7653affab982b574eb7acc55df2e04.gif

    同样是 15 个数据, 在排序好的数组中查询数据 10, 需要查询 10 次:

    ab7653affab982b574eb7acc55df2e04.gif

    其实: 如果是排序好的数组, 可以通过二分查找: 第一次找 9, 第二次找 13, 第三次找 15.... 我们发现如果把每次二分的数据拿出来以树的形式表示的话就是二叉搜索树. 这就是数组二分法查找效率之所以高的原因.

    参考资料: JavaScript 数据结构与算法

    来源: https://www.cnblogs.com/AhuntSun-blog/p/12446656.html

    展开全文
  • 十多年来,NAS中已经存在的目录和文件达到10亿之多,在设计和开发备份系统的过程中碰到了很多挑战,本文将分享大量文件名记录的树形结构存储实践。 一、引言 既然是定期备份,肯定会1次以上的备份。对于一个特定...

    十多年来,NAS中已经存在的目录和文件达到10亿之多,在设计和开发备份系统的过程中碰到了很多挑战,本文将分享大量文件名记录的树形结构存储实践。

    一、引言

    既然是定期备份,肯定会有1次以上的备份。对于一个特定目录,每次备份时都要与上次备份时进行比较,以期找出哪些文件被删除了,又新增了哪些文件,这就需要每次备份时把该目录下的所有文件名进行保存。我们首先想到的是把所有文件名用特定字符进行拼接后保存。由于我们使用了MySQL保存这些信息,当目录下文件很多时,这种拼接的方式很可能超出MySQL的Blob长度限制。根据经验,当一个目录有大量文件时,这些文件的名称往往是程序生成的,有一定规律的,而且开头一般是重复的,于是我们想到了使用一种树形结构来进行存储。

    例如,一个有abc、abc1、ad、cde 4个文件的目录对应的树如图1所示。

    图1 树形结构示例

    图1中,R表示根节点,青色节点我们称为结束节点,从R到每个结束节点的路径都表示一个文件名。可以在树中查找是否含有某个文件名、遍历树中所有的文件名、对树序列化进行保存、由序列化结果反序列化重新生成树。

    二、涉及的数据结构

    注意:我们使用java编写,文中涉及语言特性相关的知识点都是指java。

    2.1 Node的结构

    包括根节点在内的每个节点都使用Node类来表示。代码如下:

        class Node {
            private char value;
            private Node[]children = new Node[0];
            private byte end = 0;
        }
    

    字段说明:

    • value:该节点表示的字符,当Node表示根节点时,value无值。
    • children:该节点的所有子节点,初始化为长度为0的数组。
    • end:标记节点是否是结束节点。0不是;1是。叶子节点肯定是结束节点。默认非结束节点。

    2.2 Node的操作

        public Node(char v);
        public Node findChild(char v);
        public Node addChild(char v);
    

    操作说明:

    • Node:构造方法。将参数v赋值给this.value。
    • findChild:查找children中是否含有value为v的子节点。有则返回子节点,没有则返回null。
    • addChild:首先查找children中是否已经含有value为v的子节点,如果有则直接将查到的子节点返回;否则创建value为v的节点,将children的长度延长1,将新创建的节点作为children的最后一个元素,并返回新创建的节点。

    2.3 Tree的结构

        class Tree {
            public Node root = new Node();
        }
    

    字段说明:Tree只含有root Node。如前所述,root的value无值,end为0。初始时的children长度为0。

    2.4 Tree的操作

        public void addName(String name) ;
        public boolean contain(String name);
        public Found next(Found found);
        public void writeTo(OutputStream out);
        public static Tree readFrom(InputStream in);
    

    操作说明:

    • addName:向树中增加一个新的文件名,即参数name。以root为起点,name中的每个字符作参数调用addChild,返回值又作为新的起点,直到name中的全部字符添加完毕,对最后一次调用addChild的返回值标记为结束节点。
    • contain:查询树中是否含有一个文件名。
    • next:对树中包含的所有文件名进行遍历,为了使遍历能够顺利进行,我们引入了新的类Found,细节会在后文详述。
    • writeTo:将树写入一个输出流以进行持久化。
    • readFrom:此方法是静态方法。从一个输入流来重新构建树。

    三、树的构建

    在新建的Tree上调用addName方法,将所有文件名添加到树中,树构建完成。仍然以含有abc、abc1、ad、cde 四个文件的目录为例,对树的构建进行图示。

    图2 树的构建过程

    图2中,橙色节点表示需要在该节点上调用addChild方法增加子节点,同时addChild的返回值作为新的橙色节点。直到没有子节点需要增加时,把最后的橙色节点标记为结束节点。

    四、树的查询

    查找树中是否含有一个某个文件名,对应Tree的contain方法。在图2中的结果上分别查找ef、ab和abc三个文件来演示查找的过程。如图3所示。

    图3 树的查询示意图

    图3中,橙色节点表示需要在该节点上调用findChild方法查找子节点。

    五、树的遍历

    此处的遍历不同于一般树的遍历。一般遍历是遍历树中的节点,而此处的遍历是遍历根节点到所有结束节点的路径。

    我们采用从左到右、由浅及深的顺序进行遍历。我们引入了Found类,并作为next方法的参数进行遍历。

    5.1 Found的结构

        class Found {    
            private String name;
            private int[] idx ;
        }
    

    为了更加容易的说明问题,在图1基础上进行了小小的改造,每个节点的右下角增加了下标,如图4。

    图4 带下标的Tree

    对于abc这个文件名,Found中的name值为“abc”,idx为{0,0,0}。

    对于abc1这个文件名,Found中的name值为“abc1”,idx为{0,0,0,0}。

    对于ad这个文件名,Found中的name值为“ad”,idx为{0,1}。

    对于cde这个文件名,Found中的name值为“cde”,idx为{1,0,0}。

    5.2 如何遍历

    对于图4而言,第一次调用next方法应传入null,则返回第一个结果,即abc代表的Found;继续以这个Found作为参数进行第二次next的调用,则返回第二个结果,即abc1代表的Found;再继续以这个Found作为参数进行第三次next的调用,则返回第三个结果,即ad所代表的Found;再继续以这个Found作为参数进行第四次next的调用,则返回第四个结果,即cde所代表的Found;再继续以这个Found作为参数进行第五次调用,则返回null,遍历结束。

    六、序列化与反序列化

    6.1 序列化

    首先应该明确每个节点序列化后应该包含3个信息:节点的value、节点的children数量和节点是否为结束节点。

    6.1.1 节点的value

    虽然之前所举的例子中节点的value都是英文字符,但实际上文件名中可能含有汉字或者其他语言的字符。为了方便处理,我们没有使用变长编码。而是直接使用unicode码。字节序采用大端编码。

    6.1.2 节点的children数量

    由于节点的value使用了unicode码,所以children的数量不会多于unicode能表示的字符的数量,即65536。children数量使用2个字节。字节序同样采用大端编码。

    6.1.3 节点的end

    0或1可以使用1位(1bit)来表示,但java中最小单位是字节。如果采用1个字节来表示end,有些浪费空间,其实任何一个节点children数量达到65536/2的可能性都是极小的,因此我们考虑借用children数量的最高位来表示end。

    综上所述,一个节点序列化后占用4个字节,以图4中的根节点、value为b的节点和value为e的节点为例:

    表1 Node序列化示例

    value的unicode children数量 end children数量/(end<<15) 最终结果
    根节点 0x0000 2 0 0x0002 0x00020000
    b节点 0x0062 1 0 0x0001 0x00010062
    e节点 0x0065 0 1 0x8000 0x80000065

    6.1.4 树的序列化过程

    对树进行广度遍历,在遍历过程中需要借助队列,以图4的序列化为例进行说明:

    图5 对图4的序列化过程

    6.2 反序列化

    反序列化是序列化的逆过程,由于篇幅原因不再进行阐述。值得一提的是,反序列化过程同样需要队列的协助。

    七、讨论

    7.1 关于节省空间

    为方便讨论,假设目录下的文件名是10个阿拉伯数字的全排列,当位数为1时,目录下含有10个文件,即0、1、2……8、9,当位数为2时,目录下含有100个文件,即00、01、02……97、98、99,以此类推。

    比较2种方法,一种使用“/”分隔,另一种是本文介绍的方法。

    表2 2种方法的存储空间比较(单位:字节)

    位数 方法 1 2 3 4 5 6
    “/”分隔 19 299 3999 49999 599999 6999999
    Tree 44 444 4444 44444 444444 4444444

    由表2可见,当位数为4时,使用Tree的方式开始节省空间,位数越多节省的比例越高,这正是我们所需要的。

    表中,使用“/”分隔时,字节数占用是按照utf8编码计算的。如果直接使用unicode进行存储,占用空间会加倍,那么会在位数为2时就开始节省空间。同样使用“/”分隔,看起来utf8比使用unicode会更省空间,但实际上,文件名中有时候会含有汉字,汉字的utf8编码占用3个字节。

    7.2 关于时间

    在树的构建、序列化反序列化过程中,引入了额外的运算,根据我们的实践,user CPU并没有明显变化。

    7.3 关于理想化假设

    最初我们就是使用了“/”分隔的方法对文件名进行存储,并且数据库的相应字段类型是Blob(Blob的最大值是65K)。在测试阶段就发现,超出65K是一件很平常的事情。在不可能预先统计最大目录里所有文件名拼接后的大小的情况下,我们采取了2种手段,一是使用LongBlob类型,另一种就是尽量减小拼接结果的大小,即本文介绍的方法。

    即使使用树形结构来存储文件名,也不能够保证最终结果不超出4G(LongBlob类型的最大值),至少在我们实践的过程并未出现问题,如果真出现这种情况,只能做特殊处理了。

    7.4 关于其他压缩方法

    把文件名使用“/”拼接后,使用gzip等压缩算法对拼接结果进行压缩后再存储,在节省存储空间方面会取得更好的效果。但是在压缩之前,拼接结果存在于内存,这样对JVM的堆内存有比较高的要求;另外,使用“/”拼接时,查找会比较麻烦。

    作者:牛宁昌

    来源:宜信技术学院

    转载于:https://my.oschina.net/u/4007037/blog/3065510

    展开全文
  • 阅读原文请访问我的博客BrightLoong's Blog 之前在项目需要实现一个功能——将xml文件映射成实体,然后对映射的实体进行...当映射成对应的实体school和student的时候,我们需要知道“school-one”下面有哪些学生,“...

    阅读原文请访问我的博客BrightLoong's Blog

    之前在项目需要实现一个功能——将xml文件映射成实体,然后对映射的实体进行逻辑处理,最后保存到数据库中;由于xml结构的数据是结构化的数据,所以需要保证保存的数据具有正确的主外键关联。如下所示,是一个需要保存到数据库的xml文件。当映射成对应的实体school和student的时候,我们需要知道“school-one”下面有哪些学生,“school-two”下面有哪些学生,这个时候想到了使用树形结构来保存实体,让实体之间依然存在关联关系。

    <school-inf>
      <msg>2017-10-1XX省学校信息总汇</msg>
      <schools>
        <school>
          <name>school-one</name>
          <students>
            <student>Jack</student>
            <student>Rose</student>
            <student>Jon</student>
          </students>
        </school>
        <school>
          <name>school-two</name>
          <students>
            <student>Bob</student>
            <student>Alisa</student>
            </students>
          </school>
        </schools>
    </school-inf>
    复制代码

    树形工具

    以下是树形工具类的实现,包含了树形节点类和树形结构类,由于代码中注释已经比较全面,所以不做过多的说明。

    树形节点类BeanTreeNode.java

    每一个节点对应一个实体,节点包含了实体信息,为了保证实体之间的关联关系,需要留有父节点信息,所有的子节点信息。由此推断出,节点的主要成员有

    • 父节点信息
    • 所有子节点信息
    • 当前实体信息

    为了方便操作,我还多增加了id和pid(parent id),以及节点类型(nodeType)。对id的相关操作我并没有添加,如果需要可以自行添加。

    import java.util.ArrayList;
    import java.util.List;
    import java.util.UUID;
    
    /**
     * 实体树形结构点
     * BeanTreeNode
     * @author BrightLoong
     * @version 1.0
     *
     */
    public class BeanTreeNode {
        
        /**标识id*/
        private String id;
        
        /**父id标识,为了方便获取冗余出来*/
        private String pid;
        
        /**父节点*/
        private BeanTreeNode parentNode;
        
        /**节点类型*/
        private String nodeType;
        
        /**节点值*/
        private Object bean;
        
        /**子节点*/
        private List<BeanTreeNode> childNodes;
        
    
        /**
         * @param parentNode
         * @param nodeType
         * @param bean
         * @param childNodes
         */
        public BeanTreeNode(BeanTreeNode parentNode, String nodeType, Object bean) {
            this.parentNode = parentNode;
            this.nodeType = nodeType;
            this.bean = bean;
            this.childNodes = new ArrayList<BeanTreeNode>();
            this.id = UUID.randomUUID().toString().replaceAll("-", "");
            if (parentNode != null) {
                this.pid = parentNode.getId();
            }
        }
    
        /**
         * @return the nodeType
         */
        public String getNodeType() {
            return nodeType;
        }
    
        /**
         * @param nodeType the nodeType to set
         */
        public void setNodeType(String nodeType) {
            this.nodeType = nodeType;
        }
    
        /**
         * @return the parentNode
         */
        public BeanTreeNode getParentNode() {
            return parentNode;
        }
    
        /**
         * @param parentNode the parentNode to set
         */
        public void setParentNode(BeanTreeNode parentNode) {
            this.parentNode = parentNode;
        }
    
        /**
         * @return the bean
         */
        public Object getBean() {
            return bean;
        }
    
        /**
         * @param bean the bean to set
         */
        public void setBean(Object bean) {
            this.bean = bean;
        }
    
        /**
         * @return the childNodes
         */
        public List<BeanTreeNode> getChildNodes() {
            return childNodes;
        }
    
        /**
         * @param childNodes the childNodes to set
         */
        public void setChildNodes(List<BeanTreeNode> childNodes) {
            this.childNodes = childNodes;
        }
    
        /**
         * @return the id
         */
        public String getId() {
            return id;
        }
    
        /**
         * @param id the id to set
         */
        public void setId(String id) {
            this.id = id;
        }
    
        /**
         * @return the pid
         */
        public String getPid() {
            return pid;
        }
    
        /**
         * @param pid the pid to set
         */
        public void setPid(String pid) {
            this.pid = pid;
        }
        
        /**
         * 是否具有子节点
         * @return true or false
         */
        public boolean haveChild() {
            return !CollectionUtils.isEmpty(childNodes);
        }
    }
    复制代码

    树形结构类BeanTree.java

    BeanTree.java里面包含了如下的一些常用操作:

    • 返回根节点
    • 返回最后添加节点
    • 判断是否具有子节点
    • 添加节点
    • 移动节点到其他节点下
    • 获取对应nodeType的所有节点或实体
    • 根据实体获取节点
    • 获取父节点
    • 转化为map结构

    代码如下

    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    import org.apache.commons.collections.CollectionUtils;
    
    /**
     * 实体树形结构
     * BeanTree
     * @author BrightLoong
     * @version 1.0
     *
     */
    public class BeanTree {
        /**根节点*/
        private BeanTreeNode root;
        
        /**
         * 最新添加的节点
         */
        private BeanTreeNode currentNode;
        
        
        /**
         * @return the currentNode
         */
        public BeanTreeNode getCurrentNode() {
            return currentNode;
        }
    
        /**
         * @return the root
         */
        public BeanTreeNode getRoot() {
            return root;
        }
        
        /**
         * 判断节点是否有子节点.
         * @param node 要判断的节点
         * @return true or false
         */
        public boolean haveChild(BeanTreeNode node) {
            return CollectionUtils.isEmpty(node.getChildNodes());
        }
        
        /**
         * 在父节点上面添加节点,并返回天添加的节点.
         * @param parentNode 父节点
         * @param bean 要添加的bean
         * @param nodeType 节点类型
         * @return 返回包含bean的节点
         */
        public BeanTreeNode addNode(BeanTreeNode parentNode, Object bean, String nodeType) {
            BeanTreeNode node;
            if (bean == null) {
                return null;
            }
            //如果没有父节点说明为root根节点
            if (parentNode == null) {
                node = root = new BeanTreeNode(null, nodeType, bean);
            } else {
                //创建子节点,并添加到父节点上
                node = new BeanTreeNode(parentNode, nodeType, bean);
                parentNode.getChildNodes().add(node);
            }
            currentNode = node;
            return node;
        }
        
        /**
         * 将当期bean-sBean,以及sBean下的子Bean,挂到dBean下
         * @param sBean 源Bean
         * @param dBean 目的父Bean
         */
        public void removeTo(Object sBean, Object dBean) {
            BeanTreeNode sNode = getNodeByBean(sBean);
            BeanTreeNode dNode = getNodeByBean(dBean);
            removeTo(sNode, dNode);
        }
        
        /**
         * 将当期node-sNode,以及sNode下的子Node,挂到dNode下
         * @param sNode 源node
         * @param dNode 目的父node
         */
        public void removeTo(BeanTreeNode sNode, BeanTreeNode dNode) {
            //从当前父节点移除sNode
            sNode.getParentNode().getChildNodes().remove(sNode);
            //将sNode移到dNode下
            dNode.getChildNodes().add(sNode);
            //修改sNode的父Id和父节点
            sNode.setPid(dNode.getId());
            sNode.setParentNode(dNode);
        }
        
        /**
         * 获取父bean.
         * @param bean 子bean
         * @return 返回父bean
         */
        public Object getParentBean(Object bean) {
            return getNodeByBean(bean).getParentNode().getBean();
        }
        
        /**
         * 根据传入的bean获取bean下面对应类型的子bean.
         * @param bean 当前bean
         * @param nodeType 节点类型
         * @return 子bean的集合
         */
        public List<Object> getBeanListByBeanAndNodeType(Object bean, String nodeType) {
            BeanTreeNode node = getNodeByBean(bean);
            return getBeanListByNodeType(node, nodeType);
        }
        
        /**
         * 根据传入的bean获取包含bean的Node节点
         * @param node 当前node
         * @param bean 要查找的bean
         * @return node节点
         */
        public BeanTreeNode getNodeByBean(BeanTreeNode node, Object bean) {
            BeanTreeNode resultNode = null;
            if (node.getBean().equals(bean)) {
                resultNode = node;
                return resultNode;
            } else {
                for (BeanTreeNode tempNode : node.getChildNodes()) {
                    resultNode = getNodeByBean(tempNode, bean);
                    if (resultNode != null) {
                        break;
                    }
                }
            }
            return resultNode;
        }
        
        /**
         * 根据传入的bean获取root节点下包含bean的Node节点
         * @param bean 要查找的bean
         * @return node节点
         */
        public BeanTreeNode getNodeByBean(Object bean) {
            return getNodeByBean(root, bean);
        }
        
        /**
         * 根据节点类型返回当前节点下对应节点类型的bean的list集合.
         * 默认如果当前节点满足类型,那么当前节点不会存在相同类型的子节点
         * @param node 当前节点
         * @param nodeType 节点类型
         * @return
         */
        @SuppressWarnings("unchecked")
        public <T> List<T> getBeanListByNodeType(BeanTreeNode node, String nodeType) {
            List<T> beanList = new ArrayList<T>();
            if (node.getNodeType().equals(nodeType)) {
                beanList.add((T)node.getBean());
            } else {
                for (BeanTreeNode tempNode : node.getChildNodes()) {
                    beanList.addAll((Collection<? extends T>) getBeanListByNodeType(tempNode, nodeType));
                }
            }
            return beanList;
        }
        /**
         * 根据节点类型返回根节点下对应节点类型的bean的list集合.
         * @param nodeType 节点类型
         * @return
         */
        public <T> List<T> getBeanListByNodeType(String nodeType) {
            return getBeanListByNodeType(root, nodeType);
        }
        
        /**
         * 从root节点开始获取对应nodeType的node.
         * @param nodeType 节点类型
         * @return nodeType类型的节点集合
         */
        public List<BeanTreeNode> getNodeListByNodeType(String nodeType) {
            return getNodeListByNodeType(root, nodeType);
        }
        
        /**
         * 从node节点开始获取对应nodeType的node.
         * @param node node节点
         * @param nodeType 节点类型
         * @return nodeType类型的节点集合
         */
        public List<BeanTreeNode> getNodeListByNodeType(BeanTreeNode node, String nodeType) {
            List<BeanTreeNode> nodeList = new ArrayList<BeanTreeNode>();
            if(node==null){
                return nodeList;  
            }
            if (nodeType.equals(node.getNodeType())) {
                nodeList.add(node);
            } else {
                for (BeanTreeNode tempNode : node.getChildNodes()) {
                    nodeList.addAll(getNodeListByNodeType(tempNode, nodeType));  
                }
            }
            
            return nodeList;
        }
        
        /**
         * 将树形结构转化为map.
         * @return
         */
        public Map<String, List<Object>> toMap() {
            return toMap(root);
        }
        
        /**
         * 将对应节点及其子节点转化为map.
         * @param node 树节点
         * @return 转化后的map
         */
        public Map<String, List<Object>> toMap(BeanTreeNode node) {
            Map<String, List<Object>> map = new HashMap<String, List<Object>>();
            toMap(node, map);
            return map;
        }
        
        
        /**
         * 根据传入的nodeType删除对应的节点以及其所有子节点.
         * @param nodeType
         */
        public void delNodeByNodeType(String nodeType) {
            delNodeByNodeType(root, nodeType);
        }
        
        /**
         * 删除node节点下,类型为nodeType的节点和所有子节点
         * @param node
         * @param nodeType
         */
        public void delNodeByNodeType(BeanTreeNode node, String nodeType) {
            List<BeanTreeNode> nodeList = getNodeListByNodeType(node, nodeType);
            for (BeanTreeNode beanTreeNode : nodeList) {
                beanTreeNode.getParentNode().getChildNodes().remove(beanTreeNode);
            }
        }
        
        /**
         * 从树结构里面删除bean和相关node.
         * @param bean bean
         */
        public void delNodeByBean(Object bean) {
            BeanTreeNode node = getNodeByBean(bean);
            BeanTreeNode parentNode = node.getParentNode();
            List<BeanTreeNode> childNodes = parentNode.getChildNodes();
            Iterator<BeanTreeNode> it = childNodes.iterator();
            while (it.hasNext()) {
                BeanTreeNode beanTreeNode = it.next();
                if (node == beanTreeNode) {
                    it.remove();
                }
            }
        }
        
        
        /**
         * 根据class返回对应的beanList.
         * @param cls class
         * @return beanList
         */
        public <T> List<Object> getBeanListByClass(Class<T> cls) {
            return getBeanListByClass(root, cls);
        }
        
        /**
         * 根据class返回对应的beanList.
         * @param node 节点
         * @param cls class
         * @return beanList
         */
        public <T> List<Object> getBeanListByClass(BeanTreeNode node, Class<T> cls) {
            List<Object> beanList = new ArrayList<Object>();
            Object bean = node.getBean();
            if (cls.isAssignableFrom(bean.getClass())) {
                beanList.add(bean);
            }
            List<BeanTreeNode> childNodes = node.getChildNodes();
            for (BeanTreeNode beanTreeNode : childNodes) {
                beanList.addAll(getBeanListByClass(beanTreeNode, cls));
            }
            return beanList;
        }
        
        
        /**
         * 将对应节点及其子节点转化为map.
         * @param node 树节点
         * @param map 用来保存结果的map
         */
        private void toMap(BeanTreeNode node, Map<String, List<Object>> map) {
            String key = node.getNodeType();
            Object bean = node.getBean();
            if (map.containsKey(key)) {
                map.get(key).add(bean);
            } else {
                List<Object> list = new ArrayList<Object>();
                list.add(bean);
                map.put(key, list);
            }
            for (BeanTreeNode tempNode : node.getChildNodes()) {
                toMap(tempNode, map);
            }
        }
    }
    复制代码

    测试树形工具

    使用上面的xml进行测试,这里就不再做xml映射,假设存在上面xml所示的所有实体,“school-one”和“school-two”以及5个student,看看能否构造出想要的结构,测试类代码如下。

    class SchoolInf {
        private String msg;
        public SchoolInf(String msg) {
            this.msg = msg;
        }
    }
    
    class Student {
        private String name;
        public Student(String name) {
            this.name = name;
        }
    }
    
    class School {
        private String name;
        public School(String name) {
            this.name = name;
        }
    }
    
    public class Test {
        public static void main(String[] args) {
            SchoolInf schoolInf = new SchoolInf("2017-10-1XX省学校信息总汇");
            School school_one = new School("school-one");
            School school_two = new School("school-two");
            Student Jack = new Student("Jack");
            Student Rose = new Student("Rose");
            Student Jon = new Student("Jon");
            Student Bob = new Student("Bob");
            Student Alisa = new Student("Alisa");
            
            BeanTree tree = new BeanTree();
            BeanTreeNode root = tree.addNode(null, schoolInf, "root");
            BeanTreeNode school_node1 = tree.addNode(root, school_one, "school");
            BeanTreeNode school_node2 = tree.addNode(root, school_two, "school");
            tree.addNode(school_node1, Jack, "root");
            tree.addNode(school_node1, Rose, "root");
            tree.addNode(school_node1, Jon, "root");
            tree.addNode(school_node2, Bob, "root");
            tree.addNode(school_node2, Alisa, "root");
            
            System.out.println("end");
        }
    }
    
    复制代码

    我们通过调试观察树结构变量“tree”的值如下:

    可以看出来能够构造出正确的结构,BeanTree中其他的一些方法这里就不在一一测试了。

    更新记录

    • 2018/1/10,在BeanTree中添加更多的操作方法。

    转载于:https://juejin.im/post/5add8ea8518825670e5cab3f

    展开全文
  • 简单搜了一下没有合适的,只找到一个基础的瑕疵的树形结构,就在基础上改了增加了复选框以及简化了部分代码。下面上演示效果图,时长25秒,手机卡见谅。 复选框两种设计模式: 1、子节点选中则父节点选中,适合...
  • 简单搜了一下没有合适的,只找到一个基础的瑕疵的树形结构,就在基础上改了增加了复选框以及简化了部分代码,。下面上演示效果图,时长25秒,手机卡见谅。 复选框两种设计模式: 1、子节点选中则父节点选中...

    之前做项目的时候做人员组织架构时候需要用到,同样可以用于目录视图。简单搜了一下没有合适的,只找到一个基础的有瑕疵的树形结构,就在基础上改了增加了复选框以及简化了部分代码,。下面上演示效果图,时长25秒,手机卡见谅。

    复选框有两种设计模式:

    1、子节点选中则父节点选中,适合多级多item下方便了解哪些被选中;

    2、子节点全部选中父节点才选中,更符合日常逻辑,适合少数量以及少层级。

    下面上主要代码:

    首先上MainActivity,主要作用上加载layout以及读取数据。实际中一般从数据库获取。命名较为随意请见谅。

    public class MainActivity extends AppCompatActivity {
    
        List<Node> list = new ArrayList<Node>();
        private TreeListView listView;
        private RelativeLayout relativeLayout, rl;
    
        @Override
        protected void onCreate(Bundle savedInstanceState) {
            super.onCreate(savedInstanceState);
            setContentView(R.layout.activity_main);
            relativeLayout = (RelativeLayout) findViewById(R.id.main_relative_layout);
            Context context=MainActivity.this;
            rl = new RelativeLayout(context);
            rl.setLayoutParams(new RelativeLayout.LayoutParams(RelativeLayout.LayoutParams.MATCH_PARENT, RelativeLayout.LayoutParams.MATCH_PARENT));
            listView = new TreeListView(context, initNodeTree());
            listView.setLayoutParams(new RelativeLayout.LayoutParams(RelativeLayout.LayoutParams.MATCH_PARENT, RelativeLayout.LayoutParams.MATCH_PARENT));
            relativeLayout.addView(listView);
        }
        public List<Node> initNodeTree() {
    
            List<Node> member_list =new ArrayList<Node>();
    //        -1表示为根节点,id的作用为标识对象身份,第三个参数此例子中是text文本
            member_list.add(new Node("" + -1, "1" , "111"));
            member_list.add(new Node(""+1 , "2" , "222"));
            member_list.add(new Node("" + -1, "3" , "333"));
            member_list.add(new Node("" + 1, "4" , "444"));
            member_list.add(new Node("" + 4, "5" , "555"));
            member_list.add(new Node("" + 4, "6" , "666"));
            member_list.add(new Node("" + 4, "7" , "777"));
            member_list.add(new Node("" + 7, "8" , "888"));
            member_list.add(new Node("" + 8, "9" , "999"));
            member_list.add(new Node("" + 8, "10" , "101010"));
            list.addAll(member_list);
            return list;
        }
    }

     

    接下来是Node类:

    Node对象当前主要有父节点Id,自身id以及值组成,自身id自加,父节点id,使用过程中根据实际使用增加成员属性。比如作为组织架构,标识为人名还是一个空的部门,当前对象为第几层级等等,以及从数据库中获取时候直接设置默认选中。

    public class Node implements Serializable {
    	private Node parent = null; // 父节点
    	private List<Node> childrens = new ArrayList<Node>();//子节点
    	private String value;//节点显示值
    	private boolean isChecked = false; //是否被选中
    	private boolean isExpand = true;//是否处于扩展状态
    	private boolean hasCheckBox = true;//是否有复选框
    	private String parentId = null;
    	private String curId = null;
    
    
    	//父节点集合
    	private List<Node> parents = new ArrayList<>();
    
    	/**
    	 * 设置节点值
    	 *
    	 * @param parentId
    	 *            TODO
    	 * @param curId
    	 *            TODO
    	 */
    	public Node( String parentId, String curId, String value) {
    		// TODO Auto-generated constructor stub
    
    		this.value = value;
    		this.parentId = parentId;
    		this.curId = curId;
    
    	}
    
    	public List<Node> getParents() {
    		return parents;
    	}
    
    	public void setParents(Node node) {
    		if(node != null) {
    			if (!parents.contains(node)) {
    				parents.add(node);
    			}
    		}
    	}
    
    	/**
    	 * 得到父节点
    	 */
    	public Node getParent() {
    		return parent;
    	}
    	/**
    	 * 设置父节点
    	 * @param parent
    	 */
    	public void setParent(Node parent) {
    		this.parent = parent;
    	}
    	/**
    	 * 得到子节点
    	 * @return
    	 */
    	public List<Node> getChildrens() {
    		return childrens;
    	}
    	/**
    	 * pandu是否根节点
    	 * @return
    	 *
    	 */
    	public boolean isRoot(){
    		return parent ==null?true:false;
    	}
    
    	/**
    	 * 是否被选中
    	 * @return
    	 *
    	 */
    	public boolean isChecked() {
    		return isChecked;
    	}
    	public void setChecked(boolean isChecked) {
    		this.isChecked = isChecked;
    	}
    	/**
    	 * 是否是展开状态
    	 * @return
    	 *
    	 */
    	public boolean isExplaned() {
    		return isExpand;
    	}
    	/**
    	 * 设置展开状态
    	 * @param isExplaned
    	 *
    	 */
    	public void setExplaned(boolean isExplaned) {
    		this.isExpand = isExplaned;
    	}
    	/**
    	 * 是否有复选框
    	 * @return
    	 *
    	 */
    	public boolean hasCheckBox() {
    		return hasCheckBox;
    	}
    	/**
    	 * 设置是否有复选框
    	 * @param hasCheckBox
    	 *
    	 */
    	public void setHasCheckBox(boolean hasCheckBox) {
    		this.hasCheckBox = hasCheckBox;
    	}
    
    
    
    
    	/**
    	 * 得到节点值
    	 * @return
    	 *
    	 */
    	public String getValue() {
    		return value;
    	}
    	/**
    	 * 设置节点值
    	 * @param value
    	 *
    	 */
    	public void setValue(String value) {
    		this.value = value;
    	}
    	/**
    	 * 增加一个子节点
    	 * @param node
    	 *
    	 */
    	public void addNode(Node node){
    		if(!childrens.contains(node)){
    			childrens.add(node);
    		}
    	}
    	/**
    	 * 移除一个子节点
    	 * @param node
    	 *
    	 */
    	public void removeNode(Node node){
    		if(childrens.contains(node))
    			childrens.remove(node);
    	}
    	/**
    	 * 移除指定位置的子节点
    	 * @param location
    	 *
    	 */
    	public void removeNode(int location){
    		childrens.remove(location);
    	}
    	/**
    	 * 清除所有子节点
    	 *
    	 */
    	public void clears(){
    		childrens.clear();
    	}
    	/**
    	 * 判断给出的节点是否当前节点的父节点
    	 * @param node
    	 * @return
    	 *
    	 */
    	public boolean isParent(Node node){
    		if(parent == null)return false;
    		if(parent.equals(node))return true;
    		return parent.isParent(node);
    	}
    	/**
    	 * 递归获取当前节点级别
    	 * @return
    	 *
    	 */
    	public int getLevel(){
    		return parent ==null?0:parent.getLevel()+1;
    	}
    	/**
    	 * 父节点是否处于折叠的状态
    	 * @return
    	 *
    	 */
    	public boolean isParentCollapsed(){
    		if(parent ==null)return false;
    		if(!parent.isExplaned())return true;
    		return parent.isParentCollapsed();
    	}
    	/**
    	 * 是否叶节点(没有展开下级的几点)
    	 * @return
    	 *
    	 */
    	public boolean isLeaf(){
    		return childrens.size()<1?true:false;
    	}
    	/**
    	 * 返回自己的id
    	 * @return
    	 **/
    	public String getCurId() {
    		// TODO Auto-generated method stub
    		return curId;
    	}
    	/**
    	 * 返回的父id
    	 * @return
    	 **/
    	public String getParentId() {
    		// TODO Auto-generated method stub
    		return parentId;
    	}
    }
    

    下面是核心代码:

    两种选择模式在treeAdapter中进行修改。

    package com.example.administrator.treeview.treeView;
    
    
    import android.content.Context;
    import android.util.Log;
    import android.view.LayoutInflater;
    import android.view.View;
    import android.view.View.OnClickListener;
    import android.view.ViewGroup;
    import android.widget.BaseAdapter;
    import android.widget.CheckBox;
    import android.widget.ImageView;
    import android.widget.TextView;
    
    
    import com.example.administrator.treeview.R;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class TreeAdapter extends BaseAdapter {
    	private Context con;
    	private LayoutInflater lif;
    	public List<Node> all = new ArrayList<Node>();//展示
    	private List<Node> cache = new ArrayList<Node>();//缓存,记录点状态
    	private TreeAdapter tree = this;
    	boolean hasCheckBox;
    	private int expandIcon = -1;//展开图标
    	private int collapseIcon = -1;//收缩图标
    	ViewItem vi = null;
    
    //	//存储checkbox选中的集合
    //	private List<>
    
    	/**
    	 * 构造方法
    	 */
    	public TreeAdapter(Context context, List<Node> rootNodes){
    		this.con = context;
    		this.lif = (LayoutInflater)con.getSystemService(Context.LAYOUT_INFLATER_SERVICE);
    		for(int i=0;i<rootNodes.size();i++){
    			addNode(rootNodes.get(i));
    		}
    	}
    	/**
    	 * 把一个节点上的所有的内容都挂上去
    	 * @param node
    	 */
    	public void addNode(Node node){
    		all.add(node);
    		cache.add(node);
    		if(node.isLeaf())return;
    		for(int i = 0;i<node.getChildrens().size();i++){
    			addNode(node.getChildrens().get(i));
    		}
    	}
    	/**
    	 * 设置展开收缩图标
    	 * @param expandIcon
    	 * @param collapseIcon
    	 */
    	public void setCollapseAndExpandIcon(int expandIcon,int collapseIcon){
    		this.collapseIcon = collapseIcon;
    		this.expandIcon = expandIcon;
    	}
    	/**
    	 * 一次性对某节点的所有节点进行选中or取消操作
    	 */
    	public void checkNode(Node n,boolean isChecked){
    		n.setChecked(isChecked);
    		checkChildren(n,isChecked);
    //		有一个子节点选中,则父节点选中
    		if (n.getParent()!=null)
    			checkParent(n,isChecked);
    //		有一个子节点未选中,则父节点未选中
    //		unCheckNode(n, isChecked);
    	}
    
    	/**
    	 * 对父节点操作时,同步操作子节点
    	 */
    	public void checkChildren(Node n,boolean isChecked){
    		for(int i =0 ;i<n.getChildrens().size();i++){
    			n.getChildrens().get(i).setChecked(isChecked);
    			checkChildren(n.getChildrens().get(i),isChecked);
    		}
    	}
    	/**
    	 *  有一个子节点选中,则父节点选中
    	 */
    	public void checkParent(Node n,boolean isChecked){
    //		有一个子节点选中,则父节点选中
    		if (n.getParent()!=null&&isChecked){
    			n.getParent().setChecked(isChecked);
    			checkParent(n.getParent(),isChecked);
    		}
    //		全部子节点取消选中,则父节点取消选中
    		if (n.getParent()!=null &&!isChecked){
    			for (int i = 0; i < n.getParent().getChildrens().size(); i++) {
    				if (n.getParent().getChildrens().get(i).isChecked()) {
    					checkParent(n.getParent(),!isChecked);
    					return ;
    				}
    			}
    			n.getParent().setChecked(isChecked);
    			checkParent(n.getParent(),isChecked);
    		}
    	}
    
    	/**
    	 *  有一个子节点未选中,则父节点未选中
    	 */
    	public void unCheckNode(Node n, boolean isChecked){
    		boolean flag = false;
    		n.setChecked(isChecked);
    		if(n.getParent() != null ){
    			Log.d("parentSize", n.getParent().getChildrens().get(0).isChecked() + "");
    			for (int i = 0; i < n.getParent().getChildrens().size(); i++) {
    				if((n.getParent().getChildrens().get(i)) != n && (n.getParent().getChildrens().get(i).isChecked() != true)){
    					flag = true;
    					break;
    				}
    			}
    			if(!flag) {
    				unCheckNode(n.getParent(), isChecked);
    			}
    		}
    	}
    
    	/**
    	 * 获取所有选中节点
    	 * @return
    	 *
    	 */
    	public List<Node> getSelectedNode(){
    		Log.d("getSelectedNode", "我被执行了!");
    		List<Node> checks =new ArrayList<Node>()	;
    		for(int i = 0;i<cache.size();i++){
    			Node n =(Node)cache.get(i);
    			if(n.isChecked())
    				checks.add(n);
    		}
    		return checks;
    	}
    
    	public void setSelectedNode(List<String> selectedNode){
    		for (int i=0;i<cache.size();i++) {
    			if(selectedNode.contains(cache.get(i).getCurId())) {
    				cache.get(i).setChecked(true);
    				cache.get(i).getParent().setChecked(true);
    			}
    		}
    	}
    	/**
    	 * 设置是否有复选框
    	 * @param hasCheckBox
    	 *
    	 */
    	public void setCheckBox(boolean hasCheckBox){
    		this.hasCheckBox = hasCheckBox;
    	}
    	/**
    	 * 控制展开缩放某节点
    	 * @param location
    	 *
    	 */
    	public void ExpandOrCollapse(int location){
    		Node n = all.get(location);//获得当前视图需要处理的节点 
    		if(n!=null)//排除传入参数错误异常
    		{
    			if(!n.isLeaf()){
    				n.setExplaned(!n.isExplaned());// 由于该方法是用来控制展开和收缩的,所以取反即可
    				filterNode();//遍历一下,将所有上级节点展开的节点重新挂上去
    				this.notifyDataSetChanged();//刷新视图
    			}
    		}
    	}
    
    	/**
    	 * 设置展开等级
    	 * @param level
    	 *
    	 */
    	public void setExpandLevel(int level){
    		all.clear();
    		for(int i = 0;i<cache.size();i++){
    			Node n = cache.get(i);
    			if(n.getLevel()<=level){
    				if(n.getLevel()<level)
    					n.setExplaned(true);
    				else
    					n.setExplaned(false);
    				all.add(n);
    			}
    		}
    
    	}
    	/* 清理all,从缓存中将所有父节点不为收缩状态的都挂上去*/
    	public void filterNode(){
    		all.clear();
    		for(int i = 0;i<cache.size();i++){
    			Node n = cache.get(i);
    			if(!n.isParentCollapsed()||n.isRoot())//凡是父节点不收缩或者不是根节点的都挂上去
    				all.add(n);
    		}
    	}
    
    	@Override
    	public int getCount() {
    		// TODO Auto-generated method stub
    		return all.size();
    	}
    
    
    	@Override
    	public Object getItem(int location) {
    		// TODO Auto-generated method stub
    		return all.get(location);
    	}
    
    
    	@Override
    	public long getItemId(int location) {
    		// TODO Auto-generated method stub
    		return location;
    	}
    
    
    	@Override
    	public View getView(final int location, View view, ViewGroup viewgroup) {
    
    		final Node n = all.get(location);
    
    		//ViewItem vi = null;
    		if(view == null){
    			view = lif.inflate(R.layout.member_item, null);
    			vi = new ViewItem();
    			vi.cb = (CheckBox)view.findViewById(R.id.checkBox);
    			vi.flagIcon = (ImageView)view.findViewById(R.id.disclosureImg);
    			vi.tv = (TextView)view.findViewById(R.id.contentText);
    			vi.cb.setOnClickListener(new OnClickListener() {
    				private Node mCheckBoxN;
    				@Override
    				public void onClick(View v) {
    					mCheckBoxN = (Node) v.getTag();
    					checkNode(mCheckBoxN, ((CheckBox) v).isChecked());
    					//unCheckNode(n, ((CheckBox) v).isChecked());
    					tree.notifyDataSetChanged();        //只有点击部门后刷新页面,不然刷新频繁导致卡顿
    
    				}
    			});
    			view.setTag(vi);
    		}
    		else{
    			vi = (ViewItem)view.getTag();
    		}
    		if(n!=null){
    			if(vi==null||vi.cb==null)
    				System.out.println();
    			vi.cb.setTag(n);
    			vi.cb.setChecked(n.isChecked());
    			//叶节点不显示展开收缩图标
    				if(n.isExplaned()){
    					if(expandIcon!=-1){
    						vi.flagIcon.setImageResource(expandIcon);
    					}
    				}
    				else{
    					if(collapseIcon!=-1){
    						vi.flagIcon.setImageResource(collapseIcon);
    					}
    				}
    			//显示文本
    			vi.tv.setText(n.getValue());
    			// 控制缩进
    			vi.flagIcon.setPadding(100*n.getLevel(), 3,3, 3);
    				if(n.isLeaf()){
    					vi.flagIcon.setVisibility(View.INVISIBLE);
    				}
    				else{
    					vi.flagIcon.setVisibility(View.VISIBLE);
    			}
    			//设置是否显示复选框
    			if(n.hasCheckBox()){
    				vi.cb.setVisibility(View.VISIBLE);
    			}
    			else{
    				vi.cb.setVisibility(View.GONE);
    			}
    		}
    		return view;
    	}
    
    
    	public class ViewItem{
    		private CheckBox cb;
    		private ImageView flagIcon;
    		private TextView tv;
    	}
    }
    

    接下来是TreeListView: 

    package com.example.administrator.treeview.treeView;
    
    import android.content.Context;
    import android.util.Log;
    import android.view.View;
    import android.view.ViewGroup;
    import android.widget.AdapterView;
    import android.widget.LinearLayout;
    import android.widget.ListView;
    import android.widget.RelativeLayout;
    import com.example.administrator.treeview.R;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.LinkedHashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    public class TreeListView extends ListView {
    	ListView treelist = null;
    	TreeAdapter ta = null;
    	public List<Node> mNodeList;
    	private List<Node> checkList;
    
    
    	public TreeListView(final Context context, List<Node> res) {
    		super(context);
    		treelist = this;
    		treelist.setFocusable(false);
    		treelist.setBackgroundColor(0xffffff);
    		treelist.setFadingEdgeLength(0);
    		treelist.setLayoutParams(new ViewGroup.LayoutParams(LinearLayout.LayoutParams.MATCH_PARENT, RelativeLayout.LayoutParams.MATCH_PARENT));
    
    		treelist.setOnItemClickListener(new OnItemClickListener() {
    
    			@Override
    			public void onItemClick(AdapterView<?> parent, View view,
                                        int position, long id) {
    				((TreeAdapter) parent.getAdapter()).ExpandOrCollapse(position);
    			}
    		});
    		initNode(context, initNodRoot(res), true, -1, -1, 0);
    	}
    
    	// 使用 onMeasure 方法,来解决尺寸高度的问题,以及事件冲突的问题;
    	protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
    		heightMeasureSpec = MeasureSpec.makeMeasureSpec(
    				Integer.MAX_VALUE>>2,
    				MeasureSpec.AT_MOST
    		);
    		super.onMeasure(widthMeasureSpec, heightMeasureSpec);
    	}
    //	/**
    //	 *
    //	 * @param context
    //	 *            响应监听的上下文
    //	 * @param root
    //	 *            已经挂好树的根节点
    //	 * @param hasCheckBox
    //	 *            是否整个树有复选框
    //	 * @param tree_ex_id
    //	 *            展开iconid -1会使用默认的
    //	 * @param tree_ec_id
    //	 *            收缩iconid -1会使用默认的
    //	 * @param expandLevel
    //	 *            初始展开等级
    //	 *
    //	 */
    	public List<Node> initNodRoot(List<Node> res) {
    		ArrayList<Node> list = new ArrayList<Node>();
    		ArrayList<Node> roots = new ArrayList<Node>();
    		Map<String, Node> nodemap = new LinkedHashMap<String, Node>();
    		for (int i = 0; i < res.size(); i++) {
    			Node nr = res.get(i);
    			Node n = new Node( nr.getParentId(), nr.getCurId(), nr.getValue());
    			nodemap.put(n.getCurId(), n);// 生成map树
    		}
    		Set<String> set = nodemap.keySet();
    		Collection<Node> collections = nodemap.values();
    		Iterator<Node> iterator = collections.iterator();
    		while (iterator.hasNext()) {// 添加所有根节点到root中
    			Node n = iterator.next();
    			if (!set.contains(n.getParentId()))
    				roots.add(n);
    			list.add(n);
    		}
    		for (int i = 0; i < list.size(); i++) {
    			Node n = list.get(i);
    			for (int j = i + 1; j < list.size(); j++) {
    				Node m = list.get(j);
    				if (m.getParentId() .equals( n.getCurId())) {
    					n.addNode(m);
    					m.setParent(n);
    					m.setParents(n);
    				} else if (m.getCurId() .equals( n.getParentId())) {
    					m.addNode(n);
    					n.setParent(m);
    					m.setParents(m);
    				}
    			}
    		}
    		return roots;
    	}
    
    	public void initNode(Context context, List<Node> root, boolean hasCheckBox,
                             int tree_ex_id, int tree_ec_id, int expandLevel) {
    		ta = new TreeAdapter(context, root);
    		//获取
    		mNodeList = ta.all;
    		// 设置整个树是否显示复选框
    		ta.setCheckBox(true);
    		// 设置展开和折叠时图标
    		int tree_ex_id_ = (tree_ex_id == -1) ? R.drawable.down_icon : tree_ex_id;
    		int tree_ec_id_ = (tree_ec_id == -1) ? R.drawable.right_icon : tree_ec_id;
    		ta.setCollapseAndExpandIcon(tree_ex_id_, tree_ec_id_);
    		// 设置默认展开级别
    		ta.setExpandLevel(expandLevel);
    		this.setAdapter(ta);
    	}
    	/* 返回当前所有选中节点的List数组 */
    	public List<Node> get() {
    		Log.d("get", ta.getSelectedNode().size() + "");
    		return ta.getSelectedNode();
    	}
    public void setSelect(List<String> allSelect){
    	ta.setSelectedNode(allSelect);
    }}
    

    资源地址:

    https://download.csdn.net/download/weixin_40299948/11157435

    github链接:

    https://github.com/Black-Mango/treeListView

    书写不易,麻烦点个赞/star/关注

    展开全文
  • 树形结构是非常重要的一种数据结构。我们可以通过平衡二叉树来实现排序问题,用树结构来表示源程序的语法结构,树也可以表示数据库或文件系统。并且很多容器的底层都是树结构。 下面先来了解关于树结构的名词有哪些...
  • 常用数据结构有哪些

    2015-11-29 20:39:33
    四类基本结构:集合、线性结构、树形结构、图状结构; 集合结构:除了同属于一种类型外,别无其它关系 线性结构:元素之间存在一对一关系常见类型: 数组,链表,队列,栈,它们之间在操作上有所区别.例如:...
  • 常用的局域网的网络拓扑有哪些种类?现在最流行的是哪种结构?为什么早期的以太网选择总线拓扑结构而不是星形拓扑结构,但现在却改为使用星形拓扑结构? 星形网,总线网,环形网,树形网 当时很可靠的星形拓扑结构...
  • 我们之前已经知道,数据结构就是计算机存储,组织数据的...(2)树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类...
  • 四类基本结构:集合、线性结构、树形结构、图状结构; 集合结构:除了同属于一种类型外,别无其它关系 线性结构:元素之间存在一对一关系常见类型: 数组,链表,队列,栈,它们之间在操作上有所区别. 例如...
  • 简单来说 数据结构有哪些? 存储方式上:链表形式,数组, 数据结构分别为逻辑结构、存储结构(物理结构) 逻辑结构又分为四类基本结构: 集合、线性结构、树形结构、图状结构(网状结构) 集合、线性...
  • Android带复选框的树形组织架构treeListView,类似目录和word的结构图,可折叠,带两种全选模式:1、子节点选中则父节点选中,适合多级多item下方便了解哪些被选中;2、子节点全部选中父节点才选中,更符合逻辑,...
  • 决策树(DT)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的...通过定义我们知道,决策树(DT)是一种树形结构,树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结...
  • 首先,良好的网站结构是提高文章...对于大型网站树形结构,它是一种常见的结构布局方法,而小型企业网站的物理结构有利于站点目录权重的整体提升,因为小站本身比较简单,而且侧面并列结构是许多小型企业站点采用的...
  • HASH索引可以一次定位,不需要像树形索引那样逐层查找,因此具有极高的效率。但是,这种高效是条件的,即只在“=”和“in”条件下高效,对于范围查询、排序及效率不高。 Hash 索引遇到大量Hash值相等的情况后性能...
  • 树形结构 树形结构具有分支、层次特性,其形态有点象自然界中的树. ④ 图状结构 图状结构中的结点按逻辑关系互相缠绕,任何两个结点都可以邻接 集合:结构中的数据元素之间除了同属于一种类型外,别无其它关系 ...
  • 最显著的特点 就是,您的数据层级结构,所有才使用树形的。说直白一点就是 子级 父级,那么这个数据 就可以使用TreeGrid进行展示。 ··· 记住一句话: 知识不是学的多就意义,而是用的多才能体现价值,...
  • 的头节点是公司唯一的老板,除老板外,每个员工都唯一的直接上级,叶节点是没有任何下属的基层员工,除基层员工外,每个员工都一个或多个直接下级,另外每个员工都一个快乐值。 这个公司现在要办 party,你...
  • DOM 建立树形结构的方式解析 XML 文档,DOM 解析器把 XML 文档转化为一个包含节点信息的树,可以对树的访问与修改,读取和修改 XML。 SAX 采用事件模型,解析 XML 文档时可以触发一系列事件,解析到期望的节点,...
  • gitflow 是什么,有哪些优缺点?1. 什么是git2. git的优点3....本地和云端的仓库的维护机制是类似的,它们都是使用一个类似一个树形结构的数据结构来维护的。每次的文件内容的改变都是一个节点(blob节点),
  • 常见Dom操作有哪些

    2018-04-16 10:46:52
    1.背景介绍DOM是Document Object Model(文档...在网页上,组织页面(或文档)的对象被组织在一个树形结构中,用来表示文档中对象的标准模型就称为DOM。Document Object Model的历史可以追溯至1990年代后期微软与Net...
  • Linux的目录结构为树形结构,最顶级的目录为根目录,其他目录通过挂载添加到树中,通过解除挂载来进行删除,除此之外,还可以对目录进行其他处理操作,常用的目录处理命令如下:1. ls命令(列出目录)常用用法:ls ...
  • 层次数据库是最早研制成功的数据库系统,它把数据通过层次结构(树形结构)的方式表现出来。层次数据库曾经是数据库的主流,但随着关系数据库的出现和普及,现在已经很少使用了。 比较具有代表性的层次数据库是 IMS...
  • 企业可以利用hr人力资源管理系统对有关部门进行设立和撤销操作,建立无限层级的树形部门结构。可以回顾部门结构的历史记录。快捷、方便的查看组织机构图,并直接打印,也可以导出为HTML格式。 2、绩效管理 h...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 238
精华内容 95
热门标签
关键字:

树形结构有哪些