Program to insert contents of file in bst or avl

# Program to insert contents of file in bst or avl
# It calculates total time it took for the insertion of all the elements
# It also calcultaes average height of the tree formed and height of any particaluar node
# Average height is the average of lenghts of all the paths from root to leaves
# Functions for inorder traversals for the both are given
# A sample file may be inculded with the project named "input.txt" which contains 1000000 numbers
# So make sure to have a file named "input.txt" in the same directory as the code (having some numbers)

import time
class node:
left = right = parent = data = height = None

class bst:
root = None
max_height = 0
ttime = 0

def insert1(self,number):
if self.root is None:
self.root = node()
self.root.data = number
self.root.height = 0

else:
p = None
current = self.root
h = 0
while (current is not None):
p = current
h = h + 1
if number > current.data:
current = current.right
else:
current = current.left

if number > p.data:
p.right = node()
p.right.data = number
p.right.height = h
p.right.parent = p
if h > self.max_height:
self.max_height = h

else:
p.left = node()
p.left.data = number
p.left.height = h
p.left.parent = p
if h > self.max_height:
self.max_height = h

def insert(self,file_name):
start_tick = time.time()
with open(file_name) as openfileobject:
for line in openfileobject:
self.insert1(int(line))
end_tick = time.time()
diff = end_tick - start_tick
self.ttime = diff

def inorder_body(self,current):
if current:
self.inorder_body(current.left)
print current.data
self.inorder_body(current.right)

def inorder(self):
self.inorder_body(self.root)

def avg_height(self):
class avg:
avh = 0
number_nodes = 0
average_height_reference = avg()
self.inorder_height(self.root,average_height_reference)
avgheight = (1.0*average_height_reference.avh)/average_height_reference.number_nodes
return avgheight

def inorder_height(self,current,avg):
if current:
self.inorder_height(current.left,avg)
if current.left is None and current.right is None:
avg.avh = avg.avh+current.height
avg.number_nodes = avg.number_nodes + 1
self.inorder_height(current.right,avg)

def t(self):
return self.ttime

def height(self,number=None):
if number is None:
return self.max_height
else:
current = self.root
while (current is not None):
if current.data == number:
break
elif current.data > number:
current = current.left
else:
current = current.right
if current is None:
print "Number not found"
else:
return current.height

class avl_node:
left = right = parent = None
height = 1

class avl:
root = None

def node_height(self,current):
if current == None:
return 0
else:
return current.height

def balance_factor(self,current):
return self.node_height(current.left) - self.node_height(current.right)

def setheight(self,current):
if current==None:
return
else:
left = self.node_height(current.left)
right = self.node_height(current.right)
current.height = max(left,right) + 1
factor = self.balance_factor(current)
if (factor > 1 and self.node_height(current.left.left) > self.node_height(current.left.right)):
current = self.right_rotate(current)
elif (factor > 1):
self.left_rotate(current.left)
current = self.right_rotate(current)
elif(factor < -1 and self.node_height(current.right.right) > self.node_height(current.right.left)):
current = self.left_rotate(current)
elif(factor < -1):
self.right_rotate(current.right)
current = self.left_rotate(current)
self.setheight(current.parent)

def right_rotate(self,current):
if current is None:
return
else:
l = current.left
z = l.right
l.right = current
l.parent = current.parent
if (current.parent is not None):
if (current == current.parent.left):
current.parent.left = l
else:
current.parent.right = l
else:
self.root = l
current.left = z
current.parent = l
if z is not None:
z.parent = current
current.height = max(self.node_height(current.left),self.node_height(current.right)) + 1 ;
l.height = max(self.node_height(l.left),self.node_height(l.right)) + 1 ;
return l

def left_rotate(self,current):
if current is None:
return
else:
r = current.right
z = r.left
r.left = current
r.parent = current.parent
if (current.parent is not None):
if (current == current.parent.left):
current.parent.left = r
else:
current.parent.right = r
else:
self.root = r
current.right = z
current.parent = r
if z is not None:
z.parent = current
current.height = max(self.node_height(current.left),self.node_height(current.right)) + 1 ;
r.height = max(self.node_height(r.left),self.node_height(r.right)) + 1 ;
return r

def insert1(self,number):
if self.root is None:
self.root = avl_node()
self.root.data = number

else:
p = None
current = self.root
while (current is not None):
p = current
if number > current.data:
current = current.right
else:
current = current.left

if number > p.data:
p.right = avl_node()
p.right.data = number
p.right.parent = p
self.setheight(p.right)
else:
p.left = avl_node()
p.left.data = number
p.left.parent = p
self.setheight(p.left)

def inorder(self):
self.inorder_body(self.root)

def inorder_body(self,current):
if current:
self.inorder_body(current.left)
print current.data, " ", current.height
self.inorder_body(current.right)

def insert(self,file_name):
start_tick = time.time()
with open(file_name) as openfileobject:
for line in openfileobject:
self.insert1(int(line))
end_tick = time.time()
diff = end_tick - start_tick
self.ttime = diff

def height(self,number=None):
if number is None:
return self.root.height
else:
current = self.root
current_height = 0
while (current is not None):
if current.data == number:
break
elif current.data > number:
current_height = current_height + 1
current = current.left
else:
current_height = current_height + 1
current = current.right
if current is None:
print "Number not found"
else:
return current_height

def avg_height(self):
class avg:
avh = 0
number_nodes = 0
average_height_reference = avg()
self.inorder_height(self.root,average_height_reference,0)
avgheight = (1.0*average_height_reference.avh)/average_height_reference.number_nodes
return avgheight

def inorder_height(self,current,avg,number):
if current:
self.inorder_height(current.left,avg,number+1)
if current.left is None and current.right is None:
avg.avh = avg.avh+number
avg.number_nodes = avg.number_nodes + 1
self.inorder_height(current.right,avg,number+1)

def insert_time(self):
return self.ttime

def main():
bst1 = bst()
print "Insertion in Bst started..."
bst1.insert("input.txt")
print "Insertion in Bst finished"
bst_insert_time = bst1.t()
print "Time taken for insertion is ", bst_insert_time, " seconds"
bst_height = bst1.height()
print "Height of Bst formed is ", bst_height
bst_average_height = bst1.avg_height()
print "Average height of Bst formed is ", bst_average_height
nodes_height = bst1.height(61913013)
print "Height of node(61913013) is ", nodes_height

# bst1.inorder() will print the nodes of bst as encountered in inorder traversal

print

avl1 = avl()
print "Insertion in AVL started..."
avl1.insert("input.txt")
print "Insertion finished."
avl_insert_time = avl1.insert_time()
print "Time for insertion is ", avl_insert_time," seconds"
avl_tree_height = avl1.height()
print "Height of AVL tree formed is: ", avl_tree_height
avl_average_height = avl1.avg_height()
print "Average height of tree is ", avl_average_height
node_height = avl1.height(61913013)
print "Height of node(61913013) is ", node_height

# avl1.inorder() will print the nodes of avl as encountered in inorder traversal
main()

WAP to covert String into Lower case

#include<stdio.h>

#include<conio.h>
void main()
{
clrscr();
//char b='A';
char a[100];
char *k=a;
printf("\n Enter the String ");
gets(a);
while(*k)
{
if(*k>='A' && *k<='Z' )
{
*k=*k+32;
}
k++;
}
printf("  %s",a);
getch();
}

WAP to find Factorial

#include<conio.h>
#include<stdio.h>
void main()
{
clrscr();
int a=1,x;
printf("  Enter no. ");
scanf("%d",&x);
printf("\n");
for(int i=1;i<=x;i++)
{
a=a*i;
}
printf(" %d",a);
getch();
}

WAP to take input a set of intergers and store them in an array and display in Reverse order.

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int a[20],k,x,i;
printf(" How many no. to be entered ? ");
scanf("%d",&k);
printf("\n\tEnter no. ");
for(i=0;i<k;i++)
{
scanf(" %d",&a[i]);
}
printf("Numbers in Reverse order \n");
x=k-1;
for(x;x>=0;x--)
{
printf(" %d",a[x]);
}
getch();
}

WAP that will take as input a set of integer and find and display the largest and the smallest value with in the input data value

#include<conio.h>
#include<stdio.h>

void main()
{
clrscr();
int a[20],k,x=0,i,p=0;
printf(" How many no. to be entered ? ");
scanf("%d",&k);
printf("\n\tEnter no. ");
for(i=0;i<k;i++)
{
scanf(" %d",&a[i]);
}
for(i=0;i<k;i++)
{
if(a[0]>a[i])
{
a[0]=a[i];
p=a[0];
}
}
for(i=0;i<k;i++)
{
if(a[0]<a[i])
{
a[0]=a[i];
x=a[0];
}
}
printf(" Smallest no. is %d  and Largest no. is  %d",p,x);
getch();
}

WAP to covert a String into Upper case

#include<stdio.h>

#include<conio.h>
void main()
{
clrscr();
//char b='A';
char a[100];
char *k=a;
printf("\n Enter the String ");
gets(a);
while(*k)
{
if(*k>='a' && *k<='z' )
{
*k=*k-32;
}
k++;
}
printf("%s",a);
getch();
}

WAP to count no. of Vowels ,Consonant and spaces in a String

#include<stdio.h>

#include<conio.h>
void main()
{
clrscr();
char s[100];
char *a=s;
int m=0, x=0,p=0,k=0;
printf("\nEnter the String ");
gets(s);
while(*a)
{
a++;
m++;
}
for(int i=0;i<m;i++)
{
if(s[i]==' ')
{
k++;
}
else
if(s[i]=='a' || s[i]=='A' || s[i]=='e' || s[i]=='E' || s[i]=='i' || s[i]=='I' || s[i]=='o' || s[i]=='O' || s[i]=='u' || s[i]=='U')
{
p++;
}
else{
x++;
}
}
printf("\n\tVowel in String is : %d " ,p);
printf("\n\tSpaces in String is : %d " ,k);
printf("\n\tconstraint in String is : %d " ,x);
getch();

}

WAP to print length of String.

#include<stdio.h>

#include<conio.h>
void main()
{
clrscr();
char s[100];
char *a=s;
int x=0;
printf("\nEnter the String ");
gets(s);
while(*a)
{      a++;
       x++;

}
printf("\n\tLength of String is : %d",x);
getch();

}

WAP to print patter

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int k,i,j;
for(i=0;i<5;i++)  {
for(j=0;j<5-i;j++) {
printf(" ");
}
for(k=0;k<=i;k++){
printf("*");
}
printf("\n");
}
getch();
}

WAP to print pattern STAR(*)

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int k,i,j;
for(i=0;i<5;i++)  {
for(j=0;j<5-i;j++) {
printf(" ");
}
for(k=0;k<=i*2;k++){
printf("*");
}
printf("\n");
}
getch();
}

WAP to check if the given matrix is magic square or not

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int a[10][10],sum,p,q,r=0;
int i,j,x,n;
printf("\t Enter the no. of row in Matrix ");
scanf("%d",&x);
printf("\n\t Enter the no. of column in Matrix ");
scanf("%d",&n);
printf("\n\t Enter the Matrix of A : ");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\tThe Matrix is : \n");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
printf("   %d",a[i][j]);
}
printf("\n");
}
sum=0;
for(i=0;i<x;i++){
for(j=0;j<n;j++) {
if(i == j)
{
sum=sum+a[i][j];
}
}
}
for(i=0;i<x;i++){
p=0;
for(j=0;j<n;j++) {
p=p+a[i][j];
}
if(sum == p)
r=1;
else
{
r=0;
break;
}
}
for(i=0;i<x;i++){
q=0;
for(j=0;j<n;j++) {
q=q+a[j][i];
}
if(sum == q)
r=1;
else
{
r=0;
break;
}
}
if(r==1)
{
printf("\n\tMatrix is Magic Square ");
}
else
{
printf("\n\t Matrix is not Magic Square ");
}
getch();
}

WAP to compute transpose of the matrix

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int a[10][10],b[10][10],c[10][10];
int i,j,x,n;
printf("\t Enter the no. of row in Matrix ");
scanf("%d",&x);
printf("\n\t Enter the no. of column in Matrix ");
scanf("%d",&n);
printf("\n\t Enter the Matrix of A : ");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\tThe Matrix is : \n");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
printf("   %d",a[i][j]);
}
printf("\n");
}
for(i=0;i<x;i++){
for(j=0;j<n;j++) {
b[i][j]= a[j][i];
}
}
printf("\n\tTranspose of Matrix is :  \n");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
printf("   %d",b[i][j]);
}
printf("\n");
}
getch();
}

WAP to perform Subtraction between two matrix.

#include<conio.h>
#include<stdio.h>

void main()
{
clrscr();
int a[10][10],b[10][10],c[10][10];
int i,j,x,n;
printf("\t Enter the no. of row in Matrix ");
scanf("%d",&x);
printf("\n\t Enter the no. of column in Matrix ");
scanf("%d",&n);
printf("\n\t Enter the Matrix of A : ");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\n\tEnter the Matrix of B : ");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&b[i][j]);
}
}
for(i=0;i<x;i++){
for(j=0;j<n;j++) {
c[i][j]= a[i][j]-b[i][j];
}
}
printf("\n\t Subtration is :  ");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
printf("%d    ",c[i][j]);
}
printf("\n\t\t\t");
}
getch();
}

WAP to print the Upper triangle of the matrix

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int a[10][10],i,j,k;
printf("\nEnter the Matrix of 3X3 : ");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("The Matrix is : \n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("\t%d",a[i][j]);
}
printf("\t\n");
}
printf("\n Upper triangular Matrix is: \n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(i>=j)
{
printf("\t%d",a[i][j]);
}
else
{
printf("\t0");
}
}
printf("\n");
}
getch();
}

WAP to print the Lower triangle of the matrix

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int a[10][10],i,j,k;
printf("\nEnter the Matrix of 3X3 : ");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("The Matrix is : \n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("\t%d",a[i][j]);
}
printf("\t\n");
}
printf("\n Lower triangular Matrix is: \n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(i<=j)
{
printf("\t%d",a[i][j]);
}
else
{
printf("\t0");
}
}
printf("\n");
}
getch();
}

WAP to perform Multiplication between two matrix.

#include<conio.h>

#include<stdio.h>
void main()
{
clrscr();
int a[10][10],b[10][10],c[10][10];
int i,j,x,y,m,n,k;
printf("\t\n Enter the no. of row and column in Matrix A :");
scanf("%d%d",&x,&y);
printf("\n\t Enter the no. of row and column in Matrix B :");
scanf("%d%d",&m,&n);
printf("\n\t Enter the Matrix of A : ");
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\n\tEnter the Matrix of B : ");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&b[i][j]);
}
}
for(i=0;i<x;i++){
for(j=0;j<n;j++) {
for(k=0;k<y;k++){
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
}
}
printf("\n\t Multiplication is :  ");
for(i=0;i<x;i++)
{
for(j=0;j<n;j++)
{
printf("%d  ",c[i][j]);
}
printf("\n\t\t\t");
}
getch();
}