6. Trees

When we see a tree in our everyday lives the roots are generally in the ground and the leaves are up in the air. The branches of a tree spread out from the roots in a more or less organized fashion. The word tree is used in Computer Science when talking about a way data may be organized. Trees have some similarilties to the linked list organization found in chapter 4. In a tree there are nodes which have links to other nodes. In a linked list each node has one link, to the next node in the list. In a tree each node may have two or more links to other nodes. A tree is not a sequential data structure. It is organized like a tree, except the root is at the top of tree data structures and the leaves are at the bottom. A tree in computer science is usually drawn inverted when compared to the trees we see in nature. There are many uses for trees in computer science.

In this chapter we’ll explore trees and when it makes sense to build and or use a tree in a program. Not every program will need a tree data structure. Nevertheless, trees are used in many types of programs. A knowledge of them is not only a necessity, proper use of them can greatly simplify some types of programs.

6.1. Abstract Syntax Trees

You can download prefix expression parser and abstract syntax tree code here. You must have access to the queue code from chapter 4 to run this program.

 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
import queue

class TimesNode:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        
    def eval(self):
        return self.left.eval() * self.right.eval()
    
    def inorder(self):
        return "(" + self.left.inorder() + " * " + self.right.inorder() + ")" 
    
class PlusNode:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        
    def eval(self):
        return self.left.eval() + self.right.eval()
    
    
    def inorder(self):
        return "(" + self.left.inorder() + " + " + self.right.inorder() + ")"  
    
class NumNode:
    def __init__(self, num):
        self.num = num
        
    def eval(self):
        return self.num
    
    def inorder(self):
        return str(self.num)
 
def E(q):
    if q.isEmpty():
        raise ValueError("Invalid Prefix Expression")
    
    token = q.dequeue()
    
    if token == "+":
        return PlusNode(E(q),E(q))
    
    if token == "*":
        return TimesNode(E(q),E(q))
    
    return NumNode(float(token))
    
def main():
    x = NumNode(5)
    y = NumNode(4)
    p = PlusNode(x,y)
    t = TimesNode(p, NumNode(6))
    root = PlusNode(t, NumNode(3))
    
    print(root.eval())
    print(root.inorder())
    
    x = input("Please enter a prefix expression: ")
    
    lst = x.split()
    q = queue.Queue()
    
    for token in lst:
        q.enqueue(token)
        
    root = E(q)
    
    print(root.eval())
    print(root.inorder())
    
        
    
if __name__ == "__main__":
    main()
    

6.2. Binary Search Trees

You can download binary search tree code here.

 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
class BinarySearchTree:
    # This is a Node class that is internal to the BinarySearchTree class. 
    class Node:
        def __init__(self,val,left=None,right=None):
            self.val = val
            self.left = left
            self.right = right
            
        def getVal(self):
            return self.val
        
        def setVal(self,newval):
            self.val = newval
            
        def getLeft(self):
            return self.left
        
        def getRight(self):
            return self.right
        
        def setLeft(self,newleft):
            self.left = newleft
            
        def setRight(self,newright):
            self.right = newright
            
        # This method deserves a little explanation. It does an inorder traversal
        # of the nodes of the tree yielding all the values. In this way, we get
        # the values in ascending order.
        def __iter__(self):
            if self.left != None:
                for elem in self.left:
                    yield elem
                    
            yield self.val
            
            if self.right != None:
                for elem in self.right:
                    yield elem

        def __repr__(self):
            return "BinarySearchTree.Node(" + repr(self.val) + "," + repr(self.left) + "," + repr(self.right) + ")"            
            
    # Below are the methods of the BinarySearchTree class. 
    def __init__(self, root=None):
        self.root = root
        
    def insert(self,val):
        self.root = BinarySearchTree.__insert(self.root,val)
        
    def __insert(root,val):
        if root == None:
            return BinarySearchTree.Node(val)
        
        if val < root.getVal():
            root.setLeft(BinarySearchTree.__insert(root.getLeft(),val))
        else:
            root.setRight(BinarySearchTree.__insert(root.getRight(),val))
            
        return root
        
    def __iter__(self):
        if self.root != None:
            return iter(self.root)
        else:
            return iter([])

    def __str__(self):
        return "BinarySearchTree(" + repr(self.root) + ")"
 
def main():
    s = input("Enter a list of numbers: ")
    lst = s.split()
    
    tree = BinarySearchTree()
    
    for x in lst:
        tree.insert(float(x))
        
    for x in tree:
        print(x)

if __name__ == "__main__":
    main()

6.3. Sudoku Test Files

Here are two more sudoku test files. These can be solved if you implement the depth first search as described in chapter 6 of the text.

6.4. OrderedTreeSet

Here is an OrderedTreeSet implementation to get you started with the ordered tree set implementation. This file has an OrderedTreeSet class with a BinarySearchTree class nested inside it.

  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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
import random

class OrderedTreeSet:
    class BinarySearchTree:
        # This is a Node class that is internal to the BinarySearchTree class. 
        class Node:
            def __init__(self,val,left=None,right=None):
                self.val = val
                self.left = left
                self.right = right
                
            def getVal(self):
                return self.val
            
            def setVal(self,newval):
                self.val = newval
                
            def getLeft(self):
                return self.left
            
            def getRight(self):
                return self.right
            
            def setLeft(self,newleft):
                self.left = newleft
                
            def setRight(self,newright):
                self.right = newright
                
            # This method deserves a little explanation. It does an inorder traversal
            # of the nodes of the tree yielding all the values. In this way, we get
            # the values in ascending order.
            def __iter__(self):
                if self.left != None:
                    for elem in self.left:
                        yield elem
                        
                yield self.val
                
                if self.right != None:
                    for elem in self.right:
                        yield elem

            def __repr__(self):
                return "BinarySearchTree.Node(" + repr(self.val) + "," + repr(self.left) + "," + repr(self.right) + ")"            
                
        # Below are the methods of the BinarySearchTree class. 
        def __init__(self, root=None):
            self.root = root
            
        def insert(self,val):
            self.root = OrderedTreeSet.BinarySearchTree.__insert(self.root,val)
            
        def __insert(root,val):
            if root == None:
                return OrderedTreeSet.BinarySearchTree.Node(val)
            
            if val < root.getVal():
                root.setLeft(OrderedTreeSet.BinarySearchTree.__insert(root.getLeft(),val))
            else:
                root.setRight(OrderedTreeSet.BinarySearchTree.__insert(root.getRight(),val))
                
            return root
            
        def __iter__(self):
            if self.root != None:
                return iter(self.root)
            else:
                return iter([])

        def __str__(self):
            return "BinarySearchTree(" + repr(self.root) + ")"
            
    def __init__(self,contents=None):
        self.tree = OrderedTreeSet.BinarySearchTree()
        if contents != None:
            # randomize the list
            indices = list(range(len(contents)))
            random.shuffle(indices)
            
            for i in range(len(contents)):
                self.tree.insert(contents[indices[i]])
                
            self.numItems = len(contents)
        else:
            self.numItems = 0
            
    def __str__(self):
        pass
    
    def __iter__(self):
        return iter(self.tree)
    
    # Following are the mutator set methods 
    def add(self, item):
        pass
                
    def remove(self, item):
        pass
        
    def discard(self, item):
        pass
        
    def pop(self):
        pass
            
    def clear(self):
        pass
        
    def update(self, other):
        pass
            
    def intersection_update(self, other):
        pass
            
    def difference_update(self, other):
        pass
                
    def symmetric_difference_update(self, other):
        pass
                
    # Following are the accessor methods for the HashSet  
    def __len__(self):
        pass
    
    def __contains__(self, item):
        pass
    
    # One extra method for use with the HashMap class. This method is not needed in the 
    # HashSet implementation, but it is used by the HashMap implementation. 
    def __getitem__(self, item):
        pass      
        
    def not__contains__(self, item):
        pass
    
    def isdisjoint(self, other):
        pass
    
    
    def issubset(self, other):
        pass
            
    
    def issuperset(self, other):
        pass
    
    def union(self, other):
        pass
    
    def intersection(self, other):
        pass
    #done
    def difference(self, other):
        pass
    
    def symmetric_difference(self, other):
        pass
    
    def copy(self):
        pass
    
    # Operator Definitions
    def __or__(self, other):
        pass
    
    def __and__(self,other):
        pass
    
    def __sub__(self,other):
        pass
    
    def __xor__(self,other):
        pass
    
    def __ior__(self,other):
        pass
    
    def __iand__(self,other):
        pass
    
    def __ixor(self,other):
        pass    
    
    def __le__(self,other):
        pass
    
    def __lt__(self,other):
        pass
    
    def __ge__(self,other):
        pass
    
    def __gt__(self,other):
        pass
    
    def __eq__(self,other):
        pass      
                
            
    
 
def main():
    s = input("Enter a list of numbers: ")
    lst = s.split()
    
    tree = OrderedTreeSet()
    
    for x in lst:
        tree.add(float(x))
        
    for x in tree:
        print(x)

if __name__ == "__main__":
    main()

6.5. OrderedTreeSet Test Program

Here is an OrderedTreeSet Test Program that provides some tests for the OrderedTreeSet implementation. Your ordered tree set must be saved in a file called orderedtreeset.py so it can be imported into this test program.

  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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
import orderedtreeset

def main():
    s = orderedtreeset.OrderedTreeSet(list(range(100)))
    
    t = orderedtreeset.OrderedTreeSet(list(range(10,20)))
    
    u = orderedtreeset.OrderedTreeSet(list(range(10,20)))
    
    if len(t) == len(u) and len(t) == 10:
        print("Test 1 Passed")
    else:
        print("Test 1 Failed")
        
    s.intersection_update(t)
    
    if len(s) == 10:
        print("Test 2 Passed")
    else:
        print("Test 2 Failed")
        
    s = orderedtreeset.OrderedTreeSet(list(range(100)))
    
    t.update(s)
    
    if len(s) == len(t):
        print("Test 3 Passed")
    else:
        print("Test 3 Failed")
        
    t.clear()
    t.update(u)
    
    if len(t) == len(u):
        print("Test 4 Passed")
    else:
        print("Test 4 Failed")
        
    s.difference_update(t)
    
    test5Passed = True
    test6Passed = True
    
    for x in range(1,10):
        if x in s:
            pass
        else:
            test5Passed = False
            print("Test 5 Failed on",x)
            
        if x not in s:
            test6Passed = False
            print("Test 6 Failed on",x)
            
    if test5Passed:
        print("Test 5 Passed")
    
    if test6Passed:
        print("Test 6 Passed")
        

    test7Passed = True
    test8Passed = True
    
    for x in range(20,100):
        if x in s:
            pass
        else:
            test7Passed = False
            print("Test 7 Failed on",x)
            
        if x not in s:
            test8Passed = False
            print("Test 8 Failed on",x)
            
    if test7Passed:
        print("Test 7 Passed")
    
    if test8Passed:
        print("Test 8 Passed")   
        
    x = orderedtreeset.OrderedTreeSet(["a","b","c","d","e","f","g","h","i","j","k"])
    
    y = orderedtreeset.OrderedTreeSet(["c","d","e","l","m","n"])
    
    z = x.difference(y)
    
    if len(z) == 8:
        print("Test 9 Passed")
    else:
        print("Test 9 Failed")
        
    test10Passed = True
    
    for item in z:
        if item not in ["a","b","f","g","h","i","j","k"]:
            test10Passed = False
            print("Test 10 Failed on", x)
            
    if test10Passed:
        print("Test 10 Passed")
        
    if z.issubset(x):
        print("Test 11 Passed")
    else:
        print("Test 11 Failed")
        
    if x.issuperset(z):
        print("Test 12 Passed")
    else:
        print("Test 12 Failed")
        
    if z == y:
        print("Test 13 Failed")
    else:
        print("Test 13 Passed")
        
    if z == z:
        print("Test 14 Passed")
    else:
        print("Test 14 Failed")
        
    r = z.copy()
    
    if r == z:
        print("Test 15 Passed")
    else:
        print("Test 15 Failed")
        
    z = orderedtreeset.OrderedTreeSet(list(range(50)))
        
    for item in range(50):
        z.discard(item)
        
    if len(z) == 0:
        print("Test 16 Passed")
    else:
        print("Test 16 Failed")    
        
    z = orderedtreeset.OrderedTreeSet(list(range(50)))
        
    lastItem = -99999999999999999999999999999
    test17Passed = True
    
    for item in z:
        if lastItem >= item:
            print("Test 17 Failed with ", lastItem, "and", item, "out of order.")
            test17Passed = False
            
        lastItem = item
            
    if test17Passed:
        print("Test 17 Passed")  
        
    for item in range(25):
        z.remove(item)  
    
    lastItem = -99999999999999999999999999999
    test18Passed = True
    
    for item in z:
        if lastItem >= item:
            print("Test 18 Failed with ", lastItem, "and", item, "out of order.")
            test18Passed = False
            
        lastItem = item
            
    if test18Passed:
        print("Test 18 Passed") 
        
    if len(z) == 25:
        print("Test 19 Passed")
    else:
        print("Test 19 Failed")       

    
if __name__ == "__main__":
    main()
    

6.6. Figures from Text

../_images/fib1.png

Fig. 1: The Call Tree for Computing Fib(5)

../_images/ast.png

Fig. 2: The AST for (5 + 4) * 6 + 3

../_images/binarysearchtree8.png

Fig. 3: An empty BinarySearchTree object

../_images/binarysearchtree7.png

Fig. 4: The Tree After Inserting 5

../_images/binarysearchtree6.png

Fig. 5: The Tree After Inserting 8

../_images/binarysearchtree5.png

Fig. 6: The Tree After Inserting 2

../_images/binarysearchtree4.png

Fig. 7: The Tree After Inserting 1

../_images/binarysearchtree3.png

Fig. 8: The Tree After Inserting 4

../_images/binarysearchtree2.png

Fig. 9: The Tree After Inserting 9

../_images/binarysearchtree1.png

Fig. 10: The Tree After Inserting 6

../_images/binarysearchtree.png

Fig. 11: The Tree After Inserting 7

../_images/binarysearchtreefinal.png

Fig. 12: The Final BinarySearchTree Contents

../_images/binarysearchtreedelete0.png

Fig. 13: The Tree After Deleting 9

../_images/binarysearchtreedelete1.png

Fig. 14: The Tree After Deleting 6

../_images/binarysearchtreedelete2.png

Fig. 15: The Tree After Deleting 5