-
Notifications
You must be signed in to change notification settings - Fork 26
Expand file tree
/
Copy pathtree_sort.py
More file actions
48 lines (42 loc) · 1.31 KB
/
Copy pathtree_sort.py
File metadata and controls
48 lines (42 loc) · 1.31 KB
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
class BinaryTreeNode(object):
#initial values for value,left and right
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# inserting a new node in the binary tree
def insert(tree, item):
# if no initial element in the tree
if tree == None:
tree = BinaryTreeNode(item)
else:
if (item < tree.value):
# if left branch of the tree is empty
if (tree.left == None):
tree.left = BinaryTreeNode(item)
else:
insert(tree.left, item)
else:
# if right branch of the tree is empty
if (tree.right == None):
tree.right = BinaryTreeNode(item)
else:
insert(tree.right, item)
return tree
# funtion for the inorder traversal of the binary tree
def in_order_traversal(tree,a):
if (tree.left != None):
in_order_traversal(tree.left,a)
a.append(tree.value)
if (tree.right != None):
in_order_traversal(tree.right,a)
def tree_sort(x):
# root node
t = insert(None, x[0]);
# inserting all elements in the binary tree
for i in x[1:]:
insert(t,i)
# the results of the inorder traversal of a binary tree is a sorted
a = []
in_order_traversal(t,a)
return a