c - 使用递归在c中插入BST

Question

我是 c 的新手，但曾用其他语言编写过程序。我有这段用于插入 BST 的代码:

struct tnode {
  int data;
  struct tnode* left;
  struct tnode* right;
};

struct tnode* addnode(struct tnode* root, int data) {
    if (root == NULL) return talloc(data);
    else if (data < root->data) root->left = addnode(root->left, data);
    else root->right = addnode(root->right, data);
}

该代码运行良好，但试图理解它的工作原理让我发疯。我觉得它不应该正确返回，但我已经对其进行了广泛的测试并且它有效。我的提示是当你用一个值不为 NULL 的根调用 addnode 时，它​​递归地调用 addnode 返回一个新的 tnode 到 root->left 或 root->right。这可以。但是，在递归调用返回后，函数应该从原始调用的那个点恢复执行。然后它应该在 if-else 子句之后恢复。在该子句之后没有返回。当我添加多个项目时，它到底是怎么正确返回的？

我正在尝试并在 if-else 子句之后添加了一个 puts("hello"); ，这搞砸了整个事情并给了我一个段错误:11(不管那是什么意思).

Answer 1

你完全正确。您拥有的函数在 else 语句之后缺少返回调用，这肯定会让您感到困惑。尝试使用以下函数:

struct tnode* addnode(struct tnode* root, int data) {
    if (root == NULL) return talloc(data);
    else if (data < root->data) root->left = addnode(root->left, data);
    else root->right = addnode(root->right, data);
    return root;
}

如果这有帮助，请告诉我。编程愉快!