在二叉搜索树中插入节点 (C)

Question

我正在尝试编写一个函数来将一个节点插入到二叉搜索树中，我有以下内容：

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

Node *createNode(int key)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

Node *insert(Node *node, int key)
{
    if (node==NULL)
    {
        node = createNode(key);
    }
    else
    {
        if (node->key > key)
        {
            node->left = insert(node->left, key);
        }
        else
        {
            node->right = insert(node->right, key);
        }
    }
    return node;
}

int main(int argc, char* argv[])
{
    Node *root = NULL;
    root = insert(root, 10);

    return 0;
}

我知道这行得通，如果我想将 5 插入根节点为 root 的树中，我可以写 root = insert(root, 5);。我的问题是，我怎样才能编写另一个版本的 insert 来实现与 insert(root, 5); 相同的目的？我尝试了以下但无济于事。

void insert(Node *node, int key)
{
    if (node==NULL)
    {
        node = createNode(key);
    }
    else
    {
        if (node->key > key)
        {
            insert(node->left, key);
        }
        else
        {
            insert(node->right, key);
        }
    }
}

这有什么问题，为什么不起作用？。任何指针（没有双关语意）将不胜感激！

Answer 1

对我来说，你的第一个解决方案很优雅。

现在，如果您想在不利用 return 值的情况下插入，那么一种方法可能是使用指向指针的指针。

类似于：

void insert(Node ** node, int key)
{
    if (*node == NULL)
      *node = createNode(key);
    else if ((*node)->key > key)
      insert(&(*node)->left, key);
    else
      insert(&(*node)->right, key);
}

电话会是

insert(&root, 10);

在二叉搜索树中插入节点 (C)

Inserting nodes in a binary search tree (C)

c

binary-search-tree