树形数据结构——ClosureTable

比眉伴天荒 2021-10-19 02:32 864阅读 0赞

### 文章目录 ###

*  思想来源
 *  源码
 *   *  文件目录结构
     *  项目源码
     *  测试源码
 *  测试结果
 *  完整项目源码

# 思想来源 #

在现实的项目开发中，我们经常会用到`树形数据结构`，对于什么是树形数据结构，具体可以参考如下的两篇博文：

*  [ClosureTable实现高效无限分类][ClosureTable]
 *  [贡献一个 Laravel 树形结构管理包 ClosureTable][Laravel _ ClosureTable]

在看完上面两篇博文的基础上，我们就对树形数据结构，尤其是对ClosureTable有了更加清晰的认识，既然项目中经常会用到该树形数据结构，那么我们就有必要手写一个实现版本。

# 源码 #

## 文件目录结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1paWTEwNzg2ODkyNzY_size_16_color_FFFFFF_t_70]

## 项目源码 ##

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
    
    <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
      xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
      <modelVersion>4.0.0</modelVersion>
    
      <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.1.6.RELEASE</version>
      </parent>
    
      <groupId>com.lyc</groupId>
      <artifactId>closure-table</artifactId>
      <version>1.0-SNAPSHOT</version>
    
      <name>closure-table</name>
      <url>http://www.example.com</url>
    
      <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <maven.compiler.source>1.8</maven.compiler.source>
        <maven.compiler.target>1.8</maven.compiler.target>
        <spring-cloud.version>Greenwich.SR1</spring-cloud.version>
      </properties>
    
      <dependencyManagement>
        <dependencies>
          
          <dependency>
            <groupId>org.springframework.cloud</groupId>
            <artifactId>spring-cloud-dependencies</artifactId>
            <version>${spring-cloud.version}</version>
            <type>pom</type>
            <scope>import</scope>
          </dependency>
        </dependencies>
      </dependencyManagement>
    
      <dependencies>
        
        <dependency>
          <groupId>org.springframework.boot</groupId>
          <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        
        <dependency>
          <groupId>org.springframework.boot</groupId>
          <artifactId>spring-boot-starter-test</artifactId>
          <scope>test</scope>
        </dependency>
        
        <dependency>
          <groupId>org.projectlombok</groupId>
          <artifactId>lombok</artifactId>
          <version>1.18.8</version>
          <scope>provided</scope>
        </dependency>
      </dependencies>
    
      <build>
        <finalName>${project.artifactId}</finalName>
        <plugins>
          <plugin>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-maven-plugin</artifactId>
          </plugin>
        </plugins>
      </build>
    </project>

AncestorSequence

package com.lyc.closure.closureTable.core.ancestor;
    
    import com.lyc.closure.closureTable.core.Node;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 9:58 * @description: 祖先接口 **/
    public interface AncestorSequence { 
    
        // 节点数组指针的初始化
        boolean init(Node ele);
        // 加载节点数组指针域
        boolean loadNodeArray(Node ele);
        // 获取NodeArray对象
        NodeArray getNodeArray();
        // 获取当前节点数组
        Node[] getCurrentNodeArray();
        // 获取目标节点中的节点数组
        Node[] getNodeArray(Node ele);
        // 拷贝目标节点中的节点数组
        Node[] copyNodeArray(Node ele);
        // 设置节点中的节点数组指针域
        boolean setNodeArray(Node[] nodeArray, Node ele);
        // 写入节点中的节点数组指针域
        boolean writeNodeArray(Node ele);
        // 节点数组指针的判空
        boolean isEmpty();
        // 获取节点数组指针的长度
        int length();
        // 获取节点数组指针指定位置处的元素
        boolean getEle(int index, Node ele);
        // 返回第一个满足ele的数据元素的位置
        int locateEle(Node data);
        // 获取节点数组指针指定元素的前驱
        boolean priorEle(Node currentEle, Node preEle);
        // 获取节点数组指针指定元素的后继
        boolean nextEle(Node currentEle, Node nextEle);
        // 节点数组指针的数据添加（在最后添加）
        boolean insert(Node ele);
        // 节点数组指针的数据添加
        boolean insert(int index, Node ele);
        // 节点数组指针的数据删除（删除尾结点）
        boolean delete();
        // 节点数组指针的数据删除
        boolean delete(int index, Node pNode);
        // 节点数组指针的数据遍历
        void traverse();
        // 节点数组扩容
        boolean dilatation();
        // 节点数据深拷贝
        boolean cope(Node current, Node target);
    
    }

AncestorSequenceImpl

package com.lyc.closure.closureTable.core.ancestor;
    
    import com.lyc.closure.closureTable.core.Node;
    import com.lyc.closure.common.ClosureCommonConstant;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    import lombok.Getter;
    import lombok.NoArgsConstructor;
    import lombok.Setter;
    import lombok.extern.slf4j.Slf4j;
    import org.springframework.beans.BeanUtils;
    
    import java.util.Arrays;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 9:59 * @description: 祖先接口实现类 **/
    @Slf4j
    @Getter
    @Setter
    @NoArgsConstructor
    public class AncestorSequenceImpl implements AncestorSequence{ 
    
        // 节点数组指针域
        private NodeArray nodeArray = null;
        // 初始化节点数组
        private static final Node[] INIT_NODE_ARRAY = new Node[ClosureCommonConstant.Closure.INIT_CAPACITY];
    
        /** * 节点数组指针的初始化 * @param ele 节点 * @return boolean */
        @Override
        public boolean init(Node ele) { 
            // 如果节点不为空，则初始化节点数组，同时初始化节点的节点数组指针域
            if(ele != null){ 
                // 创建父辈路径节点数组
                NodeArray ancestors = NodeArray.builder()
                        .size(ClosureCommonConstant.Closure.INIT_CAPACITY)
                        .pList(INIT_NODE_ARRAY)
                        .iLength(ClosureCommonConstant.Closure.INIT_DATA_LENGTH)
                        .build();
                // 将创建的父辈路径节点数组添加到父辈节点域中
                ele.setAncestors(ancestors);
                // 加载Node对象中的NodeArray对象到NodeArrayCoreImpl的nodeArray中
                loadNodeArray(ele);
                return true;
            }
            return false;
        }
    
        /** * 加载节点数组指针域，如果成功，则返回true，失败则返回false * @param ele 目标节点 * @return boolean */
        @Override
        public boolean loadNodeArray(Node ele) { 
            if(ele != null){ 
                this.nodeArray = ele.getAncestors();
                return true;
            }
            return false;
        }
    
        /** * 获取当前节点数组 * @return Node[] */
        @Override
        public Node[] getCurrentNodeArray() { 
            return this.nodeArray.getPList();
        }
    
        /** * 获取目标节点中的节点数组 * @param ele 目标节点 * @return Node[] */
        @Override
        public Node[] getNodeArray(Node ele) { 
            // 如果节点不为空，则返回节点中的节点数组指针域
            if(ele != null){ 
                return ele.getAncestors().getPList();
            }
            return null;
        }
    
        /** * 拷贝目标节点中的节点数组 * @param ele 目标节点 * @return Node[] */
        @Override
        public Node[] copyNodeArray(Node ele) { 
            // 如果节点不为空，则返回节点中的节点数组指针域
            if(ele != null){ 
                // 获取NodeArray容器
                Node[] nodeArrayContainer = ele.getAncestors().getPList();
                // 从容器中复制有效数据，并返回
                return Arrays.copyOf(nodeArrayContainer,ele.getAncestors().getILength());
            }
            return null;
        }
    
        /** * 设置节点中的节点数组指针域 * @param nodeArray 节点数组指针域 * @param ele 目标节点 * @return boolean */
        @Override
        public boolean setNodeArray(Node[] nodeArray,Node ele) { 
            // 如果当前节点数组指针域与目标节点均不为空，则执行赋值操作
            if(nodeArray != null && ele != null){ 
                ele.getAncestors().setPList(nodeArray);
                return true;
            }
            return false;
        }
    
        /** * 写入节点中的节点数组指针域 * @param ele 节点数组指针域 * @return boolean */
        @Override
        public boolean writeNodeArray(Node ele) { 
            // 如果不为空，则将节点数组指针域回写到当前节点中
            if(ele != null){ 
                ele.setAncestors(this.getNodeArray());
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的判空 * @return boolean */
        @Override
        public boolean isEmpty() { 
            if(this.nodeArray != null && this.nodeArray.getILength() == 0){ 
                return true;
            }
            return false;
        }
    
        /** * 获取节点数组指针的长度 * @return int */
        @Override
        public int length() { 
            if(this.nodeArray != null){ 
                return this.nodeArray.getILength();
            }
            return 0;
        }
    
        /** * 获取节点数组指针指定位置处的元素 * @param index 节点的索引值 * @param ele 获取的元素 * @return boolean */
        @Override
        public boolean getEle(int index, Node ele) { 
            // 如果数据在有效范围内
            if(index >= 0 && index < this.nodeArray.getILength()){ 
                // 则取出相应的元素直接赋值给ele，传出
                // 获取目标节点
                Node temp = this.nodeArray.getPList()[index];
                // 数据拷贝
                cope(temp,ele);
                // 获取成功后返回成功状态
                return true;
            }
            return false;
        }
    
        /** * 返回第一个满足ele的数据元素的位序 * @param ele 目标节点 * @return int */
        @Override
        public int locateEle(Node ele) { 
            // 如果目标节点存在
            if(ele != null){ 
                // 获取节点数组指针域
                Node[] pList = this.nodeArray.getPList();
                // 获取节点数组的长度
                int length = this.nodeArray.getILength();
                // 循环遍历，依次查找比对节点的数据域
                for(int i = 0; i < length; i ++){ 
                    // 如果当前节点的数据域与目标节点的数据域相同，则返回当前节点所在的位序
                    if(pList[i].getData() == ele.getData()){ 
                        return i;
                    }
                }
            }
            // 如果查找不到，则返回位序值为-1
            return -1;
        }
    
        /** * 获取节点数组指针指定元素的前驱 * @param currentEle 当前节点 * @param preEle 前一个节点 * @return boolean */
        @Override
        public boolean priorEle(Node currentEle, Node preEle) { 
            // 获取当前元素所在的位序
            int temp = locateEle(currentEle);
            // 如果在有效范围内
            if(temp > 0){    // 第一个元素没有前驱
                // 获取前驱节点
                Node temp2 = this.nodeArray.getPList()[temp - 1];
                // 数据拷贝
                cope(temp2,preEle);
                // 前驱节点获取成功后返回true
                return true;
            }
            return false;
        }
    
        /** * 获取节点数组指针指定元素的后继 * @param currentEle 当前元素 * @param nextEle 指定元素的后继 * @return boolean */
        @Override
        public boolean nextEle(Node currentEle, Node nextEle) { 
            // 获取当前元素所在的位序
            int temp = locateEle(currentEle);
            // 如果在有效范围内
            if(temp != -1 && temp < this.nodeArray.getILength() -1){ 
                // 获取后继节点
                Node temp2 = this.nodeArray.getPList()[temp + 1];
                // 数据拷贝
                cope(temp2,nextEle);
                // 获取后继点解成功后返回true
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的数据添加（在最后添加） * @param ele 目标元素 * @return boolean */
        @Override
        public boolean insert(Node ele) { 
            // 获取节点数组的长度
            int length = length();
            // 如果数据在有效范围内
            if(length < this.nodeArray.getSize()){ 
                // 运行扩容方法（不一定会扩容）
                dilatation();
                // 将传入节点插入到节点数组中（尾端插入）
                this.nodeArray.getPList()[length] = ele;
                // 添加完成之后，长度自增1
                this.nodeArray.setILength(this.nodeArray.getILength() + 1);
                return true;
            }
            // 执行插入操作
            return false;
        }
    
        /** * 节点数组指针的数据添加 * @param index 索引值 * @param ele 目标元素 * @return boolean */
        @Override
        public boolean insert(int index, Node ele) { 
            // 如果插入点在有效范围内
            if(index > 0 && index < this.nodeArray.getSize() - 1){ 
                // 运行扩容方法（不一定会扩容）
                dilatation();
                // 将传入节点插入到节点数组中（非尾端插入，需要移动节点）
                // 先获取节点数组
                Node[] pList = this.nodeArray.getPList();
                for(int k = this.nodeArray.getILength() - 1; k >= index; k --){ 
                    // 把当前元素向后移动一位
                    pList[k + 1] = pList[k];
                }
                // 将目标元素插入到目标位序
                pList[index] = ele;
                // 将数据长度+1
                this.nodeArray.setILength(this.nodeArray.getILength() + 1);
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的数据删除（删除尾结点） * @return boolean */
        @Override
        public boolean delete() { 
            // 如果数据在有效长度范围内
            if(this.nodeArray.getILength() > 0){    // 保证数组容器内至少有一个节点
                // 删除尾结点（采用逻辑删除即可）
                this.nodeArray.setILength(this.nodeArray.getILength() - 1);
            }
            return false;
        }
    
        /** * 节点数组指针的数据删除 * @param index 目标节点位序 * @param pNode 目标节点 * @return boolean */
        @Override
        public boolean delete(int index, Node pNode) { 
            // 如果数据在有效范围内
            if(index > -1 && index <= this.nodeArray.getILength() - 1){ 
                // 获取节点数组
                Node[] pList = this.nodeArray.getPList();
                // 获取指定位置处的节点
                getEle(index,pNode);
                // 循环遍历，向左移动数组
                for(int k = index + 1; k < this.nodeArray.getILength(); k ++){ 
                    // 后一个元素向左移动一个元素
                    pList[index] = pList[k];
                }
                // 节点数组长度自减1
                this.nodeArray.setILength(this.nodeArray.getILength() - 1);
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的数据遍历 */
        @Override
        public void traverse() { 
            // 获取节点数组
            Node[] pList = this.nodeArray.getPList();
            // 获取节点数组长度
            int length = this.nodeArray.getILength();
            // 如果节点数组不为空
            if(length > 0){ 
                // 循环遍历所有的数据
                for(int i = 0; i < length; i ++) { 
                    // 在控制台中打印节点数组
                    log.info(pList[i].getData().toString());
                }
            }
        }
    
        /** * 节点数组扩容 * @return boolean */
        @Override
        public boolean dilatation() { 
            // 如果达到加载因子上限，则执行扩容操作
            if(this.nodeArray.getILength() >= (this.nodeArray.getSize() * ClosureCommonConstant.Closure.DEFAULT_LOAD_FACTOR)){ 
                // 生成新的容器容量
                int capacity = this.nodeArray.getSize() << 1;
                // 生成新的节点数组
                Node[] pList = Arrays.copyOf(this.nodeArray.getPList(),capacity);
                // 将新的节点数组回写到当前节点的节点数组指针域中
                this.nodeArray.setPList(pList);
                // 将容器的容量设置为新的数值
                this.nodeArray.setSize(capacity);
                // 扩容成功后，返回true
                return true;
            }
            return false;
        }
    
        /** * 节点数据深拷贝 * @param current 当前节点 * @param target 目标节点 * @return boolean */
        @Override
        public boolean cope(Node current, Node target) { 
            if(current != null && target != null){ 
                // 执行数据拷贝
                BeanUtils.copyProperties(current,target);
                // 拷贝成功后，返回拷贝后的结果
                return true;
            }
            return false;
        }
    
    }

DescendantSequence

package com.lyc.closure.closureTable.core.descendant;
    
    import com.lyc.closure.closureTable.core.Node;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 10:03 * @description: 子孙接口 **/
    public interface DescendantSequence { 
    
        // 节点数组指针的初始化
        boolean init(Node ele);
        // 加载节点数组指针域
        boolean loadNodeArray(Node ele);
        // 获取NodeArray对象
        NodeArray getNodeArray();
        // 获取当前节点数组
        Node[] getCurrentNodeArray();
        // 获取目标节点中的节点数组
        Node[] getNodeArray(Node ele);
        // 拷贝目标节点中的节点数组
        Node[] copyNodeArray(Node ele);
        // 设置节点中的节点数组指针域
        boolean setNodeArray(Node[] nodeArray, Node ele);
        // 写入节点中的节点数组指针域
        boolean writeNodeArray(Node ele);
        // 节点数组指针的判空
        boolean isEmpty();
        // 获取节点数组指针的长度
        int length();
        // 获取节点数组指针指定位置处的元素
        boolean getEle(int index, Node ele);
        // 返回第一个满足ele的数据元素的位置
        int locateEle(Node data);
        // 获取节点数组指针指定元素的前驱
        boolean priorEle(Node currentEle, Node preEle);
        // 获取节点数组指针指定元素的后继
        boolean nextEle(Node currentEle, Node nextEle);
        // 节点数组指针的数据添加（在最后添加）
        boolean insert(Node ele);
        // 节点数组指针的数据添加
        boolean insert(int index, Node ele);
        // 节点数组指针的数据删除（删除尾结点）
        boolean delete();
        // 节点数组指针的数据删除
        boolean delete(int index, Node pNode);
        // 节点数组指针的数据遍历
        void traverse();
        // 节点数组扩容
        boolean dilatation();
        // 节点数据深拷贝
        boolean cope(Node current, Node target);
        // 同级排序
        boolean siblingSort(int prior, int next);
        // 插入点位置
        boolean replace(int location,Node node);
    
    }

DescendantSequenceImpl

package com.lyc.closure.closureTable.core.descendant;
    
    import com.lyc.closure.closureTable.core.Node;
    import com.lyc.closure.common.ClosureCommonConstant;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    import lombok.Getter;
    import lombok.NoArgsConstructor;
    import lombok.Setter;
    import lombok.extern.slf4j.Slf4j;
    import org.springframework.beans.BeanUtils;
    
    import java.util.Arrays;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 10:04 * @description: 子孙接口实现类 **/
    @Slf4j
    @Getter
    @Setter
    @NoArgsConstructor
    public class DescendantSequenceImpl implements DescendantSequence{ 
    
        // 节点数组指针域
        private NodeArray nodeArray = null;
        // 初始化节点数组
        private static final Node[] INIT_NODE_ARRAY = new Node[ClosureCommonConstant.Closure.INIT_CAPACITY];
    
        /** * 节点数组指针的初始化 * @param ele 节点 * @return boolean */
        @Override
        public boolean init(Node ele) { 
            // 如果节点不为空，则初始化节点数组，同时初始化节点的节点数组指针域
            if(ele != null){ 
                NodeArray nodeArray = NodeArray.builder()
                        .size(ClosureCommonConstant.Closure.INIT_CAPACITY)
                        .pList(INIT_NODE_ARRAY)
                        .iLength(ClosureCommonConstant.Closure.INIT_DATA_LENGTH)
                        .build();
                ele.setNextArray(nodeArray);
                // 加载Node对象中的NodeArray对象到NodeArrayCoreImpl的nodeArray中
                loadNodeArray(ele);
                return true;
            }
            return false;
        }
    
        /** * 加载节点数组指针域，如果成功，则返回true，失败则返回false * @param ele 目标节点 * @return boolean */
        @Override
        public boolean loadNodeArray(Node ele) { 
            if(ele != null){ 
                this.nodeArray = ele.getNextArray();
                return true;
            }
            return false;
        }
    
        /** * 获取当前节点数组 * @return Node[] */
        @Override
        public Node[] getCurrentNodeArray() { 
            return this.nodeArray.getPList();
        }
    
        /** * 获取目标节点中的节点数组 * @param ele 目标节点 * @return Node[] */
        @Override
        public Node[] getNodeArray(Node ele) { 
            // 如果节点不为空，则返回节点中的节点数组指针域
            if(ele != null){ 
                return ele.getNextArray().getPList();
            }
            return null;
        }
    
        /** * 拷贝目标节点中的节点数组 * @param ele 目标节点 * @return Node[] */
        @Override
        public Node[] copyNodeArray(Node ele) { 
            // 如果节点不为空，则返回节点中的节点数组指针域
            if(ele != null){ 
                // 获取NodeArray容器
                Node[] nodeArrayContainer = ele.getNextArray().getPList();
                // 从容器中复制有效数据，并返回
                return Arrays.copyOf(nodeArrayContainer,ele.getNextArray().getILength());
            }
            return null;
        }
    
        /** * 设置节点中的节点数组指针域 * @param nodeArray 节点数组指针域 * @param ele 目标节点 * @return boolean */
        @Override
        public boolean setNodeArray(Node[] nodeArray,Node ele) { 
            // 如果当前节点数组指针域与目标节点均不为空，则执行赋值操作
            if(nodeArray != null && ele != null){ 
                ele.getNextArray().setPList(nodeArray);
                return true;
            }
            return false;
        }
    
        /** * 写入节点中的节点数组指针域 * @param ele 节点数组指针域 * @return boolean */
        @Override
        public boolean writeNodeArray(Node ele) { 
            // 如果不为空，则将节点数组指针域回写到当前节点中
            if(ele != null){ 
                ele.setNextArray(this.getNodeArray());
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的判空 * @return boolean */
        @Override
        public boolean isEmpty() { 
            if(this.nodeArray != null && this.nodeArray.getILength() == 0){ 
                return true;
            }
            return false;
        }
    
        /** * 获取节点数组指针的长度 * @return int */
        @Override
        public int length() { 
            if(this.nodeArray != null){ 
                return this.nodeArray.getILength();
            }
            return 0;
        }
    
        /** * 获取节点数组指针指定位置处的元素 * @param index 节点的索引值 * @param ele 获取的元素 * @return boolean */
        @Override
        public boolean getEle(int index, Node ele) { 
            // 如果数据在有效范围内
            if(index >= 0 && index < this.nodeArray.getILength()){ 
                // 则取出相应的元素直接赋值给ele，传出
                // 获取目标节点
                Node temp = this.nodeArray.getPList()[index];
                // 数据拷贝
                cope(temp,ele);
                // 获取成功后返回成功状态
                return true;
            }
            return false;
        }
    
        /** * 返回第一个满足ele的数据元素的位序 * @param ele 目标节点 * @return int */
        @Override
        public int locateEle(Node ele) { 
            // 如果目标节点存在
            if(ele != null){ 
                // 获取节点数组指针域
                Node[] pList = this.nodeArray.getPList();
                // 获取节点数组的长度
                int length = this.nodeArray.getILength();
                // 循环遍历，依次查找比对节点的数据域
                for(int i = 0; i < length; i ++){ 
                    // 如果当前节点的数据域与目标节点的数据域相同，则返回当前节点所在的位序
                    if(pList[i].getData() == ele.getData()){ 
                        return i;
                    }
                }
            }
            // 如果查找不到，则返回位序值为-1
            return -1;
        }
    
        /** * 获取节点数组指针指定元素的前驱 * @param currentEle 当前节点 * @param preEle 前一个节点 * @return boolean */
        @Override
        public boolean priorEle(Node currentEle, Node preEle) { 
            // 获取当前元素所在的位序
            int temp = locateEle(currentEle);
            // 如果在有效范围内
            if(temp > 0){    // 第一个元素没有前驱
                // 获取前驱节点
                Node temp2 = this.nodeArray.getPList()[temp - 1];
                // 数据拷贝
                cope(temp2,preEle);
                // 前驱节点获取成功后返回true
                return true;
            }
            return false;
        }
    
        /** * 获取节点数组指针指定元素的后继 * @param currentEle 当前元素 * @param nextEle 指定元素的后继 * @return boolean */
        @Override
        public boolean nextEle(Node currentEle, Node nextEle) { 
            // 获取当前元素所在的位序
            int temp = locateEle(currentEle);
            // 如果在有效范围内
            if(temp != -1 && temp < this.nodeArray.getILength() -1){ 
                // 获取后继节点
                Node temp2 = this.nodeArray.getPList()[temp + 1];
                // 数据拷贝
                cope(temp2,nextEle);
                // 获取后继点解成功后返回true
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的数据添加（在最后添加） * @param ele 目标元素 * @return boolean */
        @Override
        public boolean insert(Node ele) { 
            // 获取节点数组的长度
            int length = length();
            // 如果数据在有效范围内
            if(length < this.nodeArray.getSize()){ 
                // 运行扩容方法（不一定会扩容）
                dilatation();
                // 将传入节点插入到节点数组中（尾端插入）
                this.nodeArray.getPList()[length] = ele;
                // 添加完成之后，长度自增1
                this.nodeArray.setILength(this.nodeArray.getILength() + 1);
                return true;
            }
            // 执行插入操作
            return false;
        }
    
        /** * 节点数组指针的数据添加 * @param index 索引值 * @param ele 目标元素 * @return boolean */
        @Override
        public boolean insert(int index, Node ele) { 
            // 如果插入点在有效范围内
            if(index > 0 && index < this.nodeArray.getSize() - 1){ 
                // 运行扩容方法（不一定会扩容）
                dilatation();
                // 将传入节点插入到节点数组中（非尾端插入，需要移动节点）
                // 先获取节点数组
                Node[] pList = this.nodeArray.getPList();
                for(int k = this.nodeArray.getILength() - 1; k >= index; k --){ 
                    // 把当前元素向后移动一位
                    pList[k + 1] = pList[k];
                }
                // 将目标元素插入到目标位序
                pList[index] = ele;
                // 将数据长度+1
                this.nodeArray.setILength(this.nodeArray.getILength() + 1);
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的数据删除（删除尾结点） * @return boolean */
        @Override
        public boolean delete() { 
            // 如果数据在有效长度范围内
            if(this.nodeArray.getILength() > 0){    // 保证数组容器内至少有一个节点
                // 删除尾结点（采用逻辑删除即可）
                this.nodeArray.setILength(this.nodeArray.getILength() - 1);
            }
            return false;
        }
    
        /** * 节点数组指针的数据删除 * @param index 目标节点位序 * @param pNode 目标节点 * @return boolean */
        @Override
        public boolean delete(int index, Node pNode) { 
            // 如果数据在有效范围内
            if(index > -1 && index <= this.nodeArray.getILength() - 1){ 
                // 获取节点数组
                Node[] pList = this.nodeArray.getPList();
                // 获取指定位置处的节点
                getEle(index,pNode);
                // 循环遍历，向左移动数组
                for(int k = index + 1; k < this.nodeArray.getILength(); k ++){ 
                    // 后一个元素向左移动一个元素
                    pList[index] = pList[k];
                }
                // 节点数组长度自减1
                this.nodeArray.setILength(this.nodeArray.getILength() - 1);
                return true;
            }
            return false;
        }
    
        /** * 节点数组指针的数据遍历 */
        @Override
        public void traverse() { 
            // 获取节点数组
            Node[] pList = this.nodeArray.getPList();
            // 获取节点数组长度
            int length = this.nodeArray.getILength();
            // 如果节点数组不为空
            if(length > 0){ 
                // 循环遍历所有的数据
                for(int i = 0; i < length; i ++) { 
                    // 在控制台中打印节点数组
                    log.info(pList[i].getData().toString());
                }
            }
        }
    
        /** * 节点数组扩容 * @return boolean */
        @Override
        public boolean dilatation() { 
            // 如果达到加载因子上限，则执行扩容操作
            if(this.nodeArray.getILength() >= (this.nodeArray.getSize() * ClosureCommonConstant.Closure.DEFAULT_LOAD_FACTOR)){ 
                // 生成新的容器容量
                int capacity = this.nodeArray.getSize() << 1;
                // 生成新的节点数组
                Node[] pList = Arrays.copyOf(this.nodeArray.getPList(),capacity);
                // 将新的节点数组回写到当前节点的节点数组指针域中
                this.nodeArray.setPList(pList);
                // 将容器的容量设置为新的数值
                this.nodeArray.setSize(capacity);
                // 扩容成功后，返回true
                return true;
            }
            return false;
        }
    
        /** * 节点数据深拷贝 * @param current 当前节点 * @param target 目标节点 * @return boolean */
        @Override
        public boolean cope(Node current, Node target) { 
            if(current != null && target != null){ 
                // 执行数据拷贝
                BeanUtils.copyProperties(current,target);
                return true;
            }
            return false;
        }
    
        /** * 同级排序 * @param prior 前一个节点位置 * @param next 后一个节点位置 * @return boolean 排序后的状态 */
        @Override
        public boolean siblingSort(int prior, int next) { 
            // 创建前一个节点
            Node priorNode = new Node();
            // 创建后一个节点
            Node nextNode = new Node();
            // 如果前后节点均获取成功
            if(getEle(prior,priorNode) && getEle(next,nextNode)){ 
                // 创建缓存节点
                Node temp = new Node();
                // 将前一个节点赋值给缓存节点
                cope(priorNode,temp);
                // 将后一个节点插入到前一个节点中
                replace(prior,nextNode);
                // 将前一个节点插入到后一个节点中
                replace(next,temp);
                // 位置交换完成后，返回true
                return true;
            }
            return false;
        }
    
        /** * 插入点位置 * @param location 替换位置 * @param node 替换节点 * @return boolean 替换状态 */
        @Override
        public boolean replace(int location, Node node) { 
            // 如果数据范围有效
            if(location > -1 && location <= this.nodeArray.getSize() - 1){ 
                // 获取当前层级的节点数组
                Node[] pList = this.nodeArray.getPList();
                // 执行替换操作
                pList[location] = node;
                // 替换完成后，返回true。
                return true;
            }
            // 默认返回false
            return false;
        }
    
    }

Closure

package com.lyc.closure.closureTable.core.entity;
    
    import lombok.*;
    
    /** * @author: 张侦毅 * @date: 2019/6/10 17:38 * @description: ClosureTable 实体类 **/
    @Getter
    @Setter
    @Builder
    @ToString
    @NoArgsConstructor
    @AllArgsConstructor
    public class Closure { 
    
        // 主键id
        private Long id;
        // 祖辈
        private Long ancestor;
        // 子孙
        private Long descendant;
        // 距离
        private int distance;
        // 是否叶子节点（0，是，1否）
        // 备注，该字段无用已经被废弃
        /*private int isLeaf;*/
    
        public Closure(Long ancestor, Long descendant, int distance) { 
            this.ancestor = ancestor;
            this.descendant = descendant;
            this.distance = distance;
        }
    
    }

NodeArray

package com.lyc.closure.closureTable.core.entity;
    
    import com.lyc.closure.closureTable.core.Node;
    import lombok.*;
    
    /** * @author: 张侦毅 * @date: 2019/6/12 17:03 * @description: 节点数组 **/
    @Getter
    @Setter
    @Builder
    @NoArgsConstructor
    @AllArgsConstructor
    public class NodeArray { 
    
        // 数组容量
        private int size = 0;
        // 数组
        private Node[] pList = null;
        // 数据容量
        private int iLength = 0;
    
    }

ClosureTableLinkedList

package com.lyc.closure.closureTable.core;
    
    import com.lyc.closure.closureTable.print.Printer;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 10:08 * @description: ClosureTable接口 **/
    public interface ClosureTableLinkedList { 
    
        // 初始化链表
        Node init();
        // 销毁链表
        void destroy();
        // 清空链表
        void clean();
        // 链表判空
        boolean empty();
        // 获取指定元素的前驱
        boolean priorEle(Node node,Node priorNode);
        // 在广义表指定节点下插入元素
        boolean insert(Node position, Node ele);
        // 删除链表中指定位置处的元素，包含子元素
        boolean delete(Node node);
        // 循环遍历广义表（这里的遍历采用的是前序遍历）
        void traverse();
        // 使用函数打印
        void traverse(Printer printer);
        // 获取当前节点的儿子节点
        Node[] getChildren(Node ele);
        // 遍历子孙节点树
        void descendantTraverse(Node ele);
        // 遍历打印父辈节点路径
        void nodePathTraverse(Node ele);
        // 父辈节点路径顺序表拷贝（深拷贝）
        boolean copyAncestors(Node current, Node target);
        // 节点拷贝
        boolean copyNode(Node current, Node target);
        // 节点修改
        boolean update(Node deleteNode, Node insertNode);
        // 同级排序
        boolean siblingSort(Node target, int prior, int next);
    
    }

ClosureTableLinkedListImpl

package com.lyc.closure.closureTable.core;
    
    import com.lyc.closure.closureTable.core.ancestor.AncestorSequence;
    import com.lyc.closure.closureTable.core.ancestor.AncestorSequenceImpl;
    import com.lyc.closure.closureTable.core.descendant.DescendantSequence;
    import com.lyc.closure.closureTable.core.descendant.DescendantSequenceImpl;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    import com.lyc.closure.closureTable.print.Printer;
    import lombok.Getter;
    import lombok.NoArgsConstructor;
    import lombok.Setter;
    import org.springframework.beans.BeanUtils;
    import org.springframework.stereotype.Service;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 10:08 * @description: ClosureTable接口实现类 **/
    @Getter
    @Setter
    @NoArgsConstructor
    @Service
    public class ClosureTableLinkedListImpl implements ClosureTableLinkedList { 
    
        // 节点数组链表集合
        private Node root;
        // 根节点
        private static final Long ROOT = 0L;
        // 子孙顺序表
        DescendantSequence descendantSequence = new DescendantSequenceImpl();
        // 祖先顺序表
        AncestorSequence ancestorSequence = new AncestorSequenceImpl();
    
        /** * 初始化链表 */
        @Override
        public Node init() { 
            // 创建根节点，并将根节点赋给pList
            this.root = new Node(ROOT);
            // 初始化根节点深度（根节点深度为0）
            this.root.setDepth(-1);
            // 返回根节点
            return this.root;
        }
    
        /** * 销毁链表 */
        @Override
        public void destroy() { 
            // 销毁根节点
            this.root = null;
            // 销毁子孙节点
            this.descendantSequence = null;
            // 销毁父级节点
            this.ancestorSequence = null;
        }
    
        /** * 清空链表 */
        @Override
        public void clean() { 
            // 初始化根节点
            this.root = new Node(ROOT);
            // 初始化根节点深度（根节点深度为0）
            this.root.setDepth(-1);
            // 初始化子孙节点
            this.descendantSequence = new DescendantSequenceImpl();;
            // 初始化父级节点
            this.ancestorSequence = new AncestorSequenceImpl();
        }
    
        /** * 链表判空 * @return boolean 判空状态 */
        @Override
        public boolean empty() { 
            // 如果层级为-1，则表示已空
            if(this.root.getDepth() == -1){ 
                // 返回状态为true
                return true;
            }
            // 返回状态为false
            return false;
        }
    
        /** * 获取指定元素的前驱 * @param node 当前元素 * @param priorNode 前驱节点 * @return boolean 获取前驱状态 */
        @Override
        public boolean priorEle(Node node,Node priorNode) { 
            // 获取当前元素的前驱节点
            NodeArray ancestors = node.getAncestors();
            // 如果前驱节点不为空（其中添加的虚拟顶点应该排除在外，故此处应该是大于1）
            if(ancestors.getILength() > 1){ 
                // 获取前驱节点数组
                Node[] ancestorsPList = ancestors.getPList();
                // 获取父级节点（前驱）
                Node parentNode = ancestorsPList[ancestors.getILength() - 1];
                // 将当前节点数据拷贝到前驱节点中
                copyNode(parentNode,priorNode);
                // 返回正确
                return true;
            }
            // 返回错误
            return false;
        }
    
        /** * 在广义表指定节点下插入元素 * @param position 指定位置节点 * @param ele 目标节点 * @return boolean 返回插入后的状态 */
        @Override
        public boolean insert(Node position,Node ele) { 
            // 元素判空
            if(ele != null){ 
                // 获取当前节点的深度，然后在该深度的基础上+1，并赋给插入节点
                ele.setDepth(position.getDepth() + 1);
                // 顺序表加载目标节点中的节点数组
                descendantSequence.loadNodeArray(position);
                // 在目标节点下添加元素
                descendantSequence.insert(ele);
                // 将当前节点的父辈路径拷贝到插入节点
                copyAncestors(position,ele);
                // 父辈路径顺序表加载插入节点
                ancestorSequence.loadNodeArray(ele);
                // 父辈路径顺序表插入坐标节点
                ancestorSequence.insert(position);
                // 添加完成后，返回true
                return true;
            }
            return false;
        }
    
        /** * 删除链表中指定位置处的元素，包含子元素 * @param node 节点 * @return boolean 返回删除后的状态 */
        @Override
        public boolean delete(Node node) { 
            // 创建前驱节点
            Node priorNode = new Node();
            // 查找前驱
            priorEle(node,priorNode);
            // 加载子孙数组节点指针域
            if(descendantSequence.loadNodeArray(priorNode)){ 
                // 获取删除节点位置
                int location = descendantSequence.locateEle(node);
                // 删除指定位置处的节点
                descendantSequence.delete(location,node);
                // 删除成功后，返回true
                return true;
            }
            // 否则返回false
            return false;
        }
    
        /** * 循环遍历广义表（这里的遍历采用的是前序遍历） */
        @Override
        public void traverse() { 
            // 前序遍历
            root.frontShow();
        }
    
        /** * 使用函数打印 * @param printer 打印器 */
        @Override
        public void traverse(Printer printer) { 
            root.frontShow(printer);
        }
    
        /** * 获取当前节点的儿子节点 * @param ele 目标节点 * @return Node[] */
        @Override
        public Node[] getChildren(Node ele) { 
            return descendantSequence.copyNodeArray(ele);
        }
    
        /** * 遍历子孙节点树 * @param ele 目标节点 */
        @Override
        public void descendantTraverse(Node ele) { 
            root.frontShow(ele);
        }
    
        /** * 遍历打印节点路径 */
        @Override
        public void nodePathTraverse(Node ele) { 
            root.frontShow(ele);
        }
    
        /** * 父辈节点路径顺序表拷贝（深拷贝） * @param current 当前节点 * @param target 目标节点 * @return boolean */
        @Override
        public boolean copyAncestors(Node current, Node target) { 
            // 如果两个节点同时存在
            if(current != null && target != null){ 
                // 节点拷贝
                // 节点数组深拷贝
                NodeArray ancestors = deepCopy(current.getAncestors());
                // 将深拷贝后的对象赋值给目标节点的父辈节点域
                target.setAncestors(ancestors);
                // 拷贝成功后，返回true
                return true;
            }
            return false;
        }
    
        /** * 节点拷贝 * @param current 当前节点 * @param target 目标节点 * @return boolean 拷贝状态 */
        @Override
        public boolean copyNode(Node current, Node target) { 
            // 如果两个节点同时存在
            if(current != null && target != null){ 
                BeanUtils.copyProperties(current,target);
                return true;
            }
            return false;
        }
    
        /** * 节点修改 * @param deleteNode 删除节点 * @param insertNode 插入目标节点 * @return boolean 插入状态 */
        @Override
        public boolean update(Node deleteNode, Node insertNode) { 
            // 如果删除节点与插入节点均存在
            if(deleteNode != null && insertNode != null){ 
                // 如果删除成功，此时获得了删除节点
                if(delete(deleteNode)){ 
                    // 如果插入成功
                    if(insert(insertNode,deleteNode)){ 
                        // 返回插入后的成功状态
                        return true;
                    }
                }
            }
            return false;
        }
    
        /** * 同级排序 * @param target 目标节点 * @param prior 前一个节点 * @param next 后一个节点 * @return boolean 插入状态 */
        @Override
        public boolean siblingSort(Node target, int prior, int next) { 
            // 如果共同的目标节点存在
            if(target != null){ 
                // 加载同级节点
                descendantSequence.loadNodeArray(target);
                // 如果数据范围有效，并且前一个节点总是小于后一个节点
                if(prior > -1 && prior <= (descendantSequence.length() - 1) && next > -1 && next <= (descendantSequence.length() - 1) && prior < next){ 
                    if(descendantSequence.siblingSort(prior,next)){ 
                        return true;
                    }
                }
            }
            return false;
        }
    
        /** * 节点数组深拷贝 * @param ancestors 父辈节点数组 * @return NodeArray */
        private NodeArray deepCopy(NodeArray ancestors) { 
            NodeArray ancestorSequence = new NodeArray();
            ancestorSequence.setSize(ancestors.getSize());
            ancestorSequence.setILength(ancestors.getILength());
            // 此处采取的是克隆方法
            ancestorSequence.setPList(ancestors.getPList().clone());
            return ancestorSequence;
        }
        
    }

Node

package com.lyc.closure.closureTable.core;
    
    import com.lyc.closure.common.CommonConstant;
    import com.lyc.closure.closureTable.core.entity.Closure;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    import com.lyc.closure.closureTable.print.ConsolePrinter;
    import com.lyc.closure.closureTable.print.Printer;
    import com.lyc.closure.common.ClosureCommonConstant;
    import lombok.AllArgsConstructor;
    import lombok.Builder;
    import lombok.Getter;
    import lombok.Setter;
    import lombok.extern.slf4j.Slf4j;
    
    import java.util.Arrays;
    
    /** * @author: 张侦毅 * @date: 2019/6/12 16:57 * @description: 链表的Node节点 **/
    @Slf4j
    @Getter
    @Setter
    @Builder
    @AllArgsConstructor
    public class Node { 
    
        // 数据域
        private Long data;
        // 指针域数组
        private NodeArray nextArray;
        // 节点深度
        private int depth;
        // 记录该节点的所有父辈路径
        private NodeArray ancestors;
        // 缓存打印器
        private Printer printer;
    
        /** * 通过构造函数初始化一个空的节点数组 */
        public Node() { 
            init();
        }
    
        /** * 含有数据域的构造函数 * @param data 数据域 */
        public Node(Long data) { 
            // 初始化节点数据
            this.data = data;
            // 初始化节点NodeArray对象
            init();
        }
    
        /** * 初始化NodeArray对象 */
        private void init(){ 
            // 初始化节点数组
            Node[] INIT_NODE_ARRAY = new Node[ClosureCommonConstant.Closure.INIT_CAPACITY];
            // 初始化NodeArray
            NodeArray nodeArray = NodeArray.builder()
                    .size(ClosureCommonConstant.Closure.INIT_CAPACITY)
                    .pList(INIT_NODE_ARRAY)
                    .iLength(ClosureCommonConstant.Closure.INIT_DATA_LENGTH)
                    .build();
            // 将节点数组添加到节点数组域中
            this.setNextArray(nodeArray);
            // 初始化父辈节点数组
            Node[] INIT_ANCESTOR_ARRAY = new Node[ClosureCommonConstant.Closure.INIT_CAPACITY];
            // 初始化NodeArray
            NodeArray ancestorArray = NodeArray.builder()
                    .size(ClosureCommonConstant.Closure.INIT_CAPACITY)
                    .pList(INIT_ANCESTOR_ARRAY)
                    .iLength(ClosureCommonConstant.Closure.INIT_DATA_LENGTH)
                    .build();
            // 将父辈节点数组添加到父辈节点数组域中
            this.setAncestors(ancestorArray);
        }
    
        /** * 打印节点数组中的数据 */
        public void traverse() { 
            // 获取节点数组
            Node[] pList = this.nextArray.getPList();
            // 获取节点数组长度
            int length = this.nextArray.getILength();
            // 如果节点数组不为空
            if(length > 0){ 
                // 循环遍历所有的数据
                for(int i = 0; i < length; i ++) { 
                    // 在控制台中打印节点数组
                    log.info(pList[i].getData().toString());
                }
            }
        }
    
        /** * 前序遍历（默认含有控制台打印器） */
        public void frontShow() { 
            // 默认含有一个控制台打印器
            ConsolePrinter consolePrinter = new ConsolePrinter();
            // 递归调用遍历
            frontShow(this,consolePrinter);
        }
    
        /** * 使用函数打印 * @param printer 打印器 */
        public void frontShow(Printer printer) { 
            // 如果打印器不为空，则执行打印器遍历方法，否则不予执行
            if(printer != null){ 
                // 缓存当前打印器
                this.printer = printer;
                // 使用打印器进行前序遍历
                frontShow(this,printer);
            }
        }
    
        /** * 默认含有控制台打印器 * @param ele 目标节点 */
        public void frontShow(Node ele){ 
            // 获取当前节点的父辈路径
            String ancestorsPath = getAncestorsPath(ele);
            // 先打印当前节点
            log.info("当前节点的值：{},节点路径：{}",ele.getData(),ancestorsPath);
            // 默认含有一个控制台打印器
            ConsolePrinter consolePrinter = new ConsolePrinter();
            // 打印节点ClosureTable关系
            nodeClosureTableTraverse(this,consolePrinter);
            // 依次遍历后面各个节点
            frontShowTraverse(ele,consolePrinter);
        }
    
        /** * 前序遍历目标节点下的所有子孙节点 * @param ele 目标节点 * @param printer 打印器 */
        public void frontShow(Node ele, Printer printer){ 
            // 获取当前节点的父辈路径
            String ancestorsPath = getAncestorsPath(ele);
            // 先打印当前节点
            log.info("当前节点的值：{},节点路径：{}",ele.getData(),ancestorsPath);
            // 打印节点ClosureTable关系
            nodeClosureTableTraverse(this,printer);
            // 依次遍历后面各个节点
            frontShowTraverse(ele,printer);
        }
    
        /** * 打印节点ClosureTable关系 * @param ele 目标节点 * @param printer 打印器 */
        private void nodeClosureTableTraverse(Node ele, Printer printer) { 
            // 获取父辈节点数组
            NodeArray ancestors = ele.getAncestors();
            // 计数器
            int count = 0;
            // 打印第一条信息
            printer.print(count,ele.getDepth(),new Closure(ele.getData(),ele.getData(),count));
            //log.info("索引：{}，距离：{},序列化：{}",count,ele.getDepth(),new ClosureTable(ele.getData(),ele.getData(),count).toString());
            // 如果数据存在
            if(ancestors.getILength() > 0){ 
                // 获取数据的有效集合，该集合是一个有序序列
                Node[] validAncestors = Arrays.copyOf(ancestors.getPList(),ancestors.getILength());
                // 装数组转换成List集合，该集合是一个有序序列（大于0是因为根节点无需打印）
                for(int i = validAncestors.length - 1; i > 0; i --){ 
                    // 由于第一条信息已经被打印，所以计数器先自增，再打印
                    count ++;
                    // 打印
                    printer.print(count,ele.getDepth(),new Closure(validAncestors[i].getData(),ele.getData(),count));
                    //log.info("索引：{}，距离：{},序列化：{}",count,ele.getDepth(),new ClosureTable(validAncestors[i].getData(),ele.getData(),count).toString());
                }
            }
        }
    
        /** * 递归前序遍历目标节点数组中的节点 * @param ele 目标节点 * @param printer 打印器 */
        private void frontShowTraverse(Node ele, Printer printer) { 
            // 获取节点数组
            Node[] pList = ele.getNextArray().getPList();
            // 获取节点数组长度
            int length = ele.getNextArray().getILength();
            // 如果节点数组不为空
            if(length > 0){ 
                // 循环遍历所有的节点
                for(int i = 0; i < length; i ++) { 
                    // 获取当前节点
                    Node temp = pList[i];
                    // 递归，调用前序遍历
                    // 如果打印器不为空，则使用自定义打印器
                    if(printer != null){ 
                        temp.frontShow(temp,printer);
                    } else {  // 否则使用默认打印器，也就是说在控制台中进行打印
                        temp.frontShow();
                    }
                }
            }
        }
    
        /** * 获取当前节点的父辈路径 * @param ele 目标节点 * @return String */
        private String getAncestorsPath(Node ele) { 
            // 获取当前节点的父辈节点数组
            Node[] ancestors = copyNodeArray(ele);
            // 创建路径字符串
            StringBuilder ancestorsPath = new StringBuilder();
            // 循环遍历父节点，拼接字符串（这里需要注意的是，跳过第一个节点root节点）
            for(int i = 1; i < ancestors.length; i ++){ 
                // 获取缓存节点
                Node temp = ancestors[i];
                // 拼接父辈路径节点字符串
                ancestorsPath.append(temp.getData());
                // 添加分隔符
                ancestorsPath.append(CommonConstant.Separators.DOT);
            }
            // 如果ancestorsPath中含有数据
            if(ancestors.length > 1){ 
                // 去掉最后一个分隔符
                ancestorsPath.deleteCharAt(ancestorsPath.lastIndexOf(CommonConstant.Separators.DOT));
            }
            // 将路径转换成字符串，然后返回
            return ancestorsPath.toString();
        }
    
        /** * 拷贝有效的父辈节点数组 * @param ele 目标节点 * @return Node[] */
        private Node[] copyNodeArray(Node ele) { 
            // 获取NodeArray容器
            Node[] nodeArrayContainer = ele.getAncestors().getPList();
            // 从容器中复制有效数据，并返回
            return Arrays.copyOf(nodeArrayContainer,ele.getAncestors().getILength());
        }
    
    }

ConsolePrinter

package com.lyc.closure.closureTable.print;
    
    import com.lyc.closure.closureTable.core.entity.Closure;
    import lombok.extern.slf4j.Slf4j;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 15:24 * @description: 控制台打印器实现类 **/
    @Slf4j
    public class ConsolePrinter implements Printer { 
    
        /** * 打印函数实现方法 * @param index 索引值 * @param depth 距离 * @param closureTable closureTable */
        @Override
        public void print(int index, int depth, Closure closureTable) { 
            log.info("索引：{}，距离：{},序列化：{}",index,depth,closureTable.toString());
        }
    
    }

Printer

package com.lyc.closure.closureTable.print;
    
    import com.lyc.closure.closureTable.core.entity.Closure;
    
    /** * @author: 张侦毅 * @date: 2019/6/16 15:21 * @description: 打印器函数 **/
    @FunctionalInterface
    public interface Printer { 
    
        // 打印
        void print(int index, int depth, Closure closureTable);
    
    }

ClosureCommonConstant

package com.lyc.closure.common;
    
    /** * @author: 张天敏 * @date: 2019/6/5 9:15 * @description: 系统常量 **/
    public class ClosureCommonConstant { 
    
        /** * Closure Table */
        public interface Closure{ 
            // 初始化数组容量
            int INIT_ARRAY_SIZE = 0;
            // 初始化数据容量
            int INIT_DATA_LENGTH = 0;
            // 节点数组初始容量
            int INIT_CAPACITY = 8;
            // 加载因子
            float DEFAULT_LOAD_FACTOR = 0.75f;
            // 根节点（parent为0的节点）
            Long ROOT_PARENT = 0L;
        }
    
        /** * 定义实体类中的字段属性 */
        public interface Entity{ 
            String ID = "id";
            String PARENT_ID = "parent_id";
        }
    
    }

CommonConstant

package com.lyc.closure.common;
    
    /** * @author: 张天敏 * @date: 2019/6/5 9:15 * @description: 系统常量 **/
    public class CommonConstant { 
    
        /** * RabbitMQ系统常量，用于规范相关模块间的通信队列 * @author: 张天敏 * @date: 2019/6/5 9:15 */
        public interface RabbitMQ{ 
            // 产品消息队列
            String PRODUCT = "product";
        }
    
        /** * 分隔符 */
        public interface Separators{ 
            // 反斜杠
            String BACK_SLASH = "\\";
            // 斜杠
            String SLASH = "/";
            // 横杠
            String WHIPPLETREE = "-";
            // 点
            String DOT = ".";
            // 下划线
            String UNDERLINE = "_";
            // $符
            String DOLLAR = "$";
        }
    
    }

## 测试源码 ##

ClosureTableLinkedListCRUDTest

package com.lyc.closure.closureTable;
    
    import com.lyc.closure.closureTable.core.ClosureTableLinkedList;
    import com.lyc.closure.closureTable.core.ClosureTableLinkedListImpl;
    import com.lyc.closure.closureTable.core.Node;
    import lombok.extern.slf4j.Slf4j;
    import org.junit.Before;
    import org.junit.Test;
    
    /** * @author: 张天敏 * @date: 2019/6/16 10:24 * @description: ClosureTable测试类 **/
    @Slf4j
    public class ClosureTableLinkedListCRUDTest { 
    
        // 节点广义表
        ClosureTableLinkedList closureTableLinkedList = new ClosureTableLinkedListImpl();
        // 缓存节点
        Node temp;
        Node tempNode13;
    
        /** * 初始化数据 */
        @Before
        public void initDB(){ 
            // 插入的数据模型
            /* * 测试数据如下: * * 0 * / \ * ................ * 1 11 * | / \ * 2 12 13 * / | \ * 3 4 5 * / \ * 6 7 * / / \ * 8 9 10 */
            // 创建根节点
            Node root = closureTableLinkedList.init();
            // 依次创建各个节点
            Node node1 = new Node(1L);
            Node node2 = new Node(2L);
            Node node3 = new Node(3L);
            Node node4 = new Node(4L);
            Node node5 = new Node(5L);
            Node node6 = new Node(6L);
            Node node7 = new Node(7L);
            Node node8 = new Node(8L);
            Node node9 = new Node(9L);
            Node node10 = new Node(10L);
            Node node11 = new Node(11L);
            Node node12 = new Node(12L);
            Node node13 = new Node(13L);
            // 依次插入各个节点
            // 第一层级
            closureTableLinkedList.insert(root,node1);
            closureTableLinkedList.insert(root,node11);
            // 第二层级
            closureTableLinkedList.insert(node1,node2);
            // 第三层级
            closureTableLinkedList.insert(node2,node3);
            closureTableLinkedList.insert(node2,node4);
            closureTableLinkedList.insert(node2,node5);
            closureTableLinkedList.insert(node11,node12);
            closureTableLinkedList.insert(node11,node13);
            // 第四层级
            closureTableLinkedList.insert(node5,node6);
            closureTableLinkedList.insert(node5,node7);
            // 第五层级
            closureTableLinkedList.insert(node6,node8);
            closureTableLinkedList.insert(node7,node9);
            closureTableLinkedList.insert(node7,node10);
            // 缓存节点2
            temp = node2;
            // 缓存节点13
            tempNode13 = node13;
        }
    
        /** * 测试打印效果 */
        @Test
        public void testTraverse(){ 
            closureTableLinkedList.traverse();
        }
    
        /** * 测试打印子孙节点效果 */
        @Test
        public void testDescendantTraverse(){ 
            // 遍历节点2下的所有子孙节点
            closureTableLinkedList.descendantTraverse(temp);
        }
    
        /** * 测试打印目标节点的儿子节点 */
        @Test
        public void testGetChildren(){ 
            // 获取节点2下面的所有孩子节点
            Node[] node2Children = closureTableLinkedList.getChildren(temp);
            // 循环遍历，打印节点数值以及节点深度
            for(int i = 0; i < node2Children.length; i ++){ 
                log.info("当前节点的值为：{}，深度为：{}",node2Children[i].getData(),node2Children[i].getDepth());
            }
        }
    
        /** * 测试删除方法，该方法删除的是节点2 */
        @Test
        public void testDelete(){ 
            // 删除节点2
            closureTableLinkedList.delete(temp);
            // 遍历删除后的结果
            closureTableLinkedList.traverse();
        }
    
        /** * 测试销毁ClosureTable */
        @Test
        public void testDestroy(){ 
            closureTableLinkedList.destroy();
        }
    
        /** * 测试清空ClosureTable */
        @Test
        public void testclean(){ 
            // 清空ClosureTable
            closureTableLinkedList.clean();
            // 链表判空
            if(closureTableLinkedList.empty()){ 
                // 在控制台中打印清空后的信息
                log.info("当前链表已清空");
            }
            // 打印清空后的结果
            closureTableLinkedList.traverse();
        }
    
        @Test
        public void testUpdate(){ 
            // 修改前
            /* * 测试数据如下: * * 0 * / \ * ................ * 1 11 * | / \ * 2 12 13 * / | \ * 3 4 5 * / \ * 6 7 * / / \ * 8 9 10 */
            // 修改后(把2挪到13下面)
            /* * 测试数据如下: * * 0 * / \ * ................ * 1 11 * / \ * 12 13 * | * 2 * / | \ * 3 4 5 * / \ * 6 7 * / / \ * 8 9 10 */
            closureTableLinkedList.update(temp,tempNode13);
            // 遍历删除后的结果
            closureTableLinkedList.traverse();
        }
    
        @Test
        public void testSiblingSort(){ 
            // 修改前
            /* * 测试数据如下: * * 0 * / \ * ................ * 1 11 * | / \ * 2 12 13 * / | \ * 3 4 5 * / \ * 6 7 * / / \ * 8 9 10 */
            // 修改后(将同级的3、5对调)
            /* * 测试数据如下: * * 0 * / \ * ................ * 1 11 * | / \ * 2 12 13 * / | \ * 5 4 3 * / \ * 6 7 * / / \ * 8 9 10 */
            closureTableLinkedList.siblingSort(temp,0,2);
            // 遍历同级排序后的结果
            closureTableLinkedList.traverse();
        }
    
    }

ClosureTableLinkedListTest

DescendantSequenceInitTest

DescendantSequenceTest

package com.lyc.closure.closureTable;
    
    import com.lyc.closure.closureTable.core.Node;
    import com.lyc.closure.closureTable.core.descendant.DescendantSequence;
    import com.lyc.closure.closureTable.core.descendant.DescendantSequenceImpl;
    import com.lyc.closure.common.ClosureCommonConstant;
    import lombok.extern.slf4j.Slf4j;
    import org.junit.Assert;
    import org.junit.Before;
    import org.junit.Test;
    
    /** * @author: 张天敏 * @date: 2019/6/16 10:20 * @description: 子孙节点测试 **/
    @Slf4j
    public class DescendantSequenceTest { 
    
        // 初始化节点数组
        DescendantSequence descendantSequence = new DescendantSequenceImpl();
        // 根节点
        Node node = null;
    
        /** * 初始化节点数组 */
        private void init(){ 
            // 创建根节点
            node = Node.builder()
                    .data(0L)
                    .build();
            // 初始化根节点的节点数组
            descendantSequence.init(node);
        }
    
        /** * 初始化数据 */
        @Before
        public void initDB(){ 
            // 初始化节点数组
            init();
            // 依次初始化各节点 1、2、3、4、5
            Node node1 = new Node(1L);
            Node node2 = new Node(2L);
            Node node3 = new Node(3L);
            Node node4 = new Node(4L);
            Node node5 = new Node(5L);
            // 依次插入各节点数据
            descendantSequence.insert(node1);
            descendantSequence.insert(node2);
            descendantSequence.insert(node3);
            descendantSequence.insert(node4);
            descendantSequence.insert(node5);
        }
    
        /** * 测试数据打印 */
        @Test
        public void testDB(){ 
            // 在控制台中打印数据
            descendantSequence.traverse();
        }
    
        /** * 测试根节点 */
        @Test
        public void testRootNode(){ 
            // 断言数组容量
            Assert.assertEquals(ClosureCommonConstant.Closure.INIT_CAPACITY,node.getNextArray().getPList().length);
            // 断言数组容量数值
            Assert.assertEquals(ClosureCommonConstant.Closure.INIT_CAPACITY,node.getNextArray().getSize());
            // 断言数据长度
            Assert.assertEquals(5,node.getNextArray().getILength());
            // 断言data的值
            Assert.assertEquals(Long.valueOf(0),node.getData());
            // 在控制台中打印节点数组中的数据
            node.traverse();
        }
    
        /** * 测试获取指定位置处的元素 */
        @Test
        public void testGetEle(){ 
            // 创建节点容器
            Node nodeContainer = new Node();
            // 假设获取的是数组中的元素3，位序为2
            descendantSequence.getEle(2,nodeContainer);
            // 断言节点容器中的数据是否正确
            Assert.assertEquals(Long.valueOf(3), nodeContainer.getData());
        }
    
        /** * 测试获取前驱节点 */
        @Test
        public void testPriorEle(){ 
            // 创建当前节点
            Node current = new Node(3L);
            // 创建前驱容器节点
            Node priorContainer = new Node();
            // 假设获取的是数组中的元素3，位序为2
            descendantSequence.priorEle(current,priorContainer);
            // 断言节点容器中的数据是否正确
            Assert.assertEquals(Long.valueOf(2), priorContainer.getData());
        }
    
        /** * 测试获取后继节点 */
        @Test
        public void testNextEle(){ 
            // 创建当前节点
            Node current = new Node(3L);
            // 创建前驱容器节点
            Node nextContainer = new Node();
            // 假设获取的是数组中的元素3，位序为2
            descendantSequence.nextEle(current,nextContainer);
            // 断言节点容器中的数据是否正确
            Assert.assertEquals(Long.valueOf(4), nextContainer.getData());
        }
    
        /** * 获取元素第一次出现时的下标 */
        @Test
        public void testLocateEle(){ 
            // 创建当前节点
            Node current = new Node(3L);
            // 断言元素第一次出现时的下标
            Assert.assertEquals(2, descendantSequence.locateEle(current));
        }
    
        /** * 测试元素判空方法 */
        @Test
        public void testEmpty(){ 
            Assert.assertEquals(false, descendantSequence.isEmpty());
        }
    
        /** * 测试尾部删除方法 */
        @Test
        public void testDelete(){ 
            // 删除尾结点（删除节点5）
            descendantSequence.delete();
            // 遍历删除后的结果（结果为：1、2、3、4）
            descendantSequence.traverse();
        }
    
    }

DescendantSequenceUpdateTest

package com.lyc.closure.closureTable;
    
    import com.lyc.closure.closureTable.core.Node;
    import com.lyc.closure.closureTable.core.descendant.DescendantSequence;
    import com.lyc.closure.closureTable.core.descendant.DescendantSequenceImpl;
    import com.lyc.closure.closureTable.core.entity.NodeArray;
    import lombok.extern.slf4j.Slf4j;
    import org.junit.Assert;
    import org.junit.Before;
    import org.junit.Test;
    
    /** * @author: 张天敏 * @date: 2019/6/16 10:22 * @description: 子孙节点修改测试 **/
    @Slf4j
    public class DescendantSequenceUpdateTest { 
    
        // 初始化节点数组
        DescendantSequence nodeArrayCore = new DescendantSequenceImpl();
        // 根节点
        Node node = null;
    
        /** * 初始化节点数组 */
        private void init(){ 
            // 创建根节点
            node = Node.builder()
                    .data(0L)
                    .build();
            // 初始化根节点的节点数组
            nodeArrayCore.init(node);
        }
    
        /** * 初始化数据 */
        @Before
        public void initDB(){ 
            // 初始化节点数组
            init();
            // 依次初始化各节点 1、2、3、4、5
            Node node1 = new Node(1L);
            Node node2 = new Node(2L);
            Node node3 = new Node(3L);
            Node node4 = new Node(4L);
            Node node5 = new Node(5L);
            // 依次插入各节点数据
            nodeArrayCore.insert(node1);
            nodeArrayCore.insert(node2);
            nodeArrayCore.insert(node3);
            nodeArrayCore.insert(node4);
            nodeArrayCore.insert(node5);
        }
    
        /** * 测试在指定位序上插入节点 */
        @Test
        public void testInsert(){ 
            // 初始化9节点
            Node node9 = new Node(9L);
            // 在4（位序为3）的位置上插入9节点
            nodeArrayCore.insert(3,node9);
            // 遍历插入后的结果，期待的结果：1、2、3、9、4、5
            nodeArrayCore.traverse();
        }
    
        /** * 测试在指定位序上删除节点 */
        @Test
        public void testDelete(){ 
            // 创建删除节点容器
            Node nodeContainer = new Node();
            // 现在的数组数据为：1、2、3、4、5，删除节点4（位序3）上的数据
            nodeArrayCore.delete(3,nodeContainer);
            Assert.assertEquals(Long.valueOf(4),nodeContainer.getData());
            // 在控制台中打印被删除的节点4
            log.info("被删除的节点为：{}",nodeContainer.getData());
            // 在控制台中打印删除后的结果，期待的结果为：1、2、3、5
            nodeArrayCore.traverse();
        }
    
        /** * 测试节点数组扩容 */
        @Test
        public void testDilatation(){ 
            // 创建节点，直至节点总数超过8，为9
            Node node6 = new Node(6L);
            Node node7 = new Node(7L);
            Node node8 = new Node(8L);
            Node node9 = new Node(9L);
            // 依次尾端插入各个节点
            nodeArrayCore.insert(node6);
            nodeArrayCore.insert(node7);
            nodeArrayCore.insert(node8);
            nodeArrayCore.insert(node9);
            // 获取
            NodeArray nodeArray = nodeArrayCore.getNodeArray();
            // 断言数组容量
            Assert.assertEquals(16,nodeArray.getPList().length);
            // 断言数组容量数值
            Assert.assertEquals(16,nodeArray.getSize());
            // 断言数据长度
            Assert.assertEquals(9,nodeArray.getILength());
            // 在控制台中打印现在的节点数组，期待的结果是：1、2、3、4、5、6、7、8、9
            nodeArrayCore.traverse();
            // 在控制台中打印节点中的节点数组，期待的结果是：1、2、3、4、5、6、7、8、9
            node.traverse();
        }
    
    }

# 测试结果 #

上述代码均已测试通过，测试结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1paWTEwNzg2ODkyNzY_size_16_color_FFFFFF_t_70 1]

# 完整项目源码 #

码云[closure-table][]

备注：项目已开源，使用只需要说明出处即可。

[ClosureTable]: https://blog.51cto.com/phpme/2381629
[Laravel _ ClosureTable]: https://segmentfault.com/a/1190000011985100
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1paWTEwNzg2ODkyNzY_size_16_color_FFFFFF_t_70]: /images/20211018/479d55d9774046129bb9f1f218bafd95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1paWTEwNzg2ODkyNzY_size_16_color_FFFFFF_t_70 1]: /images/20211018/16db67b06bba4de18c69902670bf272c.png
[closure-table]: https://gitee.com/zhangzhenyi/closure/tree/master/closure-table