c - 将新节点插入二叉树并返回其头指针

Question

您好，我需要创建一个函数，将新节点插入二叉搜索树并返回指向该树的头/根的指针。我的问题是返回值，我似乎无法弄清楚如何以递归方式返回树头，如下所示。

tree_type insertNode (tree_type tree, int data) {

    tree_type temp = NULL;

    if(!tree)
    {
        temp = (tree_type)malloc(3*sizeof(tree_type)); 

        temp->left = temp->right = NULL;

        temp->data = data;

        tree = temp;

        return ;
    }

    if(data < tree->data)
    {
        insertNode(tree->left, data);
    }
    else if(data > tree->data)
    {
       insertNode(tree->right, data);
    }
}

Answer 1

首先，赋值tree = temp是没有用的，因为tree是一个局部变量，当函数返回时它就会消失。

其次，声明为返回除 void 之外的类型的函数中的 return; 需要进行诊断；它不是有效的 C 或 C++。

而不是

tree = temp;
return;

考虑返回新树:

return temp;

(不需要变量 temp；在这种情况下您可以只使用变量 tree，然后返回树)。

如何返回根节点的问题很简单:

if(data < tree->data)
{
    tree->left = insertNode(tree->left, data);
    return tree;
}

等等。如果您消除变量 temp 并在 malloc 情况下使用 tree，则您的函数只能有一个由 组成的返回点返回树；.

如果 tree->left 为 null，则 insertNode(tree->left, data) 接收一个 null left 参数，因此接收一个新节点。我们必须捕获这个返回值并将其分配给tree->left。如果 tree->left 不为 null，则 insertNode 将仅返回 tree->left，因此赋值只是将相同的值写回到树->左。