c - 在二叉搜索树中通过引用重定向指针

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 地址返回给调用函数 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);}

调用 test(int *p) 时想想p的值会变指向g_c吗？不，因为 p 只是一个参数，它不会在过程中改变它的值

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