Tree (Composite) is a structural design pattern:
š¤š¤š¤š¤š¤
What is Tree?
Tree is an object that contains Branches and Leaves. We can recursively over the whole tree structure and sum up the results easily.
![Tree diagram](https://user-images.githubusercontent.com/7069077/210161906-3c5d8744-8b5f-4f96-bc24-21f043fce85b.png)
Why use Tree?
It’s neat and clean as you traverse the entire tree to find what you need.
You have no choice but it!
![Tree branches](https://cdn-media-2.freecodecamp.org/w1280/5f9c9f48740569d1a4ca41c4.jpg)
Question: Branch
is like a container, right? How about using the list
to store leaves
?
Answer: Branch
is like a container, but it has a method(def operation
, Same name as leaf’s method) that can delegate the work to all leaves in it. Thus, it is possible to traverse all the leaf’s methods(operations)
When to use Tree?
Question: When do I need to use Tree
?
Answer: When you want to store the leaves hierarchically. Then want to traverse and use the method of leaves(operations)?
- Having many leaves.
- Having the hierarchy of those leaves.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Leaf:
def operation(self):
return "š"
container_1 = []
container_1.append(Leaf())
container_1.append(Leaf())
container_2 = []
container_2.append(Leaf())
wormy_leaf = Leaf()
containers = []
containers.append(container_1)
containers.append(Leaf())
containers.append(wormy_leaf)
containers.append(container_2)
containers.remove(wormy_leaf)
|
Expected Output:
- All leaves are stored hierarchically in an object
- Show the operation of all leaves
1
| [['š', 'š'], 'š', ['š']]
|
How to implement Tree?
Non-Tree implementation:
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
| class Leaf:
def operation(self):
return "š"
def platten(nested_list):
results = []
for item in nested_list:
item_result = platten(item) if isinstance(item, list) else item.operation()
results.append(item_result)
return results
if __name__ == "__main__":
container_1 = []
container_1.append(Leaf())
container_1.append(Leaf())
container_2 = []
container_2.append(Leaf())
wormy_leaf = Leaf()
containers = []
containers.append(container_1)
containers.append(Leaf())
containers.append(wormy_leaf)
containers.append(container_2)
containers.remove(wormy_leaf)
print(platten(containers))
|
Tree Implementation:
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
70
71
72
73
74
75
76
77
| from abc import ABC, abstractmethod
class Component(ABC):
_parent = None
@property
def parent(self):
return self._parent
@parent.setter
def parent(self, parent):
self._parent = parent
def add(self, component):
pass
def remove(self, component):
pass
@abstractmethod
def operation(self):
pass
class Leaf(Component):
"""
A leaf can't have any children.
Leaf objects do the actual work.
"""
def operation(self):
return "š"
class Branch(Component):
"""
A branch can have children(leaves or baby branches) .
Branch objects do nothing but contain children
"""
def __init__(self):
self._children = []
def add(self, component):
component.parent = self
self._children.append(component)
def remove(self, component):
component.parent = None
self._children.remove(component)
def operation(self):
results = []
for child in self._children:
results.append(child.operation())
return results
if __name__ == "__main__":
branch_1 = Branch()
branch_1.add(Leaf())
branch_1.add(Leaf())
branch_2 = Branch()
branch_2.add(Leaf())
wormy_leaf = Leaf()
tree = Branch()
tree.add(branch_1)
tree.add(Leaf())
tree.add(wormy_leaf)
tree.add(branch_2)
tree.remove(wormy_leaf)
print(tree.operation())
|
Source Code