指针收到的malloc作为参数(malloc in pointer received as argument)

指针收到的malloc作为参数(malloc in pointer received as argument)

我正在实现二叉搜索树，但由于某些原因，我无法添加节点

我的：输入是：

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(&current_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(&current_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); }