I made a binary tree but it has some logic problem can some one point

jamesbon · 09-26-2010, 12:58 PM

I wrote a program for making a binary tree
Please see if you see any errors in this

Code:

#include<stdio.h>
#include<stdlib.h>
struct node {
	struct node *left, *right;
	int data, color;
} *root;
int check = 0;
typedef struct node tree;

tree *create_node(int);
void add_tree(tree *, tree *);
void travel_tree(tree *);
int main()
{
	int i, j, value;
	tree *nv;
	printf("enter value \n");
	scanf("%d", &value);
	nv = create_node(value);
	add_tree(nv, root);
	travel_tree(root);
}

tree *create_node(int num)
{
	tree *temp;
	if (check == 0) {
		root = (tree *) malloc(sizeof(tree));
		root->data = num;
		root->left = NULL;
		root->right = NULL;
	}
	if (check != 0) {

		temp = (tree *) malloc(sizeof(tree));
		temp->data = num;
		temp->left = NULL;
		temp->right = NULL;

	}
	check++;
	return temp;
}

void add_tree(tree * something, tree * node)
{
	tree *ki;
	if (check == 0)
		return;
	if ((something->data < ki->data) && (ki->left)) {
		add_tree(something, node->left);
	} else if ((something->data < ki->data) && (ki->left == NULL)) {
		//node left is to be added at last
		ki->left = something;
		return;
	}
	if ((something->data > node->data) && (ki->right)) {
		add_tree(something, node->right);
	}
	if ((something->data > ki->data) && (ki->right == NULL)) {
		//right node is to be added
		ki->right = something;
		return;
	}

}

void travel_tree(tree * temp)
{
	if (temp->left) {
		travel_tree(temp->left);
		printf(" %d", temp->data);
	}
	if (temp) {
		travel_tree(temp);
		printf(" %d", temp->data);
	}
	if (temp->right) {
		travel_tree(temp->right);
		printf(" %d", temp->data);
	}
}

johnsfine · 09-26-2010, 01:17 PM

I see several things that might be errors depending on your intent. But the definite obvious error is in

Code:

void add_tree(tree * something, tree * node)
{
	tree *ki;
	if (check == 0)
		return;
	if ((something->data < ki->data) && (ki->left)) {

What do you think ki points to?

Other errors are mixed in with strange code, so your intent is unclear enough that the existence of an error is pretty clear but the position of the error is unclear. Consider:

Code:

int main()
{
	int i, j, value;
	tree *nv;
	printf("enter value \n");
	scanf("%d", &value);
	nv = create_node(value);
	add_tree(nv, root);

It appears (because check is zero) that this call to create_node will put a pointer to that node into root and put garbage in nv. Is that what you intended? Then what did you intend the call to add_tree to do? check would no longer be zero when you get to add_tree, so if you intended the special handling of root to suppress the action of add_tree, you missed there.

The whole concept behind check (apparently a flag for after first node) is flawed. It could be made to work, but it is still a bad idea.

It is better programming practice to do as much as possible using standard paths through the code and as little as possible in special cases. There is no need for the first node to be as different from the rest as you seem to be trying to make it.

jamesbon · 09-26-2010, 01:22 PM

Oh I wanted ki to point to node.
Thanks for pointing that out what more errors you see.
The smaller number to go left.The bigger to go right that is what I am implementing.I changed the value of ki as you pointed out above so the new code is

Code:

#include<stdio.h>
#include<stdlib.h>
struct node {
	struct node *left, *right;
	int data, color;
} *root;
int check = 0;
typedef struct node tree;

tree *create_node(int);
void add_tree(tree *, tree *);
void travel_tree(tree *);
int main()
{
	int i, j, value;
	tree *nv;
	printf("enter value \n");
	scanf("%d", &value);
	nv = create_node(value);
	add_tree(nv, root);
	travel_tree(root);
}

tree *create_node(int num)
{
	tree *temp;
	if (check == 0) {
		root = (tree *) malloc(sizeof(tree));
		root->data = num;
		root->left = NULL;
		root->right = NULL;
	}
	if (check != 0) {

		temp = (tree *) malloc(sizeof(tree));
		temp->data = num;
		temp->left = NULL;
		temp->right = NULL;

	}
	check++;
	return temp;
}

void add_tree(tree * something, tree * node)
{
	tree *ki;
	ki=node;
	if (check == 0)
		return;
	if ((something->data < ki->data) && (ki->left)) {
		add_tree(something, node->left);
	} else if ((something->data < ki->data) && (ki->left == NULL)) {
		//node left is to be added at last
		ki->left = something;
		return;
	}
	if ((something->data > node->data) && (ki->right)) {
		add_tree(something, node->right);
	}
	if ((something->data > ki->data) && (ki->right == NULL)) {
		//right node is to be added
		ki->right = something;
		return;
	}

}

void travel_tree(tree * temp)
{
	if (temp->left) {
		travel_tree(temp->left);
		printf(" %d", temp->data);
		return;
	}
	if (temp) {
		travel_tree(temp);
		printf(" %d", temp->data);
		return;
	}
	if (temp->right) {
		travel_tree(temp->right);
		printf(" %d", temp->data);
		return;
	}
}

What else are the error in the logic above you can see?

Quote:

Originally Posted by johnsfine

Other errors are mixed in with strange code, so your intent is unclear enough that the existence of an error is pretty clear but the position of the error is unclear. Consider:

Code:

int main()
{
	int i, j, value;
	tree *nv;
	printf("enter value \n");
	scanf("%d", &value);
	nv = create_node(value);
	add_tree(nv, root);

It appears (because check is zero) that this call to create_node will put a pointer to that node into root and put garbage in nv. Is that what you intended? Then what did you intend the call to add_tree to do?

My logic is I will create a node in function create_node and return a pointer to the node.
Will pass this pointer which will be in nv and root is initial call on add_tree function
when it is called subsequently I am passing left or right sibling depending upon the data in nv is greater or less than parent node to left or right.

igadoter · 09-26-2010, 01:28 PM

What is the returned value of the function create_node when 'check == 0' is true?

jamesbon · 09-26-2010, 01:32 PM

Yes that is a mistake.Thanks I modified the code

Code:

#include<stdio.h>
#include<stdlib.h>
struct node {
	struct node *left, *right;
	int data, color;
} *root;
int check = 0;
typedef struct node tree;

tree *create_node(int);
void add_tree(tree *, tree *);
void travel_tree(tree *);
int main()
{
	int i, j, value;
	tree *nv;
	printf("enter value \n");
	scanf("%d", &value);
	nv = create_node(value);
	add_tree(nv, root);
	travel_tree(root);
}

tree *create_node(int num)
{
	tree *temp;
	if (check == 0) {
		root = (tree *) malloc(sizeof(tree));
		root->data = num;
		root->left = NULL;
		root->right = NULL;
		temp=root;
	}
	if (check != 0) {

		temp = (tree *) malloc(sizeof(tree));
		temp->data = num;
		temp->left = NULL;
		temp->right = NULL;

	}
	check++;
	return temp;
}

void add_tree(tree * something, tree * node)
{
	tree *ki;
	ki=node;
	if (check == 0)
		return;
	if ((something->data < ki->data) && (ki->left)) {
		add_tree(something, node->left);
	} else if ((something->data < ki->data) && (ki->left == NULL)) {
		//node left is to be added at last
		ki->left = something;
		return;
	}
	if ((something->data > node->data) && (ki->right)) {
		add_tree(something, node->right);
	}
	if ((something->data > ki->data) && (ki->right == NULL)) {
		//right node is to be added
		ki->right = something;
		return;
	}

}

void travel_tree(tree * temp)
{
	if (temp->left) {
		travel_tree(temp->left);
		printf(" %d", temp->data);
		return;
	}
	if (temp) {
		travel_tree(temp);
		printf(" %d", temp->data);
		return;
	}
	if (temp->right) {
		travel_tree(temp->right);
		printf(" %d", temp->data);
		return;
	}
}

Now ?

johnsfine · 09-26-2010, 01:38 PM

Quote:

Originally Posted by jamesbon

Code:

 void travel_tree(tree * temp)
{
    if (temp->left) {
        travel_tree(temp->left);
        printf(" %d", temp->data);
        return;
    }

So if the tree has a left subtree, you try to print that, then the top value, then exit without printing the right. Intent?

Quote:

Code:

     if (temp) {
        travel_tree(temp);

But once you reach a tree with no left subtree, infinite recurse until stack overflow.

igadoter · 09-26-2010, 01:47 PM

Code:

tree *create_node(int num)
{
	tree *temp;
        if (check != 0) {

		temp = (tree *) malloc(sizeof(tree));
		temp->data = num;
		temp->left = NULL;
		temp->right = NULL;
                check++;
	        return temp
        }
	if (check == 0) {
		root = (tree *) malloc(sizeof(tree));
		root->data = num;
		root->left = NULL;
		root->right = NULL;
		temp=root;
                check++;
	        return temp
	}
}

Still it is not satisfied as the test 'if (check == 0)' is done only once at the begining.

jamesbon · 09-26-2010, 02:20 PM

Quote:

Originally Posted by johnsfine

So if the tree has a left subtree, you try to print that, then the top value, then exit without printing the right.

I could not understand the above part.

Quote:

Originally Posted by johnsfine

But once you reach a tree with no left subtree, infinite recurse until stack overflow.

Ok I think here is a mistake.

Quote:

Originally Posted by igadoter

Code:

tree *create_node(int num)
{
	tree *temp;
        if (check != 0) {

		temp = (tree *) malloc(sizeof(tree));
		temp->data = num;
		temp->left = NULL;
		temp->right = NULL;
                check++;
	        return temp
        }
	if (check == 0) {
		root = (tree *) malloc(sizeof(tree));
		root->data = num;
		root->left = NULL;
		root->right = NULL;
		temp=root;
                check++;
	        return temp
	}
}

Still it is not satisfied as the test 'if (check == 0)' is done only once at the begining.

Here check==0 I am doing only because if the tree does not exist then check will be zero and I need to have a root node.
root I have declared as a global pointer.

johnsfine · 09-26-2010, 03:08 PM

Usually I believe in explaining the concepts rather than rewriting the code. But some of the concepts here are too hard to explain without showing what better code would look like.

A key part of writing good code is to identify and focus on the core similarities among actions, so you code each "thing" once with a lot of generality rather than multiple similar operations.

Code:

#include<stdio.h>
#include<stdlib.h>

struct node {
	struct node *left, *right;
	int data, color;
} *root = NULL;
typedef struct node tree;

tree *create_node(int);
void add_tree(tree *, tree **);
void travel_tree(tree *);
int main()
{
	int i, j, value;
	tree *nv;
	printf("enter value \n");
	scanf("%d", &value);
	nv = create_node(value);
	add_tree(nv, &root);
	travel_tree(root);
}

tree *create_node(int num)
{
	tree* temp = (tree *) malloc(sizeof(tree));
	temp->data = num;
	temp->left = NULL;
	temp->right = NULL;
	return temp;
}

void add_tree(tree * something, tree ** node)
{
	if (*node == NULL)
	{
		*node = something;
		return;
	}
	if (something->data < (*node)->data)
	{
		add_tree(something, &((*node)->left));
		return;
	}
	if (something->data > (*node)->data)
	{
		add_tree(something, &((*node)->right));
		return;
	}
	/* Here we found an exact match for what we were trying to add */
	/* Throw the extra one away */
	free( something );
}

void travel_tree(tree * temp)
{
	if (temp != NULL) {
		travel_tree(temp->left);
		printf(" %d", temp->data);
		travel_tree(temp->right);
	}
}

Notice several things:

root is initialized to 0. That is cleaner than using an extra variable to keep track of whether root has been initialized.

create_node just does its own job. It doesn't worry about the state of the tree.

I added an extra level of indirection to the node parameter of add_tree. That is slightly messy, but has benefits that more than make up for that. The primary benefit is that there is a single place in the code that tests for a hole in the tree (instead of a special case for empty tree plus a test for a hole on the left and another test for a hole on the right).

This makes the complicated code for inserting to the left or right simple. The code just decides left or right and for each decision makes a simple call to do it. The task of dealing with whether there is a hole there (vs. further search needed) is left to the common code inside that call.

Note I also recognized there is a possible case of perfect match. I don't know what you wanted to do for an attempt at duplicate insert. The important thing is to explicitly do what you intend rather than leave that behavior to be an accident.

I also assumed travel_tree was meant to travel the whole tree. That is much simpler than what you coded because only one test is really needed (does the tree or subtree being traveled actually exist).

If you prefer, the code may be a little more readable by putting back the extra variable in add_tree

Code:

void add_tree(tree * something, tree ** node)
{
	tree* ki = *node;
	if (ki == NULL)
	{
		*node = something;
		return;
	}
	if (something->data < ki->data)
	{
		add_tree(something, &(ki->left));
		return;
	}
	if (something->data > ki->data)
	{
		add_tree(something, &(ki->right));
		return;
	}
	/* Here we found an exact match for what we were trying to add */
	/* Throw the extra one away */
	free( something );
}