我正在实现二叉搜索树,但由于某些原因,我无法添加节点
我的:输入是:
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;我添加节点的代码:
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); }有人可以解释为什么我不能添加节点?
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?
最满意答案
除了没有在add_bst_node2()传递双指针到BST_node (即BST_node** ),如注释中所述,您也没有正确实现该功能。
您的实现从未真正添加节点,而是进入无限递归。
在这里你可以找到一些关于BST的清晰理论 - http://www.zentut.com/c-tutorial/c-binary-search-tree/
这是对您的代码的未经测试的更正。 注意,这里我们将指针传递给BST_tree而不是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); }我们介绍了另一个创建和初始化节点的功能......
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; }最后我们改变add_bst_node()
void add_bst_node(BST_tree* t,entity e){ add_bst_node2(t, &e); printf("%d\n", t->root==NULL); }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); }更多推荐
发布评论