Data Structure: Tree

1. Abtract Tree

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

class Tree:
    """Abstract base class representing a tree structure."""

    # -------------------------- nested Position class --------------------------
    class Position:
        """An abstraction representing the location of a single element."""

        def element(self):
            """Return the element stored at this Position."""
            raise NotImplementedError('must be implemented by subclass')

        def __eq__(self, other):
            """Return True if other Position represents the same location."""
            raise NotImplementedError('must be implemented by subclass')

        def __ne__(self, other):
            """Return True if other does not represent the same location."""
            return not (self == other)

    # ---------------- abstract methods that concrete subclass must support ----------------
    def root(self):
        """Return Position representing the tree's root (or None if empty)."""
        raise NotImplementedError('must be implemented by subclass')

    def parent(self, p):
        """Return Position representing p's parent (or None if p is root)."""
        raise NotImplementedError('must be implemented by subclass')

    def num_children(self, p):
        """Return the number of children that Position p has."""
        raise NotImplementedError('must be implemented by subclass')

    def children(self, p):
        """Generate an iteration of Positions representing p's children."""
        raise NotImplementedError('must be implemented by subclass')

    def __len__(self):
        """Return the total number of elements in the tree."""
        raise NotImplementedError('must be implemented by subclass')

    # ---------------- concrete methods implemented in this class ----------------
    def is_root(self, p):
        """Return True if Position p represents the root of the tree."""
        return self.root() == p

    def is_leaf(self, p):
        """Return True if Position p does not have any children."""
        return self.num_children(p) == 0

    def is_empty(self):
        """Return True if the tree is empty."""
        return len(self) == 0

2. ADT Tree

2.1 Position class:

Position is a nested class inside the Tree class that represents the location of a node within the tree rather than exposing the actual node directly.

This class acts as an abstraction layer to:

Each Position object typically represents:

The Position class usually provides operations such as:

Example:

A node containing “A” in the tree may be represented by a Position object. Users interact with Position objects instead of accessing internal _Node objects directly.

Function Description
element(self) Returns the element stored at the current position in the tree. This method is used to access the data contained in a node.
__eq__(self, other) Compares the current position with another position to determine whether they represent the same node in the tree. Returns True if they are equal, otherwise False.
__ne__(self, other) Checks whether two positions are different. This method is the opposite of __eq__(). Returns True if the positions are not the same.
  1. element(self)

This function returns the element stored in the current position.

1
2

def element(self):
    return self._node._element
  1. __eq__(self, other)

This function checks whether two Position objects represent the same location in the tree.

1
2

def __eq__(self, other):
    return type(other) is type(self) and other._node is self._node

The comparison has two conditions:

The function returns:

Using:

1

p1 == p2
  1. __ne__(self, other)

This function checks whether two positions are different.

1
2

def __ne__(self, other):
    return not (self == other)

Equivalent meaning:

Using:

1

p1 != p2

2.2 init(self)

Initializes an empty tree.

1
2
3

def __init__(self):
    self._root = None
    self._size = 0

2.3. _make_position(self, node)

Converts an internal node object into a Position object.

1
2
3
4

def _make_position(self, node):
    if node is None:
        return None
    return self.Position(self, node)

2.4 _validate(self, p)

Validates whether p is a proper Position object.

1
2
3
4

def _validate(self, p):
    if not isinstance(p, self.Position):
        raise TypeError("p must be proper Position type")
    return p._node

Checks if p is an instance of Position.

2.5 root(self)

Returns the root position of the tree.

1
2

def root(self):
    return self._make_position(self._root)

Return

2.6 parent(self, p)

Returns the parent position of p.

1
2
3

def parent(self, p):
    node = self._validate(p)
    return self._make_position(node._parent)

Return

2.7 num_children(self, p)

Returns the number of children of position p.

1
2
3
4

def num_children(self, p):
    node = self._validate(p)
    return len(node._children)
Description

2.8 children(self, p)

Generates all child positions of p.

1
2
3
4
5

def children(self, p):
    node = self._validate(p)

    for child in node._children:
        yield self._make_position(child)

Supports tree traversal and iteration.

2.9 __len__(self)

1
2

def __len__(self):
    return self._size

Using

1

len(tree)

2.10 is_root(self, p)

Checks whether p is the root of the tree.

1
2

def is_root(self, p):
    return self.root() == p

Return

2.11 is_leaf(self, p)

Checks whether p is a leaf node.

1
2

def is_leaf(self, p):
    return self.num_children(p) == 0

Return

2.12 is_empty(self)

Checks whether the tree is empty.

1
2

def is_empty(self):
    return len(self) == 0

Return

2.13 add_root(self, e)

Creates the root node of the tree.

1
2
3
4
5
6
7
8

def add_root(self, e):
    if self._root is not None:
        raise ValueError("Root already exists")

    self._root = self._Node(e)
    self._size = 1

    return self._make_position(self._root)
  1. Checks whether the tree already has a root
  2. If yes, raises an error
  3. Creates a new node storing e
  4. Sets it as the root
  5. Updates tree size to 1

Returns the root position

3. Traversals

3.1 preorder(self)

Performs a preorder traversal of the tree.

Traversal Order

1
2
3
4
5
6
7
8
9
10
11

def _subtree_preorder(self, p):
    yield p

    for child in self.children(p):
        for other in self._subtree_preorder(child):
            yield other

def preorder(self):
    if not self.is_empty():
        for p in self._subtree_preorder(self.root()):
            yield p

Used when the parent node should be processed before its children. Recursive helper function for preorder traversal.

1
2
3

   A
 / | \
B  C  D

return

1

A B C D

3.2 postorder(self)

Performs a postorder traversal of the tree.

Traversal Order

1
2
3
4
5
6
7
8
9
10
11

def _subtree_postorder(self, p):
    for child in self.children(p):
        for other in self._subtree_postorder(child):
            yield other

    yield p

def postorder(self):
    if not self.is_empty():
        for p in self._subtree_postorder(self.root()):
            yield p

Useful when child nodes must be processed before their parent. Recursive helper function for postorder traversal.

1
2
3

   A
 / | \
B  C  D

return

1

B C D A

3.3 inorder(self)

Performs an inorder traversal of the tree.

Traversal Order

  1. Traverse the left subtree
  2. Visit the current node
  3. Traverse the right subtree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def _subtree_inorder(self, p):

    children = list(self.children(p))

    if len(children) > 0:
        for other in self._subtree_inorder(children[0]):
            yield other

    yield p

    if len(children) > 1:
        for other in self._subtree_inorder(children[1]):
            yield other

def inorder(self):
    if not self.is_empty():
        for p in self._subtree_inorder(self.root()):
            yield p

1
2
3

   A
 / | \
B  C  D

return

1

B A C D

Recursive helper function for inorder traversal.

Full code

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

class Tree:
    """ADT base class representing a tree structure."""
    class Position:
        def __init__(self, container, node):
            self._container = container
            self._node = node

        def element(self):
            return self._node._element

        def __eq__(self, other):
            return type(other) is type(self) and other._node is self._node

        def __ne__(self, other):
            return not (self == other)

    class _Node:
        def __init__(self, element, parent=None):
            self._element = element
            self._parent = parent
            self._children = []

    # ---------------- Tree constructor ----------------
    def __init__(self):
        self._root = None
        self._size = 0

    # ---------------- Utility methods ----------------
    def _make_position(self, node):
        if node is None:
            return None
        return self.Position(self, node)

    def _validate(self, p):
        if not isinstance(p, self.Position):
            raise TypeError("p must be proper Position type")
        return p._node

    # ---------------- Main methods ----------------
    def root(self):
        """Return root Position."""
        return self._make_position(self._root)

    def parent(self, p):
        """Return parent Position of p."""
        node = self._validate(p)
        return self._make_position(node._parent)

    def num_children(self, p):
        """Return number of children of p."""
        node = self._validate(p)
        return len(node._children)

    def children(self, p):
        """Generate children Positions."""
        node = self._validate(p)

        for child in node._children:
            yield self._make_position(child)

    def __len__(self):
        """Return total number of elements."""
        return self._size

    # ---------------- Concrete methods ----------------
    def is_root(self, p):
        return self.root() == p

    def is_leaf(self, p):
        return self.num_children(p) == 0

    def is_empty(self):
        return len(self) == 0

    # ---------------- Update methods ----------------
    def add_root(self, e):
        """Create root node."""
        if self._root is not None:
            raise ValueError("Root already exists")

        self._root = self._Node(e)
        self._size = 1

        return self._make_position(self._root)

    def add_child(self, p, e):
        """Add child node to p."""
        node = self._validate(p)

        child = self._Node(e, node)
        node._children.append(child)

        self._size += 1

        return self._make_position(child)

    def _subtree_preorder(self, p):
        yield p

        for child in self.children(p):
            for other in self._subtree_preorder(child):
                yield other

    def preorder(self):
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):
                yield p
                
    def _subtree_postorder(self, p):
        for child in self.children(p):
            for other in self._subtree_postorder(child):
                yield other

        yield p

    def postorder(self):
        if not self.is_empty():
            for p in self._subtree_postorder(self.root()):
                yield p

    def _subtree_inorder(self, p):
        children = list(self.children(p))

        if len(children) > 0:
            for other in self._subtree_inorder(children[0]):
                yield other

        yield p

        if len(children) > 1:
            for other in self._subtree_inorder(children[1]):
                yield other

    def inorder(self):
        if not self.is_empty():
            for p in self._subtree_inorder(self.root()):
                yield p

Using:

1
2
3
4
5
6
7
8
9
10
11
12
13

t = Tree()

r = t.add_root("A")

b = t.add_child(r, "B")
c = t.add_child(r, "C")

print(t.root().element())
print(t.num_children(r))
print(t.is_leaf(b))

for child in t.children(r):
    print(child.element())

Result:

1
2
3
4
5

A
2
True
B
C