C++ Create a binary tree as described in chapter 20 of the text. Your functions
ID: 3687227 • Letter: C
Question
C++
Create a binary tree as described in chapter 20 of the text. Your functions should create the nodes, display the nodes in the 3 different orders as selected by a menu choice, search for a value and delete a value. Your menu should provide the following:
1- Insert a node (value)
2- Delete a node (value)
3- Display all nodes (values)
a. In order
b. Pre order
c. Post order
4- Search for a value
5- Exit
You will need a complete diagram showing how at least 15 nodes would be laid out. Start you B-tree with the middle value so that the tree is evenly populated (e.g.: values range from 5 to 45; the first value (root of the tree) should contain the value 25).
Complete document should contain the IPO, Algorithm, source code and several screen shots showing each of the menu functions ...
Explanation / Answer
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *right, *left;
}*root,*p,*q;
struct node *make(int y)
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=y;
newnode->right=newnode->left=NULL;
return(newnode);
}
void left(struct node *r,int x)
{
if(r->left!=NULL)
printf(" Invalid !");
else
r->left=make(x);
}
void right(struct node *r,int x)
{
if(r->right!=NULL)
printf(" Invalid !");
else
r->right=make(x);
}
void inorder(struct node *r)
{
if(r!=NULL)
{
inorder(r->left);
printf(" %d",r->data);
inorder(r->right);
}
}
void preorder(struct node *r)
{
if(r!=NULL)
{
printf(" %d",r->data);
preorder(r->left);
preorder(r->right);
}
}
void postorder(struct node *r)
{
if(r!=NULL)
{
postorder(r->left);
postorder(r->right);
printf(" %d",r->data);
}
}
void create()
{
int no;
char choice='y';
printf(" Enter the root:");
scanf("%d",&no);
root=make(no);
p=root;
while(choice=='y'||choice=='Y')
{
printf(" Enter number:");
scanf("%d",&no);
if(no==-1)
break;
p=root;
q=root;
while(no!=p->data && q!=NULL)
{
p=q;
if(no<p->data)
q=p->left;
else
q=p->right;
}
if(no<p->data)
{
printf("Left branch of %d is %d ",p->data,no);
left(p,no);
}
else
{
right(p,no);
printf("Right Branch of %d is %d ",p->data,no);
}
printf(" Continue ? ");
scanf(" %c",&choice);
}
}
void main()
{
int no,action;
clrscr();
while(1)
{
printf(" 1) Create ");
printf("2) Inorder Traversal ");
printf("3) Preorder Traversal ");
printf("4) Postorder Traversal ");
printf("5) Exit ");
printf("Enter choice : ");
scanf("%d",&action);
switch(action)
{
case 1:
create();
break;
case 2:
printf(" Inorder Traversal is ");
inorder(root);
break;
case 3:
printf(" Preorder Traversal is ");
preorder(root);
break;
case 4:
printf(" Postorder Traversal is ");
postorder(root);
break;
case 5:
exit();
break;
}
getch();
}
}
/*
Output for the Program Given in 5.2.4.A
1) Create
2) Inorder Traversal
3) Preorder Traversal
4) Postorder Traversal
5) Exit
Enter choice : 1
Enter the root : 50
Enter number : 30
Left branch of 50 is 30
Continue ? y
Enter number : 22
Left branch of 30 is 22
Continue ? y
Enter number : 60
Right branch of 50 is 60
Continue ? y
Enter number : 65
Right branch of 60 is 65 Continue ? y
Continue ? n
1) Create
2) Inorder Traversal
3) Preorder Traversal
4) Postorder Traversal
5) Exit
Enter choice : 2
Inorder Traversal is
22 30 50 60 65
1) Create
2) Inorder Traversal
3) Preorder Traversal
4) Postorder Traversal
5) Exit
Enter choice : 3
Preorder Traversal is
50 30 22 60 65
1) Create
2) Inorder Traversal
3) Preorder Traversal
4) Postorder Traversal
5) Exit
Enter choice : 4
Postorder Traversal is
22 30 65 60 50
1) Create
2) Inorder Traversal
3) Preorder Traversal
4) Postorder Traversal
5) Exit
Enter choice : 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.