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

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是一个局部变量，其消失在函数返回时。

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

而不是

tree = temp; 
return; 

考虑返回新树：

return temp; 

（无需为变量temp，你可以只使用在这种情况下，变量tree然后return tree） 。

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

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

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

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

Answer 2

这就是你需要的吗？

if(!tree) 
{ 
    temp = (tree_type) malloc(sizeof(*temp)); 
    temp->left = temp->right = NULL; 
    temp->data = data; 

    return temp; 
} 

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