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
|
#! /usr/bin/env python
#-*- coding: utf-8 -*-
# A binary ordered tree example
class CNode(object):
"""
Represent a node.
"""
def __init__(self, data):
"""
Initialization.
"""
self.left = None
self.right = None
self.data = data
class CBOrdTree(object):
"""
Represent a binary ordered tree.
"""
def __init__(self):
"""
Initializes the root member.
"""
self.root = None
def addNode(self, data):
"""
Creates a new node and returns it.
"""
return CNode(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 tree
if data['article_date'] <= root.data['article_date']:
# if the data is less than the stored one
# goes into the left-sub-tree
root.left = self.insert(root.left, data)
else:
# processes the right-sub-tree
root.right = self.insert(root.right, data)
return root
def lookup(self, root, target):
"""
Looks for a value into the tree.
"""
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 printTree(self, root):
"""
Prints the tree path.
"""
if root == None:
pass
else:
self.printTree(root.left)
print(root.data, end=' ')
self.printTree(root.right)
def printRevTree(self, root):
"""
Prints the tree path in reverse order.
"""
if root == None:
pass
else:
self.printRevTree(root.right)
print(root.data, end=' ')
self.printRevTree(root.left)
if __name__ == "__main__":
# Point of entry in execution mode.
# create the binary tree
BTree = CBOrdTree()
# add the root node
root = BTree.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
BTree.insert(root, data)
BTree.printTree(root)
print()
BTree.printRevTree(root)
print()
data = int(input("Insert a value to find: "))
if BTree.lookup(root, data):
print("found")
else:
print("not found")
print(BTree.minValue(root))
print(BTree.maxDepth(root))
print(BTree.size(root))
|
