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

优质资源分享

学习路线指引（点击解锁）	知识定位	人群定位
🧡 Python实战微信订餐小程序 🧡	进阶级	本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。
Python量化交易实战	入门级	手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

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

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

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 menuComponents = new ArrayList();
 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 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 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 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 iterator = null;

 public List list = new ArrayList();

 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 iterator = list.iterator();

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

 public List getList() {
 return list;
 }

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

 @Override
 public Iterator 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 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 {

 Stack> stack = new Stack>();

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

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

 }

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

}

GroupIterator

public class NullIterator implements Iterator {
 
 public GroupComponent next() {
 return null;
 }
 
 public boolean hasNext() {
 return false;
 }
 
 
}

NullIterator

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

 @Test
 public void Test() {

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

 Iterator iterator = tree.createIterator();

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

 }

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

 }

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