Reputation: 339
I'm implementing an binary search tree but for some reasons I 'm not able to add a node
my: input was :
a.value = 5;
add_bst_node(&t,a);
mystructures:
typedef struct BST_node{
entity value;
struct BST_node* left;
struct BST_node* right;
}BST_node;
typedef struct BST_tree{
BST_node* root;
}BST_tree;
my code for add a node:
void add_bst_node2(BST_node* root,entity* e){
if(!root){
root = (BST_node*)malloc(sizeof(BST_node));
root->value = *e;
root->left = NULL;
root->right = NULL;
return;
}
else if(great_than(&root->value,e))
add_bst_node2(root->left,e);
else
add_bst_node2(root->right,e);
}
void add_bst_node(BST_tree* t,entity e){
add_bst_node2(t->root,&e);
printf("%d\n",t->root==NULL);
}
Someone can explayn why I'can't add a node?
Upvotes: 3
Views: 156
Reputation: 1244
Apart from not passing double pointer to BST_node
(i.e. BST_node**
) in add_bst_node2()
as noted in the comments, you also didn't implement the function properly.
Your implementation never really adds a node, but instead in enters into infinite recursion.
Here you can find some clean theory about BST - http://www.zentut.com/c-tutorial/c-binary-search-tree/
Here is an untested correction of your code. Note that here we pass pointer to BST_tree
instead of BST_node
void add_bst_node2(BST_tree* tree,entity* e){
if(!tree->root){
/* If the binary search tree is empty, we just create a root node */
tree->root = bst_create_node(e);
return;
}
int is_left = 0;
BST_node* current_node = tree->root;
BST_node* prev = NULL;
/* Traverse the tree until we find the proper position for the new node.
* The position is denoted by 'current_node'
*/
while(current_node != NULL) {
prev = current_node;
if(greater_than(¤t_node->value, e)) {
is_left = 1;
current_node = current_node->left;
} else {
is_left = 0;
current_node = current_node->right;
}
}
/* We finally know the position where we should add the new node */
if(is_left)
prev->left = bst_create_node(e);
else
prev->right = bst_create_node(e);
}
We introduce another function for creating and initializing a node...
BST_node *bst_create_node(entity *e)
{
BST_node *n = malloc(sizeof(BST_node));
n->value = *e;
n->left = NULL;
n->right = NULL;
return n;
}
And finally we change add_bst_node()
void add_bst_node(BST_tree* t,entity e){
add_bst_node2(t, &e);
printf("%d\n", t->root==NULL);
}
Upvotes: 1
Reputation: 46
first thing is that you put an unnecessary structure BST_tree.You do it in simple way like
struct node
{
int value;
node* left;
node* right;
};
struct node* root;
I suggest you try with this code
struct node* insert(struct node* r, int data)
{
if(r==NULL) // BST is not created created
{
r = (struct node*) malloc(sizeof(struct node)); // create a new node
r->value = data; // insert data to new node
// make left and right childs empty
r->left = NULL;
r->right = NULL;
}
// if the data is less than node value then we must put this in left sub-tree
else if(data < r->value){
r->left = insert(r->left, data);
}
// else this will be in the right subtree
else {
r->right = insert(r->right, data);
}
return r;
}`
`
Upvotes: 0
Reputation: 182
From what it seems, a is a struct BST_node and value is a variable in it. You have to either pass the value to the function and handle the node creation there, or pass the whole constructed node and just point to it from the existing tree.
Upvotes: 0