-
Notifications
You must be signed in to change notification settings - Fork 0
/
binarytree.py
163 lines (152 loc) · 5.04 KB
/
binarytree.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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#lesson no : 22 binary tree
#binary tree using linked list
import queue
class Treenode:
def __init__(self, data):
self.data = data
self.leftchild = None
self.rightchild = None
#traversal functions in bt
def preordertraversal(rootnode):
if not rootnode:
return
print(rootnode.data)
preordertraversal(rootnode.leftchild)
preordertraversal(rootnode.rightchild)
def inordertraversal(rootnode):
if not rootnode:
return
preordertraversal(rootnode.leftchild)
print(rootnode.data)
preordertraversal(rootnode.rightchild)
def postordertraversal(rootnode):
if not rootnode:
return
preordertraversal(rootnode.leftchild)
preordertraversal(rootnode.rightchild)
print(rootnode.data)
def levelordertraversal(rootnode):
if not rootnode:
return
else:
customqueue=queue.queue()
customqueue.enqueue(rootnode)
while not(customqueue.isempty()):
root=customqueue.dequeue()
print(root.value.data)
if root.value.leftchild is not None:
customqueue.enqueue(root.value.leftchild)
if root.value.rightchild is not None:
customqueue.enqueue(root.value.rightchild)
#search for a node in bt
def searchbt(rootnode,nodevalue):
if not rootnode:
return
else:
customqueue = queue.queue()
customqueue.enqueue(rootnode)
while not (customqueue.isempty()):
root = customqueue.dequeue()
if root.value.data==nodevalue:
return root.value.data
if root.value.leftchild is not None:
customqueue.enqueue(root.value.leftchild)
if root.value.rightchild is not None:
customqueue.enqueue(root.value.rightchild)
else:
return 'not found'
#insert a node in bt (little issue)
def insertnodebt(rootnode,newnode):
if not rootnode:
return
else:
customqueue = queue.queue()
customqueue.enqueue(rootnode)
while not (customqueue.isempty()):
root = customqueue.dequeue()
if root.value.leftchild is not None:
customqueue.enqueue(root.value.leftchild)
else:
root.value.leftchild=newnode
return 'node successfully inserted'
if root.value.rightchild is not None:
customqueue.enqueue(root.value.rightchild)
else:
root.value.rightchild = newnode
return 'node successfully inserted'
#delete a node from bt (little issue)
def getdeepestnode(rootnode):
if not rootnode:
return
else:
customqueue=queue.queue()
customqueue.enqueue(rootnode)
while not(customqueue.isempty()):
root=customqueue.dequeue()
print(root.value.data)
if root.value.leftchild is not None:
customqueue.enqueue(root.value.leftchild)
if root.value.rightchild is not None:
customqueue.enqueue(root.value.rightchild)
deepestnode=root.value
return deepestnode
def deletedeepestnode(rootnode,dnode):
if not rootnode:
return
else:
customqueue=queue.queue()
customqueue.enqueue(rootnode)
while not(customqueue.isempty()):
root=customqueue.dequeue()
if root.value is dnode:
root.value=None
return
if root.value.rightchild:
if root.value.rightchild==dnode:
root.value.rightchild=None
return
else:
if root.value.leftchild:
if root.value.leftchild == dnode:
root.value.leftchild = None
return
def deletenodebt(rootnode,node):
if not rootnode:
return
else:
customqueue = queue.queue()
customqueue.enqueue(rootnode)
while not (customqueue.isempty()):
root = customqueue.dequeue()
if root.value.data==node:
dnode=getdeepestnode(rootnode)
root.value.data=dnode.data
deletedeepestnode(rootnode,dnode)
return 'sucessfully deleted'
if root.value.leftchild is not None:
customqueue.enqueue(root.value.leftchild)
if root.value.rightchild is not None:
customqueue.enqueue(root.value.rightchild)
return 'faild to delete'
#delete bt
def deletebt(rootnode):
rootnode.data=None
rootnode.leftchild.data = None
rootnode.rightchild.data=None
return "successfully deleted bt"
newbt = Treenode('Drinks')
hot = Treenode('hot')
cold = Treenode('cold')
newbt.leftchild = hot
newbt.rightchild = cold
cofee = Treenode('cofee')
tea = Treenode('tea')
hot.leftchild = cofee
hot.rightchild = tea
alcholic = Treenode('alcholic')
nonalcholic = Treenode('non-alcholic')
cold.leftchild = alcholic
cold.rightchild = nonalcholic
deletebt(newbt)
#insertnodebt(newbt,"hot cofee")
levelordertraversal(newbt)