In This Post,I would like to explain the simple structure on how to
create binary search tree using python classes.In binary search tree,
left child is always smaller than parent and right child is
greater than parent.This property makes it easy for operations like
addition,search,deletion of node.In Real world,you may have seen of phone
directory in which we search by getting common string numbers.
class Node:
#initialize node structure
def __init__(self,data):
self.data = data
self.left = None
self.right = None
#get minimum node from tree starting from this node
def get_min_Node(self):
current = self
while current.left is not None:
current = current.left
return current.data
#get maximum node from tree starting from this node
def get_max_Node(self):
current = self
while current.right is not None:
current = current.right
return current.data
#insert node in binary tree
def insert(self,data):
current = self
if current is None:
current = Node(data)
if current.left is None and current.data>data:
current.left = Node(data)
elif current.right is None and current.data < data:
current.right = Node(data)
elif current.data >data:
insert(self.left,data)
else:
insert(self.right,data)
#delete node from binary tree
def delete_Node(self,data):
#check for none type
if self is None:
return self
#if data is greater than node data
elif data>self.data:
self.right = delete_Node(self.right,data)
#if data is less than node
elif self.data>data:
self.left = delete_Node(self.left,data)
else:
if self.left is None:
tmp = self.right
self = None
return tmp
elif self.right is None:
tmp = self.left
self = None
return tmp
#get minimal node from right subtree
tmp = self.right.get_min_Node()
#put data into self
self.data = tmp.data
#delete the minimal subtree from right
self.right = delete_Node(self.right,tmp.data)
return self
#print inorder traversal of binary tree
def inorder(self):
if self is None:
return
inorder(self.left)
print(self.data)
inorder(self.right)
#print preorder traversal of binary tree
def preorder(self):
if self is None:
return
print(self.data)
inorder(self.left)
inorder(self.right)
#print postorder traversal of binary tree
def postorder(self):
#if node is null or None
if self is None:
return
#if node is not none
inorder(self.left)
inorder(self.right)
print(self.data)
#get height of tree
def height(self):
if self is None:
return 0
else:
lheight = height(self.left)
rheight = height(self.right)
if lheight > rheight:
return lheight + 1
else:
return rheight + 1
#level order traversal of tree
def level_order(self):
#get height of tree
h = height(self)
for i in range(1,h+1):
print_level(self,i)
def print_level(self,level):
if self is None:
return
if level == 1:
print(self.data)
else:
if level > 1:
print_level(self.left,level-1)
print_level(self.right,level-1)
a = Node(30)
insert(a,22)
insert(a,1)
insert(a,36)
#print preorder traversal of binary tree
preorder(a)
root = delete_Node(a,36)
#print tree
preorder(a)
No comments:
Post a Comment