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.

 1import queue
 2
 3class TimesNode:
 4    def __init__(self, left, right):
 5        self.left = left
 6        self.right = right
 7        
 8    def eval(self):
 9        return self.left.eval() * self.right.eval()
10    
11    def inorder(self):
12        return "(" + self.left.inorder() + " * " + self.right.inorder() + ")" 
13    
14class PlusNode:
15    def __init__(self, left, right):
16        self.left = left
17        self.right = right
18        
19    def eval(self):
20        return self.left.eval() + self.right.eval()
21    
22    
23    def inorder(self):
24        return "(" + self.left.inorder() + " + " + self.right.inorder() + ")"  
25    
26class NumNode:
27    def __init__(self, num):
28        self.num = num
29        
30    def eval(self):
31        return self.num
32    
33    def inorder(self):
34        return str(self.num)
35 
36def E(q):
37    if q.isEmpty():
38        raise ValueError("Invalid Prefix Expression")
39    
40    token = q.dequeue()
41    
42    if token == "+":
43        return PlusNode(E(q),E(q))
44    
45    if token == "*":
46        return TimesNode(E(q),E(q))
47    
48    return NumNode(float(token))
49    
50def main():
51    x = NumNode(5)
52    y = NumNode(4)
53    p = PlusNode(x,y)
54    t = TimesNode(p, NumNode(6))
55    root = PlusNode(t, NumNode(3))
56    
57    print(root.eval())
58    print(root.inorder())
59    
60    x = input("Please enter a prefix expression: ")
61    
62    lst = x.split()
63    q = queue.Queue()
64    
65    for token in lst:
66        q.enqueue(token)
67        
68    root = E(q)
69    
70    print(root.eval())
71    print(root.inorder())
72    
73        
74    
75if __name__ == "__main__":
76    main()
77

6.2. Binary Search Trees

You can download binary search tree code here.

 1class BinarySearchTree:
 2    # This is a Node class that is internal to the BinarySearchTree class. 
 3    class Node:
 4        def __init__(self,val,left=None,right=None):
 5            self.val = val
 6            self.left = left
 7            self.right = right
 8            
 9        def getVal(self):
10            return self.val
11        
12        def setVal(self,newval):
13            self.val = newval
14            
15        def getLeft(self):
16            return self.left
17        
18        def getRight(self):
19            return self.right
20        
21        def setLeft(self,newleft):
22            self.left = newleft
23            
24        def setRight(self,newright):
25            self.right = newright
26            
27        # This method deserves a little explanation. It does an inorder traversal
28        # of the nodes of the tree yielding all the values. In this way, we get
29        # the values in ascending order.
30        def __iter__(self):
31            if self.left != None:
32                for elem in self.left:
33                    yield elem
34                    
35            yield self.val
36            
37            if self.right != None:
38                for elem in self.right:
39                    yield elem
40
41        def __repr__(self):
42            return "BinarySearchTree.Node(" + repr(self.val) + "," + repr(self.left) + "," + repr(self.right) + ")"            
43            
44    # Below are the methods of the BinarySearchTree class. 
45    def __init__(self, root=None):
46        self.root = root
47        
48    def insert(self,val):
49        self.root = BinarySearchTree.__insert(self.root,val)
50        
51    def __insert(root,val):
52        if root == None:
53            return BinarySearchTree.Node(val)
54        
55        if val < root.getVal():
56            root.setLeft(BinarySearchTree.__insert(root.getLeft(),val))
57        else:
58            root.setRight(BinarySearchTree.__insert(root.getRight(),val))
59            
60        return root
61        
62    def __iter__(self):
63        if self.root != None:
64            return iter(self.root)
65        else:
66            return iter([])
67
68    def __str__(self):
69        return "BinarySearchTree(" + repr(self.root) + ")"
70 
71def main():
72    s = input("Enter a list of numbers: ")
73    lst = s.split()
74    
75    tree = BinarySearchTree()
76    
77    for x in lst:
78        tree.insert(float(x))
79        
80    for x in tree:
81        print(x)
82
83if __name__ == "__main__":
84    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.

  1import random
  2
  3class OrderedTreeSet:
  4    class BinarySearchTree:
  5        # This is a Node class that is internal to the BinarySearchTree class. 
  6        class Node:
  7            def __init__(self,val,left=None,right=None):
  8                self.val = val
  9                self.left = left
 10                self.right = right
 11                
 12            def getVal(self):
 13                return self.val
 14            
 15            def setVal(self,newval):
 16                self.val = newval
 17                
 18            def getLeft(self):
 19                return self.left
 20            
 21            def getRight(self):
 22                return self.right
 23            
 24            def setLeft(self,newleft):
 25                self.left = newleft
 26                
 27            def setRight(self,newright):
 28                self.right = newright
 29                
 30            # This method deserves a little explanation. It does an inorder traversal
 31            # of the nodes of the tree yielding all the values. In this way, we get
 32            # the values in ascending order.
 33            def __iter__(self):
 34                if self.left != None:
 35                    for elem in self.left:
 36                        yield elem
 37                        
 38                yield self.val
 39                
 40                if self.right != None:
 41                    for elem in self.right:
 42                        yield elem
 43
 44            def __repr__(self):
 45                return "BinarySearchTree.Node(" + repr(self.val) + "," + repr(self.left) + "," + repr(self.right) + ")"            
 46                
 47        # Below are the methods of the BinarySearchTree class. 
 48        def __init__(self, root=None):
 49            self.root = root
 50            
 51        def insert(self,val):
 52            self.root = OrderedTreeSet.BinarySearchTree.__insert(self.root,val)
 53            
 54        def __insert(root,val):
 55            if root == None:
 56                return OrderedTreeSet.BinarySearchTree.Node(val)
 57            
 58            if val < root.getVal():
 59                root.setLeft(OrderedTreeSet.BinarySearchTree.__insert(root.getLeft(),val))
 60            else:
 61                root.setRight(OrderedTreeSet.BinarySearchTree.__insert(root.getRight(),val))
 62                
 63            return root
 64            
 65        def __iter__(self):
 66            if self.root != None:
 67                return iter(self.root)
 68            else:
 69                return iter([])
 70
 71        def __str__(self):
 72            return "BinarySearchTree(" + repr(self.root) + ")"
 73            
 74    def __init__(self,contents=None):
 75        self.tree = OrderedTreeSet.BinarySearchTree()
 76        if contents != None:
 77            # randomize the list
 78            indices = list(range(len(contents)))
 79            random.shuffle(indices)
 80            
 81            for i in range(len(contents)):
 82                self.tree.insert(contents[indices[i]])
 83                
 84            self.numItems = len(contents)
 85        else:
 86            self.numItems = 0
 87            
 88    def __str__(self):
 89        pass
 90    
 91    def __iter__(self):
 92        return iter(self.tree)
 93    
 94    # Following are the mutator set methods 
 95    def add(self, item):
 96        pass
 97                
 98    def remove(self, item):
 99        pass
100        
101    def discard(self, item):
102        pass
103        
104    def pop(self):
105        pass
106            
107    def clear(self):
108        pass
109        
110    def update(self, other):
111        pass
112            
113    def intersection_update(self, other):
114        pass
115            
116    def difference_update(self, other):
117        pass
118                
119    def symmetric_difference_update(self, other):
120        pass
121                
122    # Following are the accessor methods for the HashSet  
123    def __len__(self):
124        pass
125    
126    def __contains__(self, item):
127        pass
128    
129    # One extra method for use with the HashMap class. This method is not needed in the 
130    # HashSet implementation, but it is used by the HashMap implementation. 
131    def __getitem__(self, item):
132        pass      
133        
134    def not__contains__(self, item):
135        pass
136    
137    def isdisjoint(self, other):
138        pass
139    
140    
141    def issubset(self, other):
142        pass
143            
144    
145    def issuperset(self, other):
146        pass
147    
148    def union(self, other):
149        pass
150    
151    def intersection(self, other):
152        pass
153    #done
154    def difference(self, other):
155        pass
156    
157    def symmetric_difference(self, other):
158        pass
159    
160    def copy(self):
161        pass
162    
163    # Operator Definitions
164    def __or__(self, other):
165        pass
166    
167    def __and__(self,other):
168        pass
169    
170    def __sub__(self,other):
171        pass
172    
173    def __xor__(self,other):
174        pass
175    
176    def __ior__(self,other):
177        pass
178    
179    def __iand__(self,other):
180        pass
181    
182    def __ixor(self,other):
183        pass    
184    
185    def __le__(self,other):
186        pass
187    
188    def __lt__(self,other):
189        pass
190    
191    def __ge__(self,other):
192        pass
193    
194    def __gt__(self,other):
195        pass
196    
197    def __eq__(self,other):
198        pass      
199                
200            
201    
202 
203def main():
204    s = input("Enter a list of numbers: ")
205    lst = s.split()
206    
207    tree = OrderedTreeSet()
208    
209    for x in lst:
210        tree.add(float(x))
211        
212    for x in tree:
213        print(x)
214
215if __name__ == "__main__":
216    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.

  1import orderedtreeset
  2
  3def main():
  4    s = orderedtreeset.OrderedTreeSet(list(range(100)))
  5    
  6    t = orderedtreeset.OrderedTreeSet(list(range(10,20)))
  7    
  8    u = orderedtreeset.OrderedTreeSet(list(range(10,20)))
  9    
 10    if len(t) == len(u) and len(t) == 10:
 11        print("Test 1 Passed")
 12    else:
 13        print("Test 1 Failed")
 14        
 15    s.intersection_update(t)
 16    
 17    if len(s) == 10:
 18        print("Test 2 Passed")
 19    else:
 20        print("Test 2 Failed")
 21        
 22    s = orderedtreeset.OrderedTreeSet(list(range(100)))
 23    
 24    t.update(s)
 25    
 26    if len(s) == len(t):
 27        print("Test 3 Passed")
 28    else:
 29        print("Test 3 Failed")
 30        
 31    t.clear()
 32    t.update(u)
 33    
 34    if len(t) == len(u):
 35        print("Test 4 Passed")
 36    else:
 37        print("Test 4 Failed")
 38        
 39    s.difference_update(t)
 40    
 41    test5Passed = True
 42    test6Passed = True
 43    
 44    for x in range(1,10):
 45        if x in s:
 46            pass
 47        else:
 48            test5Passed = False
 49            print("Test 5 Failed on",x)
 50            
 51        if x not in s:
 52            test6Passed = False
 53            print("Test 6 Failed on",x)
 54            
 55    if test5Passed:
 56        print("Test 5 Passed")
 57    
 58    if test6Passed:
 59        print("Test 6 Passed")
 60        
 61
 62    test7Passed = True
 63    test8Passed = True
 64    
 65    for x in range(20,100):
 66        if x in s:
 67            pass
 68        else:
 69            test7Passed = False
 70            print("Test 7 Failed on",x)
 71            
 72        if x not in s:
 73            test8Passed = False
 74            print("Test 8 Failed on",x)
 75            
 76    if test7Passed:
 77        print("Test 7 Passed")
 78    
 79    if test8Passed:
 80        print("Test 8 Passed")   
 81        
 82    x = orderedtreeset.OrderedTreeSet(["a","b","c","d","e","f","g","h","i","j","k"])
 83    
 84    y = orderedtreeset.OrderedTreeSet(["c","d","e","l","m","n"])
 85    
 86    z = x.difference(y)
 87    
 88    if len(z) == 8:
 89        print("Test 9 Passed")
 90    else:
 91        print("Test 9 Failed")
 92        
 93    test10Passed = True
 94    
 95    for item in z:
 96        if item not in ["a","b","f","g","h","i","j","k"]:
 97            test10Passed = False
 98            print("Test 10 Failed on", x)
 99            
100    if test10Passed:
101        print("Test 10 Passed")
102        
103    if z.issubset(x):
104        print("Test 11 Passed")
105    else:
106        print("Test 11 Failed")
107        
108    if x.issuperset(z):
109        print("Test 12 Passed")
110    else:
111        print("Test 12 Failed")
112        
113    if z == y:
114        print("Test 13 Failed")
115    else:
116        print("Test 13 Passed")
117        
118    if z == z:
119        print("Test 14 Passed")
120    else:
121        print("Test 14 Failed")
122        
123    r = z.copy()
124    
125    if r == z:
126        print("Test 15 Passed")
127    else:
128        print("Test 15 Failed")
129        
130    z = orderedtreeset.OrderedTreeSet(list(range(50)))
131        
132    for item in range(50):
133        z.discard(item)
134        
135    if len(z) == 0:
136        print("Test 16 Passed")
137    else:
138        print("Test 16 Failed")    
139        
140    z = orderedtreeset.OrderedTreeSet(list(range(50)))
141        
142    lastItem = -99999999999999999999999999999
143    test17Passed = True
144    
145    for item in z:
146        if lastItem >= item:
147            print("Test 17 Failed with ", lastItem, "and", item, "out of order.")
148            test17Passed = False
149            
150        lastItem = item
151            
152    if test17Passed:
153        print("Test 17 Passed")  
154        
155    for item in range(25):
156        z.remove(item)  
157    
158    lastItem = -99999999999999999999999999999
159    test18Passed = True
160    
161    for item in z:
162        if lastItem >= item:
163            print("Test 18 Failed with ", lastItem, "and", item, "out of order.")
164            test18Passed = False
165            
166        lastItem = item
167            
168    if test18Passed:
169        print("Test 18 Passed") 
170        
171    if len(z) == 25:
172        print("Test 19 Passed")
173    else:
174        print("Test 19 Failed")       
175
176    
177if __name__ == "__main__":
178    main()
179

6.6. Figures from Text

../_images/fib.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