Beginning with the sample binary tree code you are to generate a complex data st
ID: 3862699 • Letter: B
Question
Beginning with the sample binary tree code you are to generate a complex data structure giving trees inside of trees inside of a tree.
If you begin with the root of a binary tree.
Binode with an (id1*(binode)) ß- a binary tree
Then if that “binode” is located as part of a tuple: 2Dbinode
That tuple has an identifier and that binode with is the root of the binode tree.
2Dbinode (id2* (binode) *2Dbinode)
Each of those in turn are part of a 3Dbinode which consists of:
3Dbinode(id3 * (2Dbinode) * 3Dbinode)
Directions--You are to populate that data structure with N randomized (3Dnodes):
Allow the user to search for a specific node displaying the path to the node ex: (25, 10, 4) the display would be
(25)
(25, 7)
(25, 10)
(25, 10,4)
If the user searches for a node that does not exist:(30, (7, (30))) then the path displayed would be
(25)
(30)
(30,7)
(30, 7, 30) NOT FOUND
If the user wishes to ADD a node at any level they should be prompted to enter the 3 digit code for that node; Again the path should be displayed.EX: ADD (30, 11, 5) then the display would be
(25)
(30)
(30, 7)
(30, 11) created
(30, 11, 5) created
Print out the contents of the 3dbinode tree as a sequence of (A,B,C)
Extra Credit:IF the user wishes to DELETE a node
EX: DEL (30, 7, _)
Then the result would be
(30, 7, 22) deleted
(30, 7, 0) created
SAMPLE CODE:
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct BinaryTreeN
{
int value;
struct BinaryTreeN *l;
struct BinaryTreeN *r;
}*root = NULL, *temp = NULL, *t2, *t1;
void delete1();
void insert();
void delete();
void inorder(struct BinaryTreeN *t);
void create();
void search(struct BinaryTreeN *t);
void preorder(struct BinaryTreeN *t);
void postorder(struct BinaryTreeN *t);
void search1(struct BinaryTreeN *t,int data);
int smallest(struct BinaryTreeN *t);
int largest(struct BinaryTreeN *t);
int flag = 1;
void main()
{
int ch;
printf(" OPERATIONS ---");
printf(" 1 - Insert ");
printf("2 - Delete ");
printf("3 - Inorder Traversal ");
printf("4 - Preorder Traversal ");
printf("5 - Postorder Traversal ");
printf("6 - Exit ");
while(1)
{
printf(" Enter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
/* To insert a node in the tree */
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}
/* To create a node */
void create()
{
int data;
printf("Enter data of node to be inserted : ");
scanf("%d", &data);
temp = (struct BinaryTreeN *)malloc(1*sizeof(struct BinaryTreeN));
temp->value = data;
temp->l = temp->r = NULL;
}
/* Function to search the appropriate position to insert the new node */
void search(struct BinaryTreeN *t)
{
if ((temp->value > t->value) && (t->r != NULL)) /* value more than root node value insert at right */
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL)) /* value less than root node value insert at left */
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}
/* recursive function to perform inorder traversal of tree */
void inorder(struct BinaryTreeN *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}
/* To check for the deleted node */
void delete()
{
int data;
if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}
/* To find the preorder traversal */
void preorder(struct BinaryTreeN *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
printf("%d -> ", t->value);
if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}
/* To find the postorder traversal */
void postorder(struct BinaryTreeN *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
printf("%d -> ", t->value);
}
void search1(struct BinaryTreeN *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}
/* To delete a node */
void delete1(struct BinaryTreeN *t)
{
int k;
/* To delete leaf node */
if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}
/* To delete node having one left hand child */
else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;
}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}
/* To delete node having right hand child */
else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;
t == NULL;
free(t);
return;
}
/* To delete node having two child */
else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}
}
/* To find the smallest element in the right sub tree */
int smallest(struct BinaryTreeN *t)
{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}
/* To find the largest element in the left sub tree */
int largest(struct BinaryTreeN *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.