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

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

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

 

 

 

 

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;

建表语句

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

 

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

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

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

迭代器模式	提供一个方式来遍历集合而无需暴露集合的实现
组合模式	客户可以将对象的集合以及个别对象一视同仁

 

迭代器模式：

迭代器示例：数组实现迭代器     // 迭代器接口interface Iterator { boolean hasNext(); Object next();}// 菜单项class MenuItem { String name; String description; boolean vegetarian; double price; public MenuItem(String name, String description, boolean vegetarian, double price) { this.name = name; this.description = description; this.vegetarian = vegetarian; this.price = price; } // getter,setter方法 public String getName() { return name; }}// 菜单class DinerMenu { static final int MAX_ITEMS = 6; int numberOfItems = 0; MenuItem[] menuItems; public DinerMenu() { menuItems = new MenuItem[MAX_ITEMS]; addItem("红烧狮子头", "江南名菜", true, 50d); addItem("夫妻肺片", "和夫妻没啥关系", true, 70d); } public void addItem(String name, String description, boolean vegetarian, double price) { MenuItem menuItem = new MenuItem(name, description, vegetarian, price); if (numberOfItems >= MAX_ITEMS) { System.out.println("sorry,menu is full"); } else { menuItems[numberOfItems] = menuItem; numberOfItems += 1; } } public MenuItem[] getMenuItems() { return menuItems; } public Iterator createIteator() { return new DinerMenuIterator(menuItems); }}class DinerMenuIterator implements Iterator { MenuItem[] items; int position = 0; public DinerMenuIterator(MenuItem[] items) { this.items = items; } public Object next() { MenuItem menuItem = items[position]; position = position + 1; return menuItem; } public boolean hasNext() { // 数组可能没装满 if (position >= items.length || items[position] == null) { return false; } else { return true; } } public void remove() { if (position <= 0) { throw new IllegalStateException("you can't an item unitl you've done at least on next()"); } if (items[position - 1] != null) { for (int i = position - 1; i < (items.length - 1); i++) { items[i] = items[i + 1]; } items[items.length - 1] = null; } }}// 测试class Test { public static void main(String[] args) { Iterator iterator = (new DinerMenu()).createIteator(); while(iterator.hasNext()){ MenuItem menuItem = (MenuItem) iterator.next(); System.out.println(menuItem.getName()); } }}迭代器模式示例 数组迭代器 1.当然remove可以不实现，因为可能并发remove，迭代器不安全。 我们简单处理抛出java.lang.UnsupportedOperationException 2.java5之后,集合可以使用for/in形式代替了显示的创建迭代器。 for( Object obj: collection){ }

 

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

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

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

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

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

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

 

组合模式：

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

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

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

组合模式示例：         public abstract class MenuComponent { // 操作节点需要方法 public void add(MenuComponent menuComponent) { throw new UnsupportedOperationException(); } public void remove(MenuComponent menuComponent) { throw new UnsupportedOperationException(); } public MenuComponent getChild(int i) { throw new UnsupportedOperationException(); } // 菜单本身方法 public String getName() { throw new UnsupportedOperationException(); } public String getDescription() { throw new UnsupportedOperationException(); } public double getPrice() { throw new UnsupportedOperationException(); } public boolean isVegetarian() { throw new UnsupportedOperationException(); } public void print() { throw new UnsupportedOperationException(); }} MenuComponent public class Menu extends MenuComponent { ArrayList<MenuComponent> menuComponents = new ArrayList<MenuComponent>(); String name; String description; public Menu(String name, String description) { this.name = name; this.description = description; } public void add(MenuComponent menuComponent) { menuComponents.add(menuComponent); } public void remove(MenuComponent menuComponent) { menuComponents.remove(menuComponent); } public MenuComponent getChild(int i) { return (MenuComponent) menuComponents.get(i); } public String getName() { return name; } public String getDescription() { return description; } public void print() { System.out.print("\n" + getName()); System.out.println(", " + getDescription()); System.out.println("---------------------"); Iterator<MenuComponent> iterator = menuComponents.iterator(); while (iterator.hasNext()) { MenuComponent menuComponent = (MenuComponent) iterator.next(); menuComponent.print(); } }} Menu public class MenuItem extends MenuComponent { String name; String description; boolean vegetarian; double price; public MenuItem(String name, String description, boolean vegetarian, double price) { this.name = name; this.description = description; this.vegetarian = vegetarian; this.price = price; } public String getName() { return name; } public String getDescription() { return description; } public double getPrice() { return price; } public boolean isVegetarian() { return vegetarian; } public void print() { System.out.print(" " + getName()); if (isVegetarian()) { System.out.print("(v)"); } System.out.println(", " + getPrice()); System.out.println(" -- " + getDescription()); }} MenuItem public class Waitress { MenuComponent allMenus; public Waitress(MenuComponent allMenus) { this.allMenus = allMenus; } public void printMenu() { allMenus.print(); }} Waitress

 示例：

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

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

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

 

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

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

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

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

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());    }

 

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