More Functions on Trees In Python
''' A simple Tree- Date- 5th November 2022'''
import matplotlib.pyplot as plt
import numpy as np
ls=[]
class node():
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class tree():
def __init__(self,node):
self.root=node
def __str__(self):
global ls
def preOrderIn(root):
if(root is not None):
ls.append(str(root.data))
preOrderIn(root.left)
preOrderIn(root.right)
preOrderIn(self.root)
return " ".join(ls)
def preOrder(self,root):
# The base condition is root as None
if(root is not None):
print(root.data,end=" ")
self.preOrder(root.left)
self.preOrder(root.right)
def inOrder(self,root):
if root is not None:
self.inOrder(root.left)
print(root.data,end=" ")
self.inOrder(root.right)
def postOrder(self,root):
if root is not None:
self.postOrder(root.left)
self.postOrder(root.right)
print(root.data,end=" ")
prev=None
''' Traversal Algos '''
def preOrder(root):
if(root is not None):
print(root.data,end=" ")
preOrder(root.left)
preOrder(root.right)
def inOrder(root):
if root is not None:
inOrder(root.left)
print(root.data,end=" ")
inOrder(root.right)
def postOrder(root):
if root is not None:
postOrder(root.left)
postOrder(root.right)
print(root.data,end=" ")
'''
Date- 6th November 2022
'''
def checkBst(root):
''' Checks if a given Tree is a BST or not '''
if root is not None:
global prev
if(checkBst(root.left) is False):
return False
if(prev is not None and root.data<=prev.data):
return False
prev=root
return checkBst(root.right)
else:
return True
def searchBst(root,key):
''' To search in a BST '''
if root==None:
return None
if root.data==key:
return root
elif root.data<key:
return searchBst(root.right,key)
else:
return searchBst(root.left,key)
def searchBstItr(root,key):
while(root is not None):
if root.data==key:
return root
elif root.data<key:
root=root.right
else:
root=root.left
return None
def main():
# x=[5,4,3,2,11,1,1,1,1,2,2,3,3]
# x1=np.random.normal(120,10,140)
# plt.hist(x1)
# plt.show()
# d=[20,20,20,20,20]
# mLabels=['foo','bar','buzz','buzzFoo','FooBar']
# plt.pie(d,labels=mLabels)
# plt.show()
# ls=[5,2,1,4,3]
# mergeSort(ls)
# quickSort(ls,0,4)
# print(ls)
# bubbleSort([5,4,3,2,1])
# selectionSort([5,1,3,2,4])
# insertionSort([5,1,4,2,3])
n1=node(12)
n2=node(6)
n3=node(40)
n4=node(50)
n5=node(7)
n6=node(4)
n7=node(39)
'''
12
/ \
6 40
/ \ / \
4 7 39 50
'''
n1.left=n2
n1.right=n3
n2.left=n6
n2.right=n5
n3.left=n7
n3.right=n4
# Making a new Tree(t1)
# t1=tree(n1)
# t1.preOrder(n1)
# print()
# t1.inOrder(n1)
# print()
# t1.postOrder(n1)
# print()
# print(t1)
# print("\110\145\154\154\157")
# To check if a given tree is a BST or not
print(checkBst(n1))
# Recursive Search in a Bst
print("Enter the data to be searched in the tree:")
d=int(input())
print(searchBst(n1,d).data) if searchBst(n1,d) is not None else print(searchBst(n1,d))
# Iterative Search in a Bst
print("Enter the data to search using iterative method:")
d1=int(input())
print(searchBstItr(n1,d1).data) if searchBstItr(n1,d1) is not None else print(searchBstItr(n1,d1))
if __name__=="__main__":
main()
Comments
Post a Comment