1 . Develop a program that can be used to test an implementation of BinaryTreeIn

Question

1 . Develop a program that can be used to test an implementation of BinaryTreeInterface.

2 . Repeat the previous problem, but assume that the implementation represents a binary search tree To test:

------USING C++ , no sorting libraries. Im learning how to do these by scratch-------

Randomly generate 100 unique values in the range of [1-200] and insert them into a binary search tree (BST1).

Print height and inorder output of the BST1 tree.

Randomly generate 10 unique values in the range of [1-200] where there is an overlap with the previous values and insert them into another binary search tree (BST2).

Print preorder, inorder, and postorder output of the BST2 tree.

Find and remove any values of BST2 from BST1.

Print height, number of nodes, and inorder output of the modified BST1 tree.

Clear the binary search trees.

Print whether trees are empty before and after clear operation.

Explanation / Answer

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
FILE *fptr;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}

if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}

}

void print_preorder(node * tree)
{
if (tree)
{
//printf("%d ",tree->data);
fprintf(fptr,"%d ",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}

}

void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
//printf("%d ",tree->data);
fprintf(fptr,"%d ",tree->data);
print_inorder(tree->right);
}
}

void print_postorder(node * tree)
{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
//printf("%d ",tree->data);
fprintf(fptr,"%d ",tree->data);
}
}

void deltree(node * tree)
{
/*if (tree)
{
deltree(tree->left);
deltree(tree->right);
  
free(tree);
tree=NULL;
}*/
tree=NULL;
}

node* search(node ** tree, int val)
{
if(!(*tree))
{
return NULL;
}

if(val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
}
/*------------------------------------------*/
void calhd(node *ptr){

int depth1 = 0, depth2 = 0;
node *root1=ptr;
ptr = root1;
while (ptr->left != NULL || ptr->right != NULL)
{
depth1++;
if (ptr->left == NULL)
ptr = ptr->right;
else
ptr = ptr->left;
}
ptr = root1;
while (ptr->left != NULL || ptr->right != NULL)
{
depth2++;
if (ptr->right == NULL)
ptr = ptr->left;
else
ptr = ptr->right;
}
/*
*DEPTH IS CONSIDERED FROM LEVEL-0 ALSO HEIGHT IS CONSIDERED AS NUMBER OF EDGES
*/
if (depth1 > depth2){
  
fprintf(fptr,"height of the tree is %d ",depth1);
fprintf(fptr,"Level of the binary tree is %d (Assume that root is level 0) ",depth1-1);
}
else
fprintf(fptr,"height of the tree is %d ",depth2);
fprintf(fptr,"Level of the binary tree is %d (Assume that root is level 0) ",depth2-1);
  
}
/*------------------------------------------*/
void isempty(node *tree)
{
if(tree==NULL)
{
fprintf(fptr,"%s ","tree is empty ");
return;
}
fprintf(fptr,"%s ","Tree is not empty ");
}
/*---------------------------------------------------------------------------------------------------*/
void main()
{
node *root;
node *tmp;
int inputa[20],count=0;
int j=0,k;
int choi;
root = NULL;
fptr=fopen("outlast.txt","w");
fprintf(fptr,"%s", "OUTPUT ");
fclose(fptr);
fptr=fopen("outlast.txt","a+");
/* Inserting nodes into tree */
/******************************************/
FILE* file = fopen ("in.txt", "r");
int i = 0;

fscanf (file, "%d", &i);
while (!feof (file))
{
inputa[j++]=i;
fscanf (file, "%d", &i);
}
fclose (file);
/*******************************************/
for(k=0;k<j;k++){
insert(&root, inputa[k]);
}
fprintf(fptr,"No of nodes in the binary tree is %d ",j);
/* Printing nodes of tree */
//printf("Pre Order Display ");
fprintf(fptr,"%s ","Pre Order Display");
print_preorder(root);

//printf("In Order Display ");
fprintf(fptr,"%s ","In Order Display");
print_inorder(root);

//printf("Post Order Display ");
fprintf(fptr,"%s ","Post Order Display");
print_postorder(root);

/* Search node into tree */
int se;
printf("Enetr item for search: ");
scanf("%d",&se);
tmp = search(&root, se);
if (tmp)
{
fprintf(fptr,"Searched node=%d ", tmp->data);
}
else
{
fprintf(fptr,"%s ","Data Not found in tree. ");
}
do{
printf("Do you want to check if BST is empty of not ? (1 for Yes/2 for No): ");
scanf("%d",&choi);
switch(choi)
{
case 1:
isempty(root);
choi=2;
break;
case 2:
   break;
default:
printf("Enter valid input. ");
break;
}
}while(choi!=2);
  
calhd(root);
/* Deleting all nodes of tree */
do{
printf("Do you want to Delete BST ? (1 for Yes/2 for No): ");
scanf("%d",&choi);
switch(choi)
{
case 1:
root=NULL;
choi=2;
isempty(root);
break;
case 2:
   break;
default:
printf("Enter valid input. ");
break;
}
}while(choi!=2);
   fclose(fptr);
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.