Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
Have something to say? Contribute New Article Reply to this Article
A binary search tree code
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{struct node * left;
struct node * right;
int info;
};
typedef struct node node;
node * root=NULL,*loc,*par,*save,*child;
int item;
void pre(node *);
void in(node *);
void post(node *);
void find()
{
node * ptr;
loc=root;
par=NULL;
if(root==NULL)
{
loc=NULL;
par=NULL;
return;
}
if(root->info==item)
{
loc=root;
par=NULL;
}
if(item<root->info)
{
ptr=root->left;
save=root;
}
else
{
ptr=root->right;
save=root;
}
while(ptr!=NULL)
{if(item==ptr->info)
{
loc=ptr;
ptr=save;return;
}
if(item<root->info)
{save=ptr;ptr=ptr->left;}
else
{save=ptr;ptr=ptr->right;
}
}
loc=NULL;par=save;
}
void create()
{
node * new1;
printf("enter item");
scanf("%d",&item);
find();
if(loc!=NULL)
printf("node already present\n");
else
{
new1=(node*)malloc(sizeof(node*));
new1->info=item;
new1->left=NULL;
new1->right=NULL;
if(par==NULL)
{ root=new1;
}
else
{if(item<par->info)
par->left=new1;
else
par->right=new1;
}
}
}
void del1()
{
if(loc->left==NULL&&loc->right==NULL)
{child=NULL;}
else if(loc->left!=NULL)
child=loc->left;
else
child=loc->right;
if(par!=NULL)
{
if(loc==par->left)
par->left=child;
else
par->right=child;
}
else root=child;
}
void del()
{
printf("enter item to be deleted");
scanf("%d",&item);
find();
if(loc==NULL)
{
printf("not present ");return;}
if(loc->right!=NULL&&loc->left!=NULL)
return;
else
{
del1();
printf("here in del1");
}
}
void pre(node * temp)
{
if(temp==NULL)
return;
printf("%d\t",temp->info);
pre(temp->left);
pre(temp->right);
}
void in(node * temp)
{
if(temp==NULL)
return;
in(temp->left);
printf("%d\t",temp->info);
in(temp->right);
}
void post(node * temp)
{
if(temp==NULL)
return;
post(temp->left);
post(temp->right);
printf("%d\t",temp->info);
}
int main()
{int ch=1;
do{
printf("\nMENU......\n");
printf("1)Add nodes\n");
printf("2)Preorder\n");
printf("3)Inorder\n");
printf("4)Postorder\n");
printf("5)Delete\n");
printf("enter choice");
scanf("%d",&ch);
switch(ch)
{
case 1:create();break;
case 2:pre(root);break;
case 3:in(root);break;
case 4:post(root);break;
case 5:del();break;
default:return 0;
}
printf("do you want to continue1/0\n");
scanf("%d",&ch);
}while(ch!=0);
getch();
return 0;
}
I am running this program in Bloodshed Dev C++.
When I run it in normal execution,all the entries of the tree become 2 .
However,in Debug Mode insertion and traversal work fine.
I am not able to understand this........
del1() deletes a node if present and has only 0 or 1 children.
But del1() is deleting the whole tree in my case....
Any help will be appreciated.
PS:I am a Beginner
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
Your code is awful and I'm not terribly interested in making it better. Please read this tutorial and try to match your algorithms to the sample code.
You mean to say that you accept defeat in front of awfulness of my code
My code may be terrible,but can anyone tell me what is wrong in my code ?
Thanks for the link...I checked the algorithm of my code.I could not find any mistake.
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
My code may be terrible,but can anyone tell me what is wrong in my code ?
That's a hole with no bottom. How about offering some reproduction steps for troubleshooting the issue? Tell us how to create a tree and then break it with this program exactly the way you are.
Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
That's a hole with no bottom. How about offering some reproduction steps for troubleshooting the issue? Tell us how to create a tree and then break it with this program exactly the way you are.
Narue
I write the algorithm first on a sheet of paper then I write the code
there 's hardly any question of the logic of the program being wrong
because I have even matched the algorithms 3-4 times.The issue must be in conversion of algorithm to code.
That is what I am trying to sort out.
Help...
Also pre() ,post(),in() are pretty much redundant.....
All the problems lie with find(),create() and del()
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
Give me reproduction steps, please. I'm not going to randomly create trees looking for whatever degenerate case you've managed to hit. Since this program is user-interactive, I need to know what options and values you selected to produce the error.
Alternatively, you can remove that whole user input loop and replace it with a driver that breaks consistently.
Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
Give me reproduction steps, please. I'm not going to randomly create trees looking for whatever degenerate case you've managed to hit. Since this program is user-interactive, I need to know what options and values you selected to produce the error.
Alternatively, you can remove that whole user input loop and replace it with a driver that breaks consistently.
No ma'am ,the issue is not user input specific.
After taking input 5-6 or 6 times for insertion,the program terminates without any error.
Also,as I take input,the entries in the tree start becoming 2 one-by one.
Eg
Enter input
45
inorder 45
Enter input
78
inorder 2 78
like this.
The delete function doesn't work altogether.Sometimes it deletes the whole tree ,or else shows node not present.Despite all attempts at debugging,there is no result.
You know I made almost identical program in c++ with a tree class,and it works perfectly.
There might be an issue with global and local variables.
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
I got this far before discovering your problem:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node {
struct node * left;
struct node * right;
int info;
};
typedef struct node node;
node * root=NULL;
int item;
node *find(node **par)
{
node *loc = root;
*par = NULL;
while (loc != NULL && loc->info != item) {
*par = loc;
loc = item < loc->info ? loc->left : loc->right;
}
return loc;
}
void create()
{
node *new1, *par;
node *loc = find(&par);
if(loc!=NULL)
printf("node already present\n");
else {
new1=(node*)malloc(sizeof(node));
new1->info=item;
new1->left=NULL;
new1->right=NULL;
if(par==NULL) {
root=new1;
}
else {
if(item<par->info)
par->left=new1;
else
par->right=new1;
}
}
}
void structure_r(node *root, int depth)
{
if (root == NULL) {
for (int i = 0; i < depth; i++)
putchar('\t');
puts("~");
}
else {
structure_r(root->right, depth + 1);
for (int i = 0; i < depth; i++)
putchar('\t');
printf("%d\n", root->info);
structure_r(root->left, depth + 1);
}
}
void structure(node *root)
{
structure_r(root, 0);
}
int main()
{
int a[] = {3, 5, 2, 4, 1, 6};
for (int i = 0; i < sizeof a / sizeof *a; i++) {
item = a[i];
create();
structure(root);
//getchar();
puts("=========================================");
}
}The error is on this line in create():
new1=(node*)malloc(sizeof(node*));You're allocating memory for a pointer rather than a whole node. The line should be:
new1=(node*)malloc(sizeof(node));Give that a try and see if it works out for you.
Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
I got this far before discovering your problem:
#include<stdio.h> #include<conio.h> #include<stdlib.h> struct node { struct node * left; struct node * right; int info; }; typedef struct node node; node * root=NULL; int item; node *find(node **par) { node *loc = root; *par = NULL; while (loc != NULL && loc->info != item) { *par = loc; loc = item < loc->info ? loc->left : loc->right; } return loc; } void create() { node *new1, *par; node *loc = find(&par); if(loc!=NULL) printf("node already present\n"); else { new1=(node*)malloc(sizeof(node)); new1->info=item; new1->left=NULL; new1->right=NULL; if(par==NULL) { root=new1; } else { if(item<par->info) par->left=new1; else par->right=new1; } } } void structure_r(node *root, int depth) { if (root == NULL) { for (int i = 0; i < depth; i++) putchar('\t'); puts("~"); } else { structure_r(root->right, depth + 1); for (int i = 0; i < depth; i++) putchar('\t'); printf("%d\n", root->info); structure_r(root->left, depth + 1); } } void structure(node *root) { structure_r(root, 0); } int main() { int a[] = {3, 5, 2, 4, 1, 6}; for (int i = 0; i < sizeof a / sizeof *a; i++) { item = a[i]; create(); structure(root); //getchar(); puts("========================================="); } }The error is on this line in create():
new1=(node*)malloc(sizeof(node*));You're allocating memory for a pointer rather than a whole node. The line should be:
new1=(node*)malloc(sizeof(node));Give that a try and see if it works out for you.
Thanks a ton for that.
What errors I can make......
The problem with create() is gone
But the delete function is still not working properly
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
But the delete function is still not working properly
Once again you fail to provide enough information.
Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
Once again you fail to provide enough information.
Suppose I want to delete the root,it deletes the whole tree.
Basically my delete function is deleting every node before it in the inorder travsersal of the tree
Please help urgently.
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
Suppose I want to delete the root,it deletes the whole tree. Basically my delete function is deleting every node above the node to be deleted in hierarchy(level)
Please help urgently.
This is true for other nodes also.
In some cases the program terminated unexpectedly.
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 13
Solved Threads: 0
You
© 2012 DaniWeb® LLC
