在二叉搜索樹

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 
}