algorithm/binary_tree2.py at master · SMZCC/algorithm · GitHub

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
#! /usr/bin/env python
#coding:utf-8

# The code is from:http://code.activestate.com/recipes/286239-binary-ordered-tree/
# A binary ordered tree example

classCNode:
left , right, data=None, None, 0

def__init__(self, data):
# initializes the data members
self.left=None
self.right=None
self.data=data


classCBOrdTree:
def__init__(self):
# initializes the root member
self.root=None

defaddNode(self, data):
# creates a new node and returns it
returnCNode(data)

definsert(self, root, data):
# inserts a new data
ifroot==None:
# it there isn't any data
# adds it and returns
returnself.addNode(data)
else:
# enters into the tree
ifdata<=root.data:
# 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)
returnroot

deflookup(self, root, target):
# looks for a value into the tree
ifroot==None:
return0
else:
# if it has found it...
iftarget==root.data:
return1
else:
iftarget<root.data:
# left side
returnself.lookup(root.left, target)
else:
# right side
returnself.lookup(root.right, target)

defminValue(self, root):
# goes down into the left
# arm and returns the last value
while(root.left!=None):
root=root.left
returnroot.data

defmaxDepth(self, root):
ifroot==None:
return0
else:
# computes the two depths
ldepth=self.maxDepth(root.left)
rdepth=self.maxDepth(root.right)
# returns the appropriate depth
returnmax(ldepth, rdepth) +1

defsize(self, root):
ifroot==None:
return0
else:
returnself.size(root.left) +1+self.size(root.right)

defprintTree(self, root):
# prints the tree path
ifroot==None:
pass
else:
self.printTree(root.left)
printroot.data,
self.printTree(root.right)

defprintRevTree(self, root):
# prints the tree path in reverse
# order
ifroot==None:
pass
else:
self.printRevTree(root.right)
printroot.data,
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
foriinrange(0, 5):
data=int(raw_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(raw_input("insert a value to find: "))
ifBTree.lookup(root, data):
print"found"
else:
print"not found"

printBTree.minValue(root)
printBTree.maxDepth(root)
printBTree.size(root)