BCA 3rd sem /BCSL-033/Solved Assignment/Data and File Structures Lab /2016-2017 New

Q.1.
A.1.

Algorithm:-

1. [Initialize]

HEAD <-- NODE
LPTR(HEAD) <-- NULL
RPTR(HEAD) <-- HEAD
LEVEL[1] <-- 0
LOCATION TOP <-- 1.

2. [Process the input]

Repeat thru step 6 while input is there.

3. [Input a node]

Read(LEVEL,INFO).

4. [Create a tree node]

NEW <-- NODE
LPTR(NEW) <-- RPTR(NEW) <-- NULL
DATA(NEW) <-- INFO.

5. [Compare levels]

PRED_LEVEL <-- LEVEL[TOP]
PRED_LOC <-- LOCATION[TOP]
if LEVEL > PRED_LEVEL
then LPTR(PRED_LOC) <-- NEW
else if LEVEL = PRED_LEVEL
RPTR(PRED_LOC) <-- NEW
TOP <-- TOP – 1
else
Repeat while LEVEL != PRED_LEVEL
TOP <-- TOP – 1
PRED_LEVEL <-- LEVEL[TOP]
PRED_LOC <-- LOCATION[TOP]
if PRED_LEVEL <-- LEVEL
then write (“Invalid Input”)
return



RPTR(PRED_LOC) <-- NEW
TOP <-- TOP – 1.

6. [Pushing values in stack]

TOP <-- TOP + 1
LEVEL[TOP] <-- LEVEL
LOCATION[TOP] <-- NEW.

7. [FINISH]
return.

Program CODE:-

#include <stdio.h>
#include <stdlib.h>
struct tnode
{
int data;
struct tnode *lchild, *rchild;
};

/* returns maximum of two integers */
int maxi(int a,int b)
{
int c;
c = (a >= b)? a :b;
return c;
}

int isBalanced(struct tnode *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if(root == NULL)
return 1;

/* Get the height of left and right sub trees */
lh = height(root->lchild);
rh = height(root->rchild);

if( abs(lh-rh) <= 1 &&
isBalanced(root->lchild) &&
isBalanced(root->rchild))
return 1;

/* If we reach here then tree is not height-balanced */
return 0;
}

/* The function Compute the “height” of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct tnode* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + maxi(height(node->lchild), height(node->rchild));
}

struct tnode *insert(struct tnode *p,int val)
{
struct tnode *temp1,*temp2;
if(p == NULL)
{
p = (struct tnode *) malloc(sizeof(struct tnode));
/* insert the new node as root node*/
if(p == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
p->data = val;
p->lchild=p->rchild=NULL;
}
else
{
temp1 = p;
/* traverse the tree to get a pointer to that node
whose child will be the newly created node*/
while(temp1 != NULL)
{
temp2 = temp1;
if( temp1 ->data > val)
temp1 = temp1->lchild;
else
temp1 = temp1->rchild;
}
if( temp2->data > val)
{
temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->lchild;
if(temp2 == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
else
{
temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->rchild;
if(temp2 == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}
/* a function to binary tree in preorder */
void preorder(struct tnode *p)
{
if(p != NULL)
{
printf(“%d\t”,p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
if(p != NULL)
{
inorder(p->lchild);
printf(“%d\t”,p->data);
inorder(p->rchild);
}
}
/* a function to binary tree in postorder */
void postorder(struct tnode *p)
{
if(p != NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf(“%d\t”,p->data);
}
}
void main()
{
struct tnode *root = NULL;
int n,x;
clrscr();
printf(“\nEnter the number of nodes\n”);
scanf(“%d”,&n);
while(n!=0)
{
printf(“Enter the data value\n”);
scanf(“%d”,&x);
root = insert(root,x);
n–;
}
if(isBalanced(root))
printf(“\n***THIS TREE IS A BALANCED TREE***\n”);
else
printf(“\n**THIS TREE IS NOT A BALANCED TREE**\n”);

printf(“\n\nPREORDER OF TREE : \n”);
preorder(root);
printf(“\n\nINORDER OF TREE : \n”);
inorder(root);
printf(“\n\nPOSTORDER OF TREE : \n”);
postorder(root);
getch();
}

Q.2.A.2.

• Some algorithms (selection, bubble, heapsort) work by moving elements to their final position, one at a time. You sort an array of size N, put 1 item in place, and continue sorting an array of size N – 1 (heapsort is slightly different).
• Some algorithms (insertion, quicksort, counting, radix) put items into a temporary position, close(r) to their final position. You rescan, moving items closer to the final position with each iteration.
• One technique is to start with a “sorted list” of one element, and merge unsorted items into it, one at a time.
• Complexity and running time
  • Factors: algorithmic complexity, startup costs, additional space requirements, use of recursion (function calls are expensive and eat stack space), worst-case behavior, assumptions about input data, caching, and behavior on already-sorted or nearly-sorted data
  • Worst-case behavior is important for real-time systems that need guaranteed performance. For security, you want the guarantee that data from an attacker does not have the ability to overwhelm your machine.
  • Caching — algorithms with sequential comparisons take advantage of spatial locality and prefetching, which is good for caching.
  • Algorithmic time vs. real time — The simple algorithms may be O(N^2), but have low overhead. They can be faster for sorting small data sets (< 10 items). One compromise is to use a different sorting method depending on the input size.
  • “Comparison sorts” make no assumptions on the data and compare all elements against each other (majority of sorts). O(N lg N) time is the ideal “worst-case” scenario (if that makes sense — O(N lg N) is the smallest penalty you can hope for in the worst case). Heapsort has this behavior.
  • O(N) time is possible if we make assumptions about the data and don’t need to compare elements against each other (i.e., we know the data falls into a certain range or has some distribution). O(N) clearly is the minimum sorting time possible, 

#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
typedef struct node1
{
int data;
int bf;
struct node1 *left;
struct node1 *right;
} node;
void insert_node(node **, int);
void delete_node(node **, int);
int find_height(node *);
void delete_tree(node **);
node *findmax(node *);
void traverse_inorder(node *);

int main()
{
int choice; /* variable to store choice of user */
int element; /* variable to store data of node entered bu user */
node *root = NULL; /* intialising root node */
while (1)
{
printf(“\n\t MENU\n”);
printf(“\t——–\n”);
printf(” 1. Insert node\n”);
printf(” 2. Delete node\n”);
printf(” 3. Height of Tree\n”);
printf(” 4. Traverse inorder\n”);
printf(” 5. Exit\n\n”);
printf(“Enter your choice (1-5) ::”);
scanf(“%d”, &choice);
switch (choice)
{
case 1: printf(“\n Enter the element to be inserted::”);
scanf(“%d”, &element);
insert_node(&root, element);
break;
case 2: printf(“\n Enter the element to be deleted ::”);
scanf(“%d”, &element);
delete_node(&root, element);
break;
case 3: printf(“Height of AVL Tree = %d”, find_height(root));
break;
case 4: printf(“\n\n In-Order Traversal is\n”);
traverse_inorder(root);
break;
case 5: delete_tree(&root);
return;
}
}
}

void insert_node(node ** root, int element)
{
node *ptr1;
node *ptr2;
/* checking if there is no elemnt in th tree */
if(NULL == *root)
{
*root = (node *) malloc (sizeof(node)); /* allocating memory */
(*root)->data = element;
(*root)->left = NULL;
(*root)->right = NULL;
(*root)->bf = 0; /* allocating balance factor to root */
}
/* element is less than root than */
else if(element < (*root)->data)
{
insert_node(&((*root)->left), element);
switch((*root)->bf)
{
case 1: ptr1 = (*root)->left;
if(1 == ptr1->bf)
{
/* right rotation */
(*root)->left = ptr1->right;
ptr1->right = *root;
(*root)->bf = 0;
*root = ptr1;
}
else
{
ptr2 = ptr1->right;
ptr1->right = ptr2->left;
ptr2->left = ptr1;
(*root)->left = ptr2->right;
ptr2->right = *root;
(*root)->bf = ptr2->bf == 1 ? -1 : 0;
ptr1->bf = ptr2->bf == -1 ? 1 : 0;
*root = ptr2;
}
break;
case 0: (*root)->bf = 1;
break;
case -1: (*root)->bf = 0;
break;
}
}
else
{
insert_node(&(*root)->right, element);
switch((*root)->bf)
{
case 1: (*root)->bf = 0;
break;
case 0: (*root)->bf = -1;
break;
case -1: ptr1 = (*root)->right;
if(ptr1->bf == -1)
{
/* left rotation */
(*root)->right = ptr1->left;
ptr1->left = *root;
(*root)->bf = 0;
*root = ptr1;
}
else
{
/* double rotation ,right left */
ptr2 = ptr1->left;
ptr1->left = ptr2->right;
ptr2->right = ptr1;
(*root)->right = ptr2->left;
ptr2->left = (*root);
(*root)->bf = ptr2->bf == -1 ? 1 : 0;
ptr1->bf = ptr2->bf == 1 ? -1 : 0;
*root = ptr2;
}
}
}
}

int find_height (node *tree)
{
int height_of_left_subtree;
int height_of_right_subtree;
int height;
if (NULL == tree)
{
height = 0;
}
else
{
height_of_left_subtree = find_height(tree->left);
height_of_right_subtree = find_height(tree->right);
if(height_of_left_subtree > height_of_right_subtree)
height = height_of_left_subtree + 1;
else
height = height_of_right_subtree + 1;
}
return height;
}

void delete_node (node **h, int element)
{
node *temp; /* variable to store node which has to be freed */
node *ptr1;
node *ptr2;
if (NULL == *h)
{
printf(“Element %d not found in the AVL tree\n”, element);
printf(“press any key to continue….”);
getch();
}
else if(element < (*h)->data)
{
delete_node(&(*h)->left, element);
switch((*h)->bf)
{
case 1: (*h)->bf = 0;
break;
case 0: (*h)->bf = -1;
break;
case -1: ptr1 = (*h)->right;
if(ptr1->bf == -1)
{
/* left rotation */
(*h)->right = ptr1->left;
ptr1->left = *h;
(*h)->bf = 0;
*h = ptr1;
}
else
{
ptr2 = ptr1->left;
ptr1->left = ptr2->right;
ptr2->right = ptr1;
(*h)->right = ptr2->left;
ptr2->left = *h;
(*h)->bf = ptr2->bf == -1 ? 1 : 0;
ptr1->bf = ptr2->bf == 1 ? -1 : 0;
*h = ptr2;
}
}
}
else if (element > (*h)->data)
{
delete_node (&(*h)->right, element);
switch ((*h)->bf)
{
case 1: ptr1 = (*h)->left;
if(ptr1->bf == 1)
{
/* right rotation */
(*h)->left = ptr1->right;
ptr1->right = *h;
(*h)->bf = 0;
*h = ptr1;
}
else
{
/* double rotation , left-right */
ptr2 = ptr1->right;
ptr1->right = ptr2->left;
ptr2->left = ptr1;
(*h)->left = ptr2->right;
(*h)->bf = ptr2->bf == 1 ? -1 : 0;
ptr1->bf = ptr2->bf == -1 ? 1 : 0;
*h = ptr2;
}
break;
case 0: (*h)->bf = 1;
break;
case -1: (*h)->bf = 0;
break;
}
}
/* when element found and it has both the child than find predecessor */
else if( (*h)->left && (*h)->right)
{
temp = findmax((*h)->left); /* find predecessor */
(*h)->data = temp->data; /* replace node with predecessor */
delete_node(&(*h)->left, temp->data); /* delete predecessor */
}
else
{
temp = *h;
if(((*h)->left == NULL) && ((*h)->right == NULL)) /* terminal node */
*h = NULL;
else if ((*h)->right == NULL) /* left child only */
*h = (*h)->left;
else
*h = (*h)->right; /* right child only */
free(temp);
}
}

node * findmax(node *root)
{
if((NULL == root) || (NULL == root->right))
{
return root;
}
else
return findmax(root->right);
}

void traverse_inorder(node *root)
{
if(NULL != root)
{
traverse_inorder(root->left);
printf(“%d, “, root->data);
traverse_inorder(root->right);
}
}
void delete_tree(node **root)
{
if (NULL != *root)
{
delete_tree(&((*root)->left));
delete_tree(&((*root)->right));
free(root);
}
}
Output:

q2