binary search tree problem

[sugaray]

the binary search tree node here contains another structure as it's
data field,
programs did successfully work when data field is int, char, this time
i got stucked, don't know why ? if there's something to do with
dynamic data object ?
thanx for your help.

=============== === begin of code =============== ===============
#include <stdio.h>
#include <stdlib.h>

typedef struct tagStock
{
char name[64];
int tag;
} Stock;

typedef struct tagBinarySearch TreeNode BSTNode;
struct tagBinarySearch TreeNode
{
Stock *stock;
BSTNode *left;
BSTNode *right;
};

typedef struct tagBinarySearch Tree
{
size_t size;
BSTNode *root;
} BSTree;

Stock *
CreateStock (char *name, int tag)
{
Stock *stock;

stock = (Stock *) malloc (sizeof (Stock));
if (stock == NULL)
return NULL;

strcpy (stock->name, name);
stock->tag = tag;

return stock;
}

BSTNode *
InsertNode (BSTree * tree, Stock * stock)
{
BSTNode *tmp;
BSTNode *root = tree->root;
if (root == NULL)
{
root->stock = stock;
root->left = NULL;
root->right = NULL;
tree->size = 1;
}
else
{
while (root != NULL)
{
tmp = root;
if ((stock->tag) < (root->stock->tag))
root = root->left;
else
root = root->right;
}

if ((stock->tag) < (tmp->stock->tag))
{
root->stock = stock;
root->left = NULL;
root->right = NULL;
tmp->left = root;
tree->size++;
}
else if ((stock->tag) > (tmp->stock->tag))
{
root->stock = stock;
root->left = NULL;
root->right = NULL;
tmp->right = root;
tree->size++;
}
else return NULL;
}
return root;
}

void
Traversal (BSTNode * root)
{
if (root == NULL)
return;
Traversal (root->left);
printf ("%d\n", root->stock->tag);
Traversal (root->right);
}

int
main (int argc, char **argv)
{
char name[64];
int tag = 0, i;
Stock *stock;
BSTree *tree = NULL;

for (i = 0; i < 10; ++i)
{
scanf ("%s", name);
scanf ("%d", &tag);
stock = CreateStock (name, tag);
InsertNode (tree, stock);
}

Traversal (tree->root);

return 0;
}
=============== ========= end of code
=============== =============== ===========

[Christian Bau]

Re: binary search tree problem

In article <ad3defeb.04060 72348.68e55b7b@ posting.google. com>,
ruicui@sohu.com (sugaray) wrote:
[color=blue]
> <snipped>[/color]

In function InsertNode, you have a loop

while (root != NULL) { ... }

Since there is no break statement in the loop, you will have root ==
NULL after executing this loop. However, in the following code you have
assignments to root->xxx - that's a bad idea.

[Richard Bos]

Re: binary search tree problem

ruicui@sohu.com (sugaray) wrote:
[color=blue]
> the binary search tree node here contains another structure as it's
> data field,
> programs did successfully work when data field is int, char,[/color]

By accident.
[color=blue]
> this time i got stucked, don't know why ? if there's something to do with
> dynamic data object ?[/color]

It's nothing to do with your struct member and everything with your
tree.
[color=blue]
> InsertNode (BSTree * tree, Stock * stock)
> {
> BSTNode *tmp;
> BSTNode *root = tree->root;[/color]

This function asks for tree->root without checking whether tree points
at a valid tree object...
[color=blue]
> BSTree *tree = NULL;[/color]
[color=blue]
> InsertNode (tree, stock);[/color]

....yet in your main function, you pass it a null pointer. That this
worked before is mere accident. Correct InsertNode() so that it checks
for null pointers, and does something about them.
[color=blue]
> if (root == NULL)
> {
> root->stock = stock;
> root->left = NULL;
> root->right = NULL;
> tree->size = 1;
> }[/color]

And while you're at it, it would be a very good idea not to
_intentionally_ write through a null pointer. You do this throughout
your insertion function. Where did you think all those nodes would end
up? They aren't assigned some memory by magic, you know.

Richard

[CBFalconer]

Re: binary search tree problem

sugaray wrote:[color=blue]
>
> the binary search tree node here contains another structure as
> it's data field,
> programs did successfully work when data field is int, char, this
> time i got stucked, don't know why ? if there's something to do
> with dynamic data object ?
> thanx for your help.
>
> =============== === begin of code =============== ===============
> #include <stdio.h>
> #include <stdlib.h>
>
> typedef struct tagStock
> {
> char name[64];
> int tag;
> } Stock;
>
> typedef struct tagBinarySearch TreeNode BSTNode;
> struct tagBinarySearch TreeNode
> {
> Stock *stock;
> BSTNode *left;
> BSTNode *right;
> };
>
> typedef struct tagBinarySearch Tree
> {
> size_t size;
> BSTNode *root;
> } BSTree;
>
> Stock *
> CreateStock (char *name, int tag)
> {
> Stock *stock;
>
> stock = (Stock *) malloc (sizeof (Stock));
> if (stock == NULL)
> return NULL;
>
> strcpy (stock->name, name);
> stock->tag = tag;
>
> return stock;
> }
>
> BSTNode *
> InsertNode (BSTree * tree, Stock * stock)
> {
> BSTNode *tmp;
> BSTNode *root = tree->root;
> if (root == NULL)
> {
> root->stock = stock;
> root->left = NULL;
> root->right = NULL;
> tree->size = 1;
> }[/color]

I stopped right here. If root is NULL, how can root possibly
point to any fields whatsoever?

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[sugaray]

Re: binary search tree problem

after a bit of modification of the faults everybody pointed out,
it still can't work correctly. i'm kinda in the middle of nowhere right
now.

BSTNode *InsertNode (BSTree * tree, Stock * stock)
{
BSTNode **tmp;
BSTNode *root;

if(tree!=NULL)
root=tree->root;

if (root == NULL)
{
root->stock = stock;
root->left = NULL;
root->right = NULL;
tree->size = 1;
}
else
{
while (root != NULL)
{
tmp = &root;
if ((stock->tag) < (root->stock->tag))
root = root->left;
else
root = root->right;
}

if ((stock->tag) < ((*tmp)->stock->tag))
{
root->stock = stock;
root->left = NULL;
root->right = NULL;
(*tmp)->left = root;
tree->size++;
}
else if ((stock->tag) > ((*tmp)->stock->tag))
{
root->stock = stock;
root->left = NULL;
root->right = NULL;
(*tmp)->right = root;
tree->size++;
}
else return NULL;
}
return root;
}

int main (int argc, char **argv)
{
char name[64];
int tag = 0, i;
Stock *stock;
BSTree *tree;
tree=(BSTree *)malloc(sizeof (BSTree));
assert(tree!=NU LL);
tree->root=NULL;
tree->size=0;

for (i = 0; i < 10; ++i)
{
scanf ("%s", name);
scanf ("%d", &tag);
stock = CreateStock (name, tag);
InsertNode (tree, stock);
}

Traversal (tree->root);

free(tree);

return 0;
}

[Barry Schwarz]

Re: binary search tree problem

On 9 Jun 2004 20:01:21 -0700, ruicui@sohu.com (sugaray) wrote:
[color=blue]
>after a bit of modification of the faults everybody pointed out,
>it still can't work correctly. i'm kinda in the middle of nowhere right
>now.
>
>BSTNode *InsertNode (BSTree * tree, Stock * stock)
>{
> BSTNode **tmp;
> BSTNode *root;
>
> if(tree!=NULL)
> root=tree->root;
>
> if (root == NULL)[/color]

If tree is NULL, root is uninitialized and this invokes undefined
behavior.
[color=blue]
> {
> root->stock = stock;[/color]

Since root is NULL, you cannot dereference as you try to do here.
This invokes undefined behavior.
[color=blue]
> root->left = NULL;
> root->right = NULL;
> tree->size = 1;[/color]

Since you check for tree being NULL earlier, it is possible that it is
NULL here also.
[color=blue]
> }
> else
> {
> while (root != NULL)
> {
> tmp = &root;[/color]

&root is a constant. Why is this assignment inside the loop?
[color=blue]
> if ((stock->tag) < (root->stock->tag))
> root = root->left;
> else
> root = root->right;
> }
>
> if ((stock->tag) < ((*tmp)->stock->tag))[/color]

(*tmp) will always evaluate to root. What is accomplished by this
additional level of indirection?
[color=blue]
> {
> root->stock = stock;
> root->left = NULL;
> root->right = NULL;
> (*tmp)->left = root;
> tree->size++;
> }
> else if ((stock->tag) > ((*tmp)->stock->tag))
> {
> root->stock = stock;
> root->left = NULL;
> root->right = NULL;
> (*tmp)->right = root;[/color]

These two assign values to the same variable.

Do you really want root->right pointing to the same struct that root
points to? The list will become circular.
[color=blue]
> tree->size++;
> }
> else return NULL;
> }
> return root;
>}
>
>int main (int argc, char **argv)
>{
> char name[64];
> int tag = 0, i;
> Stock *stock;
> BSTree *tree;
> tree=(BSTree *)malloc(sizeof (BSTree));[/color]

Don't cast the return from malloc. It cannot help in this case but
will suppress a useful diagnostic if you forget to include stdlib.h.
[color=blue]
> assert(tree!=NU LL);
> tree->root=NULL;
> tree->size=0;
>
> for (i = 0; i < 10; ++i)
> {
> scanf ("%s", name);
> scanf ("%d", &tag);
> stock = CreateStock (name, tag);
> InsertNode (tree, stock);
> }
>
> Traversal (tree->root);
>
> free(tree);
>
> return 0;
>}[/color]



<<Remove the del for email>>

[CBFalconer]

Re: binary search tree problem

sugaray wrote:[color=blue]
>
> after a bit of modification of the faults everybody pointed out,
> it still can't work correctly. i'm kinda in the middle of
> nowhere right now.[/color]

You top-posted this as a reply to a message of mine, and totally
ignored the fundamental error I pointed out. Search google for
Richard Heathfields course on reading.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Richard Bos]

Re: binary search tree problem

ruicui@sohu.com (sugaray) wrote:
[color=blue]
> after a bit of modification of the faults everybody pointed out,
> it still can't work correctly.[/color]

You did not correct _any_ of the errors I pointed out to you. You did,
indeed, only "modify the faults"; the faults are still there, but in
some cases you've muddled the code by introducing an extra pointer and
leaving the original error intact. You still do not allocate any memory
for your nodes.
Before you continue trying to create dynamic data types, go back to the
chapter which explains allocated memory (i.e., malloc(), realloc(),
calloc() and free()). Do not go back to your tree until you _fully_
understand memory allocation. Reading it through once is not enough.
Until you understand completely what malloc() is for and how pointers
work (and more importantly, how they do not work), you will never write
a working binary tree implementation.

Richard