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

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

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

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

 

 

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

 

 

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

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("rn");          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 + "rn";     }      /* (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

 

发表评论

相关文章