在二叉搜索树

Question

考虑下面的结构重定向一个指针引用：

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 Then地址returns呼叫者function bst_Insert，由于bst_Search发现的地方，以便恢复在NULL（2）。它正确地落在if语句集合q之内。然后在（3），我预计posins指向哪里（在这种情况下，T> root根指向的地址）现在应该被重定向到新的树节点q。相当于T->root = q，但使用此调用作为参考。

Answer 1

，因为你的“posins”是改变不了的，当你的“bst_Search”

void test(int *p){ 
// g_c is a gobal int 
p = &g_c; 
printf("%X ",p);} 

做你认为当通话测试（INT * P） p的值将变为点g_c？不，因为p只是一个参数，并且在出过程时不会改变它的值

my english is poor so i just hope the e.g. code will help your understand~ :) 

Answer 2

您更新q的方式是错误的。让我们说，树是这样的：

现在让我们说你搜索10，bst_search(10)（我已删除您的参数，简洁和理解的缘故）

那么，这是你做了什么：

posins = 5 // I am writing numeric values instead of addresses for understanding 

// Now 
10 > 5 
p = p->right // => p = 12 
posins = p->left // => posins = 9, cause p is pointing to 12 

Again, 10 < 12 
So, p = p->left; // => p = 9 
posins = p->left; // posins = NULL 

这是它出了问题，你应该指出，9，但你指着9左侧，这是你应该已经编码的内容：

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; 
    } else { 
     q = q->right; 
     posins = q; 
    } 

    return NULL; 
} 

如有任何疑问，请留言。

Answer 3

主要问题是调用参数无法通过posins = &(T->root);等操作进行更新。

93）函数可能会更改其参数的值，但这些更改不会影响参数的值。另一方面， 可以将指针传递给对象，函数可能会更改指向的对象的值。

所以，如果你想改变调用变量的值为P它必须是*P。
即struct Node **posins应该是struct Node ***posins。

整体代码如下所示。

#include <stdio.h> 
#include <stdlib.h> 

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; 
}; 

int TKeyCmp(TKey a, TKey b){ 
/* return value : 
** a = b : 0 
** a > b : positive value 
** a < b : negative value 
*/ 
    return a < b ? -1 : a > b; 
} 
struct TElem *elem_New(int value){ 
    struct TElem *ep = malloc(sizeof(*ep));//check omitted 
    ep->val = value; 
    return ep; 
} 
void elem_free(struct TElem *ep){ 
    free(ep); 
} 
void print(struct Node *np){ 
    if(np){ 
     print(np->left); 
     printf("(%d, %d)", np->key, np->elem->val); 
     print(np->right); 
    } 
} 

struct TElem *bst_Search(struct bst *T, TKey c, struct Node ***posins){ 
    *posins = &T->root; 

    while (**posins){ 
     int cmp = TKeyCmp(c, (**posins)->key); 
     if(cmp == 0) 
      return (**posins)->elem; 
     else if (cmp < 0) 
      *posins = &(**posins)->left; 
     else 
      *posins = &(**posins)->right; 
    } 

    return NULL; 
} 

void bst_Insert(struct bst *T, TKey c, struct TElem *x){ 
    struct Node **posins; 

    if (!bst_Search(T, c, &posins)) { 
     struct Node *q = malloc(sizeof *q); 
     q->key = c; 
     q->elem = x; 
     q->right = q->left = NULL; 
     *posins = q; 
    } else { 
     elem_free(x);//avoid memory leak 
     printf("Key exists %d\n", c); 
    } 
} 

int main(void){ 
    struct bst *T = malloc(sizeof(*T)); 

    T->root = NULL; 

    bst_Insert(T, 5, elem_New(10)); 
    bst_Insert(T, 1, elem_New(21)); 
    bst_Insert(T, 9, elem_New(42)); 
    bst_Insert(T, 1, elem_New(99));//Key exists 1 
    print(T->root);//(1, 21)(5, 10)(9, 42) 
    //release bst 
}