王李峰

王李峰

关注
发信
关注(28)粉丝(399)

通用树形结构的迭代与组合模式实现方案

日常开发过程过程中。树形结构运用的非常频繁。

例如：公司组织结构、各种分类结构、分组结构等等。

通用树形结构的迭代与组合模式实现方案-LMLPHP

通用树形结构的迭代与组合模式实现方案-LMLPHP

通用树形结构的迭代与组合模式实现方案-LMLPHP通用树形结构的迭代与组合模式实现方案-LMLPHP
SET FOREIGN_KEY_CHECKS = 0;

CREATE TABLE IF NOT EXISTS `tbl_sapo_group` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `code` varchar(100) NOT NULL COMMENT '唯一编码',
  `create_time` datetime(3) NOT NULL COMMENT '创建时间',
  `last_update_time` datetime(3) DEFAULT NULL COMMENT '最后更新时间',
  `name` varchar(255) NOT NULL COMMENT '名称',
  `detail` varchar(255) DEFAULT NULL COMMENT '详情',
  `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT '状态:0-无效，1-有效，2-编辑',
  `group_type` varchar(100) NOT NULL COMMENT '组类型',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uni_idx_group_code` (`code`),
  KEY `idx_group_group_type` (`group_type`),
  CONSTRAINT `fk_group_group_type` FOREIGN KEY (`group_type`) REFERENCES `tbl_sapo_group_type` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='组';

CREATE TABLE IF NOT EXISTS `tbl_sapo_group_rel` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `create_time` datetime(3) NOT NULL COMMENT '创建时间',
  `last_update_time` datetime(3) DEFAULT NULL COMMENT '最后更新时间',
  `parent_code` varchar(100) NOT NULL COMMENT '父节点代码，tbl_sapo_group表code',
  `child_code` varchar(100) NOT NULL COMMENT '子节点代码，tbl_sapo_group表code',
  `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT '状态:0-无效，1-有效，2-编辑',
  `group_rel_type` varchar(100) NOT NULL COMMENT '组关系类型代码，来自tbl_sapo_group_rel_type表code',
  `tree_code` varchar(100) NOT NULL COMMENT '树节点代码，tbl_sapo_tree表code',
  PRIMARY KEY (`id`),
  KEY `idx_group_rel_child_code` (`child_code`),
  KEY `idx_group_rel_parent_code` (`parent_code`),
  KEY `idx_group_rel_group_rel_type` (`group_rel_type`),
  KEY `idx_group_rel_tree_code_status_parent_code_child_code` (`tree_code`,`status`,`parent_code`,`child_code`),
  CONSTRAINT `fk_group_rel_child_code` FOREIGN KEY (`child_code`) REFERENCES `tbl_sapo_group` (`code`),
  CONSTRAINT `fk_group_rel_group_rel_type` FOREIGN KEY (`group_rel_type`) REFERENCES `tbl_sapo_group_rel_type` (`code`),
  CONSTRAINT `fk_group_rel_parent_code` FOREIGN KEY (`parent_code`) REFERENCES `tbl_sapo_group` (`code`),
  CONSTRAINT `fk_group_rel_tree_code` FOREIGN KEY (`tree_code`) REFERENCES `tbl_sapo_tree` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='组关系';

CREATE TABLE IF NOT EXISTS `tbl_sapo_group_rel_type` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `code` varchar(100) NOT NULL COMMENT '唯一编码',
  `create_time` datetime(3) NOT NULL COMMENT '创建时间',
  `last_update_time` datetime(3) DEFAULT NULL COMMENT '最后更新时间',
  `name` varchar(255) NOT NULL COMMENT '名称',
  `detail` varchar(255) DEFAULT NULL COMMENT '详情',
  `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT '状态:0-无效，1-有效，2-编辑',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uni_idx_group_rel_type_code` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='组关系类型';

CREATE TABLE IF NOT EXISTS `tbl_sapo_group_type` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `code` varchar(100) NOT NULL COMMENT '唯一编码',
  `create_time` datetime(3) NOT NULL COMMENT '创建时间',
  `last_update_time` datetime(3) DEFAULT NULL COMMENT '最后更新时间',
  `name` varchar(255) NOT NULL COMMENT '名称',
  `detail` varchar(255) DEFAULT NULL COMMENT '详情',
  `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT '状态:0-无效，1-有效，2-编辑',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uni_idx_group_type_code` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='组类型';

CREATE TABLE IF NOT EXISTS `tbl_sapo_tree` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `code` varchar(100) NOT NULL COMMENT '唯一编码',
  `create_time` datetime(3) NOT NULL COMMENT '创建时间',
  `last_update_time` datetime(3) DEFAULT NULL COMMENT '最后更新时间',
  `name` varchar(255) NOT NULL COMMENT '名称',
  `detail` varchar(255) DEFAULT NULL COMMENT '详情',
  `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT '状态:0-无效，1-有效，2-编辑',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uni_idx_tree_code` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='树定义';

CREATE TABLE IF NOT EXISTS `tbl_sapo_tree_group` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `create_time` datetime(3) NOT NULL COMMENT '创建时间',
  `last_update_time` datetime(3) DEFAULT NULL COMMENT '最后更新时间',
  `group_code` varchar(100) NOT NULL COMMENT '组代码，tbl_sapo_group表code',
  `tree_code` varchar(100) NOT NULL COMMENT '树代码，tbl_sapo_tree表code',
  `status` int(10) unsigned NOT NULL DEFAULT 2 COMMENT '状态:0-无效，1-有效，2-编辑',
  `is_root` int(10) unsigned DEFAULT NULL COMMENT '是否根节点:1-根节点,null非根节点',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uni_idx_tree_group_tree_code_is_root` (`tree_code`,`is_root`),
  KEY `idx_tree_group_group_code` (`group_code`),
  CONSTRAINT `fk_tree_group_group_code` FOREIGN KEY (`group_code`) REFERENCES `tbl_sapo_group` (`code`),
  CONSTRAINT `fk_tree_group_tree_code` FOREIGN KEY (`tree_code`) REFERENCES `tbl_sapo_tree` (`code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='树包含的组';

SET FOREIGN_KEY_CHECKS = 1;
建表语句

如图所示关系型数据库模型，基本满足一个系统多颗树、组可以复用的目的。

树的节点可能是一个单独的节点，也可能是一个子树的根。我们需要遍历的时候需要不同节点不同处理，使用【多态】。

但是处理的时候不要区分是何种节点，提供一种【透明化】处理方式，要实现需要引用两个模式：迭代模式、组合模式

老规矩，先引入概念，之后实现。

迭代器模式：

对于不同的集合，我们有不同的遍历方式。有没有一种通用的遍历集合的模式，屏蔽这种差异，该模式就是迭代器。

迭代器模式提供一种方法顺序访问一个聚合对象中的各个元素，而不暴露其内部的表示。

其实说白了，迭代器模式就是通过定义统一操作接口，来屏蔽不同底层的操作逻辑。

如果你能有一个统一的方法访问聚合中的每一个对象，你就可以编写多态的代码和这些聚合搭配。

把游走的任务放在迭代器上，而不是聚合上。这样简化了聚合的接口和实现。责任分配明晰。

符合【单一职责】，如果不使用迭代器模式，集合改变的话，例如由集合变数组，这个类必须改变，遍历方式也跟着改变。

组合模式：

允许你将对象组合成树形结构来表现“整体/部分”层次结构。

组合能让客户以一致的方式处理个别对象以及对象组合。即我们可以忽略对象组合和个别对象之间的差别，而使用相同操作。

组合模式牺牲【单一责任】获取【透明性】，透明性即客户处理组合和叶节点一视同仁。一个节点是组合还是叶节点，对客户是透明的。

 示例：

使用迭代和组合模式实现一种通用的树形结构：

1.核心及组和组的关系。

2.该方案实现了，内部迭代器和外部迭代器。根据实际情况使用。

通用树形结构的迭代与组合模式实现方案-LMLPHP通用树形结构的迭代与组合模式实现方案-LMLPHP
public abstract class GroupComponent {



    public abstract Iterator<GroupComponent> createIterator();

    // 首行字符空几格
    protected abstract String printTreeStr(int i);

    public abstract String getName();

    public  String printTreeStr() {
        return printTreeStr(0);
    };



    // 打印树形解结构
    protected String padding_n(int n) {
        StringBuffer space = new StringBuffer("");
        for (int i = 0; i < n; i++) {
            space.append("-");
        }
        space.append("|");
        return space.toString();
    }

 // 递归获取树形结构
    public static GroupComponent getTree(String groupCode) {
        // 获取通用dao
        CommonDao dao = SpringUtil.getBean(CommonDao.class);
        // 数据库中组详细信息model类
        SapoGroup sapoGroup = dao.getObj(SapoGroup.getInstance().setCode(groupCode));

        // 查询该节点所有儿子
        List<SapoGroupRel> childList = dao.getObjListWithEmpty(SapoGroupRel.getInstance().setParentCode(groupCode));

        // 如果没有子节点，直接新建叶子节点返回
        if (childList == null || childList.size() == 0) {
            LeafGroup leafGroup = new LeafGroup();
            leafGroup.setLeafGroup(sapoGroup);
            return leafGroup;
        } else {
            // 如果有子节点
            Group group = new Group();
            group.setGroupDetail(sapoGroup);
            for (SapoGroupRel rel : childList) {
                // 递归拿到上一个节点
                GroupComponent child = getTree(rel.getChildCode());
                group.getList().add(child);
            }
            return group;
        }
    }
}
GroupComponent
通用树形结构的迭代与组合模式实现方案-LMLPHP通用树形结构的迭代与组合模式实现方案-LMLPHP
public class Group extends GroupComponent {

    Iterator<GroupComponent> iterator = null;

    public List<GroupComponent> list = new ArrayList<GroupComponent>();

    public SapoGroup groupDetail;

    public SapoGroup getGroupDetail() {
        return groupDetail;
    }

    public void setGroupDetail(SapoGroup groupDetail) {
        this.groupDetail = groupDetail;
    }

    /*
     * 打印树形层级结构
     */
    protected String printTreeStr(int i) {
        // 需要打印的字段
        String waitPrintStr = this.groupDetail.getName();

        StringBuilder sb = new StringBuilder();
        sb.append(padding_n(i));
        sb.append(waitPrintStr);
        sb.append("\r\n");

        Iterator<GroupComponent> iterator = list.iterator();

        while (iterator.hasNext()) {
            GroupComponent next = iterator.next();
            // 递归进行遍历
            String printTree = next.printTreeStr(i + 2);
            sb.append(printTree);
        }
        return sb.toString();
    }

    public List<GroupComponent> getList() {
        return list;
    }

    public void setList(List<GroupComponent> list) {
        this.list = list;
    }

    @Override
    public Iterator<GroupComponent> createIterator() {
        if (iterator == null) {
            iterator = new GroupIterator(list.iterator());
        }
        return iterator;
    }

    @Override
    public String getName() {

        return "list: " + groupDetail.getName();
    }

}
Group
通用树形结构的迭代与组合模式实现方案-LMLPHP通用树形结构的迭代与组合模式实现方案-LMLPHP
public class LeafGroup extends GroupComponent {

    private SapoGroup leafGroup;

    public SapoGroup getLeafGroup() {
        return leafGroup;
    }

    public void setLeafGroup(SapoGroup leafGroup) {
        this.leafGroup = leafGroup;
    }

    public Iterator<GroupComponent> createIterator() {
        return new NullIterator();
    }

    protected String printTreeStr(int i) {
        // 关键字段
        String waitPrintStr = this.getLeafGroup().getName();
        return padding_n(i) + waitPrintStr + "\r\n";
    }

    /* (non-Javadoc)
     * @see cn.com.fmsh.nfcos.sapo.biz.testGroup.GroupComponent#getName()
     */
    @Override
    public String getName() {
       return "leaf: "+leafGroup.getName();
    }

}
LeafGroup
通用树形结构的迭代与组合模式实现方案-LMLPHP通用树形结构的迭代与组合模式实现方案-LMLPHP
public class GroupIterator implements Iterator<GroupComponent> {

    Stack<Iterator<GroupComponent>> stack = new Stack<Iterator<GroupComponent>>();

    public GroupIterator(Iterator<GroupComponent> iterator) {
        stack.push(iterator);
    }

    public boolean hasNext() {
        if (stack.isEmpty()) {
            return false;
        } else {
            Iterator<GroupComponent> iterator = stack.peek();
            if (!iterator.hasNext()) {
                stack.pop();
                return hasNext();
            } else {
                return true;
            }
        }

    }


    public GroupComponent next() {
       if(hasNext()) {
           Iterator<GroupComponent> iterator = stack.peek();
           GroupComponent next = iterator.next();
           stack.push(next.createIterator());
           return next;
       }else {
           return null;
       }
    }

}
GroupIterator
通用树形结构的迭代与组合模式实现方案-LMLPHP通用树形结构的迭代与组合模式实现方案-LMLPHP
public class NullIterator implements Iterator<GroupComponent> {

    public GroupComponent next() {
        return null;
    }

    public boolean hasNext() {
        return false;
    }


}
NullIterator

测试程序，遍历树形结构、打印树形结构。

 @Test
    public void Test() {

        // 使用外部迭代器遍历
        GroupComponent tree = Group.getTree("hotel");

        Iterator<GroupComponent> iterator = tree.createIterator();

        while (iterator.hasNext()) {
            GroupComponent next = iterator.next();
            // TODO 遍历操作内容

        }

        System.out.println("----打印树形结构-----");

        // 打印树形结构
        System.err.println(GroupComponent.getTree("hotel").printTreeStr());

    }

通用树形结构的迭代与组合模式实现方案-LMLPHP

本文来自博客园，作者：wanglifeng，转载请注明原文链接：https://www.cnblogs.com/wanglifeng717/p/16363485.html

06-12 09:34
Powered by LMLPHP ©2024 王李峰 0.037505