search in bst in c code example
Example 1: python code for binary search tree
#Complete Binary Search Tree Using Python 3
class node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class binarytree:
def __init__(self):
self.root=None
#INSERT
def insert(self,data):
if self.root==None:
self.root=node(data)
else:
self._insert(data,self.root)
def _insert(self,data,cur_node):
if data<cur_node.data:
if cur_node.left==None:
cur_node.left=node(data)
else:
self._insert(data,cur_node.left)
elif data>cur_node.data:
if cur_node.right==None:
cur_node.right=node(data)
else:
self._insert(data,cur_node.right)
else:
print('Data In Treee Already')
#REMOVE
def remove(self,data):
if self.root!=None:
self._remove(data,self.root)
def _remove(self,data,cur_node):
if cur_node == None:
return cur_node
if data<cur_node.data:
cur_node.left=self._remove(data,cur_node.left)
elif data>cur_node.data:
cur_node.right=self._remove(data,cur_node.right)
else:
if cur_node.left is None and cur_node.right is None:
print('Removing Leaf Node')
if cur_node==self.root:
self.root=None
del cur_node
return None
if cur_node.left is None:
print('Removing None with Right Child')
if cur_node==self.root:
self.root=cur_node.right
tempnode=cur_node.right
del cur_node
return tempnode
elif cur_node.right is None:
print('Removing None with Left Child')
if cur_node==self.root:
self.root=cur_node.left
tempnode=cur_node.left
del cur_node
return tempnode
print('Removing Node with 2 Children')
tempnode=self.getpred(cur_node.left)
cur_node.data=tempnode.data
cur_node.left=self._remove(cur_node.data,cur_node.left)
return cur_node
def getpred(self,cur_node):
if cur_node.right!=None:
return self.getpred(cur_node.right)
return cur_node
#INORDER TRAVERSAL
def inorder(self):
if self.root!=None:
self._inorder(self.root)
def _inorder(self,cur_node):
if cur_node!=None:
self._inorder(cur_node.left)
print(cur_node.data)
self._inorder(cur_node.right)
#PREORDER TRAVERSAL
def preorder(self):
if self.root!=None:
self._preorder(self.root)
def _preorder(self,cur_node):
if cur_node!=None:
print(cur_node.data)
self._preorder(cur_node.left)
self._preorder(cur_node.right)
#POSTORDER TRAVERSAL
def postorder(self):
if self.root!=None:
self._postorder(self.root)
def _postorder(self,cur_node):
if cur_node!=None:
self._postorder(cur_node.left)
self._postorder(cur_node.right)
print(cur_node.data)
#MINIMUM VALUE
def minval(self):
if self.root!=None:
return self._minval(self.root)
def _minval(self,cur_node):
if cur_node.left!=None:
return self._minval(cur_node.left)
return cur_node.data
#MAXIMUM VALUE
def maxval(self):
if self.root!=None:
return self._maxval(self.root)
def _maxval(self,cur_node):
if cur_node.right!=None:
return self._maxval(cur_node.right)
return cur_node.data
tree=binarytree()
tree.insert(100)
tree.insert(90) # 100
tree.insert(110) # / \
tree.insert(95) # 90 110
tree.insert(30) # / \
# 30 95
tree.remove(110)
tree.remove(90)
tree.inorder()
#tree.preorder()
#tree.postorder()
print(tree.minval())
print(tree.maxval())
Example 2: insert binary search tree
void BSNode::insert(std::string value) {
if (this->_data == value) {
_count++;
return;
}
if (this->_data > value) {
if (this->getLeft() == nullptr) {
this->_left = new BSNode(value);
}
this->getLeft()->insert(value);
return;
}
if (this->getRight() == nullptr) {
this->_right = new BSNode(value);
return;
}
this->getRight()->insert(value);
}