c - 二叉搜索树插入不与根相关联

Question

我正在制作一个基本的二叉搜索树及其操作。

为什么我的插入不起作用？

它不接受值，并且我从主发送的根不会与我插入的值关联。

void insert(struct bst* root, int val)
{
    if (root == NULL)
    {
        struct bst* temp = malloc(sizeof(struct bst));
        temp->val = val;
        temp->left = NULL;
        temp->right = NULL;
        root = temp;
    }
    else
    {
        if (root->val > val)
        {
            insert(root->left,val);
        }
        else if (root->val < val)
        {
            insert(root->right,val);
        }
        else
        {
            printf("alredy exits");
        }
    }
}

Answer 1

如果希望函数返回后知道root的值，需要将原型(prototype)改为

void insert(struct bst** root, int val)

并在调用时传递root的地址。然后你改变线路

root = temp;

至

*root = temp;

当然，您需要在代码中更改对 root 的其他访问权限。可能更好的方法是调用函数 root_p 的参数(指向 root 的指针)，然后使用

取消引用它(一旦确定它不为 NULL)

root = *root_p;

这使得整个函数如下所示:

void insert(struct bst **root_p, int val)
{
    if (*root_p == NULL)
    {
        struct bst* temp = malloc(sizeof(struct bst));
        temp->val = val;
        temp->left = NULL;
        temp->right = NULL;
        *root_p = temp;
    }
    else
    {
        root = *root_p;
        if (root->val > val)
        {
            insert(&(root->left),val);
        }
        else if (root->val < val)
        {
            insert(&(root->right),val);
        }
         else
        {
             printf("already exists"); // <<<<< fixed typo here
        }
    }
}

在调用函数中您将拥有

struct bst *root;
for(int ii=0; ii<5; ii++) insert(&root, 1); // for example

编辑了以下 @whozcraig 的评论