將新節點插入二叉樹並返回其頭指針

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; 
}