forked from logicheap/DataStructures
-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinaryTreeInsertion
94 lines (77 loc) · 2.39 KB
/
BinaryTreeInsertion
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
#This import is of the class Queue that we created in Queue chapter(https://github.com/logicheap/DataStructures/blob/master/Queue.py)
from queue import Queue
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
class BinaryTree:
def __init__(self):
self.root = None
def inorder_traversal(self, root):
if root==None:
return
else:
self.inorder_traversal(root.left)
print(root.data)
self.inorder_traversal(root.right)
def preorder_traversal(self, root):
if root == None:
return
else:
print(root.data)
self.preorder_traversal(root.left)
self.preorder_traversal(root.right)
def postorder_traversal(self, root):
if root == None:
return
else:
self.postorder_traversal(root.left)
self.postorder_traversal(root.right)
print(root.data)
def levelorder_traversal(self, root):
Q = Queue()
if root != None:
Q.enqueue(root)
while(not Q.is_empty()):
temp = Q.dequeue()
print(temp.data)
if temp.left is not None:
Q.enqueue(temp.left)
if temp.right is not None:
Q.enqueue(temp.right)
def insert(self, value):
Q = Queue()
if self.root != None:
Q.enqueue(self.root)
while(len(Q) > 0):
temp = Q.dequeue()
if temp.left is not None:
Q.enqueue(temp.left)
else:
temp.left = Node(value)
break
if temp.right is not None:
Q.enqueue(temp.right)
else:
temp.right = Node(value)
break
T = BinaryTree()
T.root = Node(10)
T.root.left = Node(20)
T.root.right = Node(30)
T.root.left.left = Node(40)
T.root.left.right = Node(50)
T.root.right.right = Node(60)
print("Inorder traversal of tree")
T.inorder_traversal(T.root)
print("Preorder traversal of tree")
T.preorder_traversal(T.root)
print("Postorder traversal of tree")
T.postorder_traversal(T.root)
print("Levelorder traversal of tree")
T.levelorder_traversal(T.root)
value = input("Provide a value for the insertion")
T.insert(value)
print("Levelorder traversal of tree after insertion")
T.levelorder_traversal(T.root)