? 优质资源分享 ?
学习路线指引(点击解锁) | 知识定位 | 人群定位 |
---|---|---|
? 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
转载请注明:xuhss » 通用树形结构的迭代与组合模式实现方案