-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbinary_tree.py
142 lines (92 loc) · 3.7 KB
/
binary_tree.py
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
'''
by Adrian Statescu <adrian@thinkphp.ro>
Twitter: @thinkphp
G+ : http://gplus.to/thinkphp
MIT Style License
'''
'''
Binary Search Tree
------------------
Trees can come in many different shapes, and they can vary in the number of children allowed per node or in the way
they organize data values within the nodes. One of the most commonly used trees in computer science is the binary tree.
A binary tree is a tree in which each node can have at most two children. On child is identified as the left child and
the other as the right child. The topmost node of the tree is known as the root node.It provides the single acccess point
into the structure. The root node is the only node in the tree that does not have an incoming edge (an edge directed towart it)
By definition every non=empty tree must have contain a root node.
'''
class Node:
def __init__(self,info): #constructor of class
self.info = info #information for node
self.left = None #left leef
self.right = None #right leef
self.level = None #level none defined
def __str__(self):
return str(self.info) #return as string
class searchtree:
def __init__(self): #constructor of class
self.root = None
def create(self,val): #create binary search tree nodes
if self.root == None:
self.root = Node(val)
else:
current = self.root
while 1:
if val < current.info:
if current.left:
current = current.left
else:
current.left = Node(val)
break;
elif val > current.info:
if current.right:
current = current.right
else:
current.right = Node(val)
break;
else:
break
def bft(self): #Breadth-First Traversal
self.root.level = 0
queue = [self.root]
out = []
current_level = self.root.level
while len(queue) > 0:
current_node = queue.pop(0)
if current_node.level > current_level:
current_level += 1
out.append("\n")
out.append(str(current_node.info) + " ")
if current_node.left:
current_node.left.level = current_level + 1
queue.append(current_node.left)
if current_node.right:
current_node.right.level = current_level + 1
queue.append(current_node.right)
print "".join(out)
def inorder(self,node):
if node is not None:
self.inorder(node.left)
print node.info
self.inorder(node.right)
def preorder(self,node):
if node is not None:
print node.info
self.preorder(node.left)
self.preorder(node.right)
def postorder(self,node):
if node is not None:
self.postorder(node.left)
self.postorder(node.right)
print node.info
tree = searchtree()
arr = [8,3,1,6,4,7,10,14,13]
for i in arr:
tree.create(i)
print 'Breadth-First Traversal'
tree.bft()
print 'Inorder Traversal'
tree.inorder(tree.root)
print 'Preorder Traversal'
tree.preorder(tree.root)
print 'Postorder Traversal'
tree.postorder(tree.root)