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
|
#! /usr/bin/env python
#-*- coding: utf-8 -*-
"""
A binary ordered tree implementation.
"""
class Node(object):
"""
Represents a node.
"""
def __init__(self, data):
"""
Initialization.
"""
self.left = None
self.right = None
self.data = data
class OrderedBinaryTree(object):
"""
Represents a binary ordered .
"""
def __init__(self, root):
"""
Initializes the root member.
"""
self.root = root
def addNode(self, data):
"""
Creates a new node and returns it.
"""
return Node(data)
def insert(self, root, data):
"""
Inserts a new data.
"""
if root == None:
# it there isn't any data
# adds it and returns
return self.addNode(data)
else:
# enters into the
if data['article_date'] <= root.data['article_date']:
# if the data is less than the stored one
# goes into the left-sub-
root.left = self.insert(root.left, data)
else:
# processes the right-sub-
root.right = self.insert(root.right, data)
return root
def lookup(self, root, target):
"""
Looks for a value into the .
"""
if root == None:
return 0
else:
# if it has found it...
if target == root.data:
return 1
else:
if target['article_date'] < root.data['article_date']:
# left side
return self.lookup(root.left, target)
else:
# right side
return self.lookup(root.right, target)
def minValue(self, root):
"""
Goes down into the left
arm and returns the last value.
"""
while(root.left != None):
root = root.left
return root.data
def maxValue(self, root):
"""
Goes down into the right
arm and returns the last value.
"""
while(root.right != None):
root = root.right
return root.data
def maxDepth(self, root):
"""
Return the maximum depth.
"""
if root == None:
return 0
else:
# computes the two depths
ldepth = self.maxDepth(root.left)
rdepth = self.maxDepth(root.right)
# returns the appropriate depth
return max(ldepth, rdepth) + 1
def size(self, root):
if root == None:
return 0
else:
return self.size(root.left) + 1 + self.size(root.right)
def pre_order_traversal(self, root, result=[]):
"""
Depth-first. Pre-order traversal.
"""
if root == None:
pass
else:
result.append(root.data)
self.pre_order_traversal(root.left, result)
self.pre_order_traversal(root.right, result)
return result
def in_order_traversal(self, root, result=[]):
"""
Depth-first. In-order traversal.
"""
if root == None:
pass
else:
self.in_order_traversal(root.left, result)
result.append(root.data)
self.in_order_traversal(root.right, result)
return result
def post_order_traversal(self, root, result=[]):
"""
Depth-first. Post-order traversal.
"""
if root == None:
pass
else:
self.post_order_traversal(root.left, result)
self.post_order_traversal(root.right, result)
result.append(root.data)
return result
def __str__(self):
"""
Pretty display.
"""
return ", ".join([article["article_title"] for article in \
self.in_order_traversal(self.root)])
if __name__ == "__main__":
# Point of entry in execution mode.
# create the tree
tree = OrderedBinaryTree()
# add the root node
root = tree.addNode(0)
# ask the user to insert values
for i in range(0, 5):
data = int(input("insert the node value nr %d: " % i))
# insert values
tree.insert(root, data)
tree.printTree(root)
print()
tree.printRevTree(root)
print()
data = int(input("Insert a value to find: "))
if tree.lookup(root, data):
print("found")
else:
print("not found")
print(tree.minValue(root))
print(tree.maxDepth(root))
print(tree.size(root))
|
