Binary Search Tree

Binary Search Tree 

Binary search tree is a binary tree where node values greater than root node are placed towards right side of root and node values less than or equal to root node are placed towards left side of root.

Source Code:

class Node:
    def __init__(self,data):
        self.data=data
        self.rchild=None
        self.lchild=None
class Bst:
    def __init__(self):
        self.root=None             
 
    def createtree(self,data):
        if self.root==None:
            self.root = Node(data)
        else:
            temp = self.root
            while temp !=None:
                if data < temp.data:
                    if temp.lchild==None:
                        temp.lchild = Node(data)
                        return
                    else:
                        temp = temp.lchild
                else:
                    if temp.rchild==None:
                        temp.rchild = Node(data)
                        return
                    else:
                        temp = temp.rchild
     
    def inorder(self, root):
        if root!=None:
            self.inorder(root.lchild)
            print(root.data)
            self.inorder(root.rchild)
 
    def preorder(self, root):
        if root!=None:
            print(root.data)
            self.preorder(root.lchild)         
            self.preorder(root.rchild)
         
    def postorder(self,root):
        if root!=None:
            self.postorder(root.lchild)         
            self.postorder(root.rchild)
            print(root.data)

    def display(self,root):
        if root!=None:         
            print(root.data)
            self.inorder(root.rchild)
            self.inorder(root.lchild)
         
    def count(self, root):
        if root == None:
            return 0
        else:
            return 1 + self.count(root.lchild) + self.count(root.rchild)

def menu():
    global ch
    print("\n1.create\n2.preorder\n3.postorder\n4.inorder
                   \n5.display\n6.count\n7.stop")
    ch=int(input("enter u r choice"))

t=Bst()
while True:
    menu()
    if ch==1:
         n=int(input("enter no of node for tree"))
         for i in range(n):
            data=int(input("enter data"))
            t.createtree(data)
    elif ch==2:
       print("preorder")
       t.preorder(t.root)
    elif ch==3:
       print("postorder")
       t.postorder(t.root)
    elif ch==4:
       print("inorder")
       t.inorder(t.root)
    elif ch==5:
       t.display(t.root)
    elif ch==6:
        print("number of nodes in binary search tree")
        print(t.count(t.root))
    else:
        exit(0)
 

 

 


 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice1
enter no of node for tree3
enter data20
enter data10
enter data30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice2
preorder
20
10
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice3
postorder
10
30
20

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice4
inorder
10
20
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice5
20
30
10

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice6
number of nodes in binary search tree
3

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice7
>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using Linked List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

class Node:
  def __init__(self,r,c,v):
    self.r=r
    self.c=c
    self.v=v
    self.next=None
class Sparse:
  def __init__(self):
    self.start=None
  def createlist(self,newnode):
    temp=self.start
    if self.start==None:
      self.start=newnode
    else:
      while temp.next!=None:
        temp=temp.next
      temp.next=newnode
  def display(self):
    temp=self.start
    print("row\tcol\tval")
    while temp!=None:
      print("%d\t%d\t%d" %(temp.r,temp.c,temp.v))
      temp=temp.next

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0
sp=Sparse()
print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
    for i in range(row):
      for j in range(col):
        if X[i][j]!=0:
          newnode=Node(i,j,X[i][j])
          sp.createlist(newnode)       
    sp.display()
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

row col val

0 0 1

0 1 2

0 2 3

2 2 4

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0

print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

4

5

matrix is:

1 2 3 

0 0 0 

0 4 5 

number of zeros: 4

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Towers of Hanoi using python

This is Towers of Hanoi program. This concept uses three towers namely source, intermediate and destination. The concept is to place the disks from source tower to destination tower. Smaller disk should be always on larger disk vice versa is not possible. The order of disks on source tower and on destination tower should be same. This concept uses recursion.

Source code:

def hanoi(n,s,i,d):
    if n==1:
        print("move 1 disk from",s,"to",d)
        return
    else:
        hanoi(n-1,s,d,i)
        hanoi(1,s,i,d)
        hanoi(n-1,i,s,d)

n=int(input("enter no of disks"))
hanoi(n,"s","i","d")

 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter no of disks3

move 1 disk from s to d

move 1 disk from s to i

move 1 disk from d to i

move 1 disk from s to d

move 1 disk from i to s

move 1 disk from i to d

move 1 disk from s to d

>>>
Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Queue using Linked list

This program is about Queue using Linked list. This program contains functions
1.Insert
2.Delete
3.Display

Source code:

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Queuell:
    def __init__(self):
        self.rear=None
        self.front=None
    def insert(self):
        data=int(input("enter data"))
        newnode=Node(data)
        if self.front == None:
            self.front=newnode
            self.rear=newnode
        else:
            self.rear.next=newnode
            self.rear=newnode
        print("element inserted")
    def delete(self):
        if self.front == None:
            print("empty")
        else:
            temp=self.front
            print("element deleted is %d" %(temp.data))
            self.front=self.front.next
            del temp

    def display(self):
        if self.front==None:
            print("empty")
        else:
            temp=self.front
            print("elements in Queue")
            while temp!=None:
                print("%d" %(temp.data))
                temp=temp.next
def menu():
    print("1.insert\n2.delete\n3.display\n4.quit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Queuell()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.insert,
    2: s.delete,
    3: s.display,
    4: stop}
    option = int(input("Please enter your choice"))

    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

1.insert

2.delete

3.display

4.quit

Please enter your choice1

enter data1

element inserted

Please enter your choice1

enter data2

element inserted

Please enter your choice1

enter data3

element inserted

Please enter your choice3

elements in Queue

1

2

3

Please enter your choice2

element deleted is 1

Please enter your choice3

elements in Queue

2

3

Please enter your choice2

element deleted is 2

Please enter your choice3

elements in Queue

3

Please enter your choice2

element deleted is 3

Please enter your choice3

empty

Please enter your choice4
Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Stacks Using Linked list

This program is stacks using linked list. the program covers the following funtions:
1.Push
2.Pop
3.Display

Source Code:


class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Stackll:
    def __init__(self):
        self.start=None
        self.top=None
    def push(self):
        data=int(input("enter data"))
        newnode=Node(data)
        if self.start==None:
           self.start=newnode
           self.top=newnode
        else:
            temp=self.start
            while temp.next!=None:
                temp=temp.next
            temp.next=newnode
            top=newnode
    def pop(self):
        temp=self.start
        if temp.next ==None:
            print ("last element of stack deleted is %d" %(temp.data))
            self.start=None
            del self.top
            self.top=None
        else:
            temp=self.start
            prev=self.start
            while temp.next != None:
                prev=temp
                temp=temp.next
         
            prev.next=None
            del temp
     
 
    def display(self):
        if self.top==None:
            print("stack empty")
        else:
            temp=self.start
            print("elements in stack are")
            while temp!=None:
                print ("%d" %(temp.data))
                temp=temp.next
             
def menu():
    print("1.push\n2.pop\n3.display\n4.quit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Stackll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.push,
    2: s.pop,
    3: s.display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
1.push
2.pop
3.display
4.quit
Please enter your choice1
enter data10
Please enter your choice1
enter data20
Please enter your choice1
enter data30
Please enter your choice3
elements in stack are
10
20
30
Please enter your choice2
Please enter your choice3
elements in stack are
10
20
Please enter your choice2
Please enter your choice3
elements in stack are
10
Please enter your choice2
last element of stack deleted is 10
Please enter your choice3
stack empty

Please enter your choice4

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

     
         

Double linked list

This is python program for Double linked list concept. This code covers the following functions of Double linked list.
1.Creation of the list
2.Insertion at the beginning of the list
3. Insertion at the end of list
4. Insertion at intermediate position in the list
5. Deletion from the beginning of the list
6. Deletion at the end of the list
7.Deletion from intermediate position of the list
8.Count nodes of a list
9.Display the list
10.Reverse display

Source Code:

class Node:

   def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class Dll:

    def __init__(self):
        self.start = None
     
   
    def createlist(self):
         n=int(input("enter no of nodes"))
         for i in range(n):
            data = int(input("enter value"))
            newnode = Node(data)
            if self.start == None:
               self.start = newnode
            else:
               temp=self.start
               while temp.right != None:
                 temp=temp.right
               temp.right=newnode
               newnode.left=temp
       

    def insertend(self):
        data=int(input("enter value"))
        newnode = Node(data)
        if self.start == None:
               self.start = newnode
        else:
           temp=self.start
           while temp.right != None:
                temp=temp.right
           temp.right=newnode
           newnode.left=temp
     

    def insertmid(self):
        data=int(input("enter value"))
        newnode = Node(data)
        pos=int(input("enter position"))
        c=self.count()
        if pos>1 and pos<=c:
              temp=self.start
              prev=temp
              i=1
              while i<pos:
                 prev=temp
                 temp=temp.right
                 i=i+1
              prev.right=newnode
              newnode.left=prev
              temp.left=newnode
              newnode.right=temp
           
        else:
              print("check position")       
       
    def count(self):
        nc=0
        temp=self.start
        while temp!=None:
           nc=nc+1
           temp=temp.right
        print("number of nodes till now:%d" %nc)
        return nc

    def deletemid(self):
      count=1
      if self.start==None:
         print("empty")
      else:
         position=int(input("enter position"))
         c=self.count()
         if position>c:
            print("check position")
         if position>1 and position<c:
            temp=prev=self.start
            while count<position:
               prev=temp
               temp=temp.right
               count=count+1
            prev.right=temp.right
            temp1=temp.right
            temp1.left=prev
            del temp
            print("node deleted")
         else:
            print("check position")
     
    def deleteend(self):
        global prev
        if self.start == None:
            print('empty')
        else:
            temp=self.start
            prev=self.start
            while temp.right != None:
                prev=temp
                temp=temp.right
            prev.right=None
            temp.left=None
            del temp
         
     
    def insertbegin(self):
        data=int(input("enter value"))
        newnode = Node(data)
        if self.start == None:
            self.start=newnode
        else:
           temp=self.start
           newnode.right=temp
           temp.left=newnode
           self.start=newnode
     
     
    def deletebegin(self):
        global prev
        if self.start == None:
            print('empty')
        else:
            temp=self.start
            self.start=self.start.right
            self.start.left=None
            del temp
                 
    def display(self):
      print("elements in double linked list are:")
      if self.start == None:
            print("empty")
      else:
         temp=self.start
         while temp!= None:
            print("%d" %(temp.data))
            temp=temp.right
         
    def reversedisplay(self):
       temp=self.start
       print("reverse display")
       if self.start==None:
          priint("empty")
       else:
          while temp.right!=None:
             temp=temp.right
          while temp!=None:
             print("%d" %(temp.data))
             temp=temp.left
     
       
def menu():
    print("1.createlist\n2.insertbegin\n3.insertend\n4.insertmid")
    print("5.deletebegin\n6.deleteend\n7.deletemid\n8.count\n9.display\n10.reversedisplay\n11.exit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Dll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.createlist,
    2: s.insertbegin,
    3: s.insertend,
    4: s.insertmid,
    5: s.deletebegin,
    6: s.deleteend,
    7: s.deletemid,
    8: s.count,
    9: s.display,
    10: s.reversedisplay,
    11:stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()


Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
1.createlist
2.insertbegin
3.insertend
4.insertmid
5.deletebegin
6.deleteend
7.deletemid
8.count
9.display
10.reversedisplay
11.exit
Please enter your choice1
enter no of nodes3
enter value2
enter value3
enter value4
Please enter your choice9
elements in double linked list are:
2
3
4
Please enter your choice10
reverse display
4
3
2
Please enter your choice2
enter value1
Please enter your choice9
elements in double linked list are:
1
2
3
4
Please enter your choice3
enter value5
Please enter your choice9
elements in double linked list are:
1
2
3
4
5
Please enter your choice4
enter value0
enter position3
number of nodes till now:5
Please enter your choice9
elements in double linked list are:
1
2
0
3
4
5
Please enter your choice7
enter position3
number of nodes till now:6
node deleted
Please enter your choice9
elements in double linked list are:
1
2
3
4
5
Please enter your choice5
Please enter your choice9
elements in double linked list are:
2
3
4
5
Please enter your choice6
Please enter your choice9
elements in double linked list are:
2
3
4
Please enter your choice8
number of nodes till now:3

Please enter your choice10

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html