给定以下结构:
struct TElem {
int val;
};
typedef int TKey;
struct Node {
TKey key;
struct TElem *elem;
struct Node *left;
struct Node *right;
};
struct bst {
struct Node *root;
};
还有两个函数bst_Search
和bst_Insert
。
struct TElem* bst_Search(struct bst *T, TKey c, struct Node **posins)
{
struct Node *q = T->root;
posins = &(T->root); // (1)
while (q)
if (q->key == c)
return q->elem;
else if ( c < q->key) {
q = q->left;
posins = &(q->left);
} else {
q = q->right;
posins = &(q->right);
}
return NULL;
}
void bst_Insert(struct bst *T, TKey c, struct TElem *x)
{
struct Node **posins;
struct TElem *v;
posins = malloc(sizeof *posins);
v = bst_Search(T, c, posins); // (2)
if (!v) {
struct Node *q = malloc(sizeof *q);
q->key = c;
q->elem = x;
q->left = NULL;
q->right = NULL;
*posins = q; // (3)
} else {
printf("Key exists %d\n", c);
}
free(posins);
}
而main()
是“主要”
struct bst *T = malloc(sizeof *T);
T->root = NULL;
struct TElem *x = elem_New(10);
bst_Insert(T, c, x);
我正在尝试将一个新元素插入(elem_New
工作正常)到 BST 中,使用辅助函数 bst_Search
返回指向要插入 的正确位置的指针。 (1) 在第一次将 posins
指向 T->root
内存地址时被调用。 (据我所知,它工作正常)。
然后 posins
地址返回给调用函数 bst_Insert
,因为 bst_Search
找到了它返回 NULL
的地方(2)。它在 if
语句中正确设置了 q
。然后在 (3),我希望 posins
指向的位置(在本例中是 T->root 指向的地址)现在应该重定向到新树节点 q
。等同于 T->root = q
,但通过引用使用此调用。
最佳答案
因为你的“posins”在你的“bst_Search”中没有改变
void test(int *p){
// g_c is a gobal int
p = &g_c;
printf("%X ",p);}
调用 test(int *p) 时想想 p的值会变指向g_c吗?不,因为 p 只是一个参数,它不会在过程中改变它的值
my english is poor so i just hope the e.g. code will help your understand~ :)
关于c - 在二叉搜索树中通过引用重定向指针,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44856193/