如何用一个对象表达一棵树?如何用一个对象遍历一棵树的所有节点?这是我们下面要讨论的一个设计模式——组合模式。该模式其实并不常见,也不常用,但需要解决树形的数据结构时,它是极佳的解决方法。


  • 举例

为末节点Leaf和非末节点即组件Composite声明接口Component
注意到接口又添加删除方法,用来添加单个或多个零件所构的组件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//组件
public abstract class Component {
protected String code;
protected String name;
public Component(String code, String name) {
this.code = code;
this.name = name;
}
public abstract void add(Component component);
public abstract void remove(Component component);
public abstract String printInfo();
}
//末节点
public class Leaf extends Component {
public Leaf(String code, String name) {
super(code, name);
}
//我是纯粹的零件,没有添加删除
@Override
public void add(Component component) {}
@Override
public void remove(Component component) {}
//打印零件信息
@Override
public String printInfo() {
return this.code + ":" + this.name;
}
}
//非末节点
public class Composite extends Component {
public Composite(String code, String name) {
super(code, name);
}
private List<Component> components = new ArrayList<Component>();
//我是组件,必须添加删除
@Override
public void add(Component component) {
components.add(component);
}
@Override
public void remove(Component component) {
components.remove(component);
}
//遍历零件信息
@Override
public String printInfo() {
StringBuffer info = new StringBuffer(this.code + ":" + this.name).append("-->");
for(Component component : this.components)
info.append(component.printInfo()).append(",");
return info.substring(0, info.length()-1);
}
}

咱们可联想一下树形部门结构是咋样的?

1
2
3
4
5
6
7
8
9
10
11
总经理
--- 人事部
--- A组
--- 王五
--- B司
--- 研发部
--- 产品A研发
--- 张三
--- 产品B研发
--- 李四
--- 市场部

于是乎。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class CompositeTemplate {
public static void main(String[] args) {
Component general = new Composite("001", "总经理");
Component hr = new Composite("101", "人事部");
Component tech = new Composite("102", "研发部");
Component market = new Composite("103", "市场部");
Leaf leaf = new Leaf("10101", "张三");
Leaf leaf2 = new Leaf("10202", "李四");
Leaf leaf3 = new Leaf("10303", "王五");
hr.add(leaf);
tech.add(leaf2);
market.add(leaf3);
general.add(hr);
general.add(tech);
general.add(market);
// 001:总经理:{101:人事部:{10101:张三},102:研发部:{10202:李四},103:市场部:{10303:王五}}
System.out.println(general.printInfo());
}
}
  • JDK中的组合模式

JDK中的java.util.ArrayList类中有addAllremoveAll就有组合模式的效果,尽管最后表现出来的依然是一维数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}