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
|
# -*- coding: utf-8 -*-
# A binary ordered tree example
class CNode(object):
left , right, data = None, None, 0
def __init__(self, data):
# initializes the data members
self.left = None
self.right = None
self.data = data
class CBOrdTree(object):
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 left
# arm and returns the last value
while(root.right != None):
root = root.right
return root.data
def maxDepth(self, root):
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__":
# 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)
print()
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))
|
