二叉搜索树（BST）

Question

我在C语言中插入二叉搜索树时遇到了问题。以下是二叉树的定义（请忽略行号）：

struct WordBT {
    char *term;
    struct WordBT *right;
    struct WordBT *left;
};

typedef struct WordBT* WordPtrBT;
WordPtrBT mainListBT;

我的插入函数：

int addlistBT(char *term, char *file, WordPtrBT curr) {
    if (curr == NULL) {
        WordPtrBT temp =  (WordPtrBT)malloc(sizeof(WordPtrBT));
        temp->term = term;
        curr = temp;
        return 1;
    }

    int test = //some test;
    if (test == 0) {
        return 0;
    }
    if (test > 0) {
        addlistBT(term, file, curr->left);
    }
    if (test < 0) {
        addlistBT(term, file, curr->right);
    }
}

然后我调用：

addlistBT(term, file, mainListBT);

我在程序后面遇到了段错误。当我使用gdb进行调试时，看到的是这样的：

                        curr = temp;
(gdb) p temp
$7 = (WordPtrBT) 0x60a2a0
(gdb) p curr
$8 = (WordPtrBT) 0x0
(gdb) p mainListBT
$9 = (WordPtrBT) 0x0
(gdb) n
93                      addfileBT(file, curr->file);
(gdb) p temp
$10 = (WordPtrBT) 0x60a2a0
(gdb) p curr
$11 = (WordPtrBT) 0x60a2a0
(gdb) p mainListBT
$12 = (WordPtrBT) 0x0

现在我的问题是，既然mainListBT被定义为指针，那么为什么它没有被赋予指向temp的指针呢？谢谢。

- Saad Farooq

---

真遗憾KepaniHalo删除了他/她的回答，因为那个是正确的。你把 mainListBT 按值而不是按地址传递给 addlistBT()。因此，调用方指针变量没有任何改变，你的函数又浪费了内存，更加伤人。 - WhozCraig

除了@WhozCraig的评论之外，malloc(sizeof(WordPtrBT))是不正确的。应该是 malloc(sizeof(*temp))。 - keltar

等等，但是mainListBT被定义为指向结构体的指针，所以我没有传递指针吗？ - Saad Farooq

@SaadFarooq C语言始终是按值传递，唯一的问题是它传递的是什么值。函数使用值的副本进行操作，因此更改它将不会对调用方产生任何结果。如果您传递指针-您可以取消引用它并更改它所指向的值（并且在调用方上进行更改，因为它是直接地址），但不能更改指针本身-因为在这种情况下，指针就是您传递给函数的值。如果您传递指向指针的指针-您可以更改原始数据值和指向它的指针，但不能更改您传递的指向指针的指针。等等。但是，您可以“返回”新值。 - keltar

Answer 1

你的程序存在多个错误。

首先，你在做以下等价的操作：

void fn(int x) {
  x = 1;
}

int main() {
  x = 0;
  fn(x);
  // you expect x == 1 here, but you *should* expect 0.
}

当你需要在foo()中传递&x而非x时，你需要向addlistBT()中传递&mainListBT（并更改其签名）。

第二个明显的错误是这行代码：

WordPtrBT temp =  (WordPtrBT)malloc(sizeof(WordPtrBT));

当您需要为结构体分配空间时，它会为指针分配空间。应该是这样：

WordPtrBT temp =  malloc(sizeof(*temp));

或者

WordPtrBT temp =  malloc(sizeof(struct WordBT));

（并且您绝不应该强制转换malloc调用的结果。）

- Employed Russian

---

你的第一个 malloc() 解决方案中是否意味着 sizeof(*temp)？（加上1） - WhozCraig

好的，我所做的更改是：传递&mainListBT并更改签名。我还将malloc行更改为malloc(sizeof(*WordPtrBT))，现在问题是“错误：请求在非结构体或联合体中的某些成员项”。malloc(sizeof(*temp))也是一样的。 - Saad Farooq

@SaadFarooq 请查看更新--它回答了你的问题。 - Employed Russian

Answer 2

你需要做的是： 使用addlistBT(term, file, &mainListBT)进行调用。 然后将addlist函数更改为以下内容：

 81 int addlistBT(char *term, char *file, WordPtrBT *curr){
 86         if(!(*curr)){
 87                 WordPtrBT temp =  (WordPtrBT)malloc(sizeof(struct WordBT));
 88                 temp->term = term;
 92                 *curr = temp;
 94                 return 1;
 95         }
 96         int test = //some test;
 97         if(test == 0){  return 0;}
101         if(test > 0){   addlistBT(term, file, &(*curr)->left);}
104         if(test < 0){   addlistBT(term, file, &(*curr)->right);}
107 }

一些指针魔法...

- Bobb Dizzles