二進制搜索樹節點總是NULL

Question

我知道這可能看起來很簡單，但我一直在摸索着我的頭幾個小時，試圖弄清楚爲什麼我會這樣做，thisNode總是NULL。因爲這是空的，這意味着沒有任何事情最終會被添加到樹中。有沒有任何想法？ Arghhh

struct node *tra(struct node * start, Type input) 
{ 
    struct node * thisNode = start; 

    if (thisNode == NULL) 
     return thisNode; 
    else 
    { 
     Type current = thisNode -> el; 

     if (strcmp(input, current) > 0) 
      return tra(thisNode -> right, input); 
     else if (strcmp(input, current) < 0) 
      return tra(thisNode -> left, input); 
     else 
     return thisNode; 
    } 
} 

Ta insert(Type input, Ta ta) 
{ 
    if ((find(input, ta)) == FALSE) 
    { 
     struct node *newEl = tra(ta -> head, input); 
     newEl = (struct node*)malloc(sizeof(struct node)); 
     newEl -> el = input; 
     newEl -> left = NULL; 
     newEl -> right = NULL; 
    } 

    return ta; 
} 

Boolean find(Type input, Ta ta) 
{ 
    if (tra(ta -> head, input) == NULL) 
     return FALSE; 
    else 
     return TRUE; 
} 

Answer 1

這裏的問題是：你分配的新節點

 struct node *newEl = tra(ta -> head, input); 
     newEl = (struct node*)malloc(sizeof(struct node)); 

，但隨後的指針墩迷路。你的函數tra應該返回一個指向指針的指針，讓插入函數修改你附加新創建節點的節點。

Answer 2

的問題如下：

當有沒有在BST，這觸發tra：

if (thisNode == NULL) 
    return thisNode; 

所以在insert然後newEl == NULL。

然後你malloc分配指針newEl一個新的值指向分配的內存。但是您返回的原始指針仍具有值NULL（因爲給指針的一個新值的副本不會更改原始指針）。處理這種

選項：

• 返回一個指針的指針（struct node **）（我想你想也需要一個指針作爲參數傳遞給一個指針insert功能）。
• 更改您的支票tra查看下一個元素（以及相應的更改）。對於鏈接列表，它看起來像：if (thisNode->next == NULL) return thisNode;和insert你可以使用newEl->next。儘管對於鏈接列表通常是一個很好的選項，但對於BST來說這是一個更多的努力，因爲您需要返回左側或右側節點是NULL，還是在insert中再次執行此檢查。
  • 請注意 - 您必須使用newEl->left或newEl->right,insert。
• 返回參考 - 這可能是最簡單的選擇。更改tra返回struct node *&並更改newEl聲明struct node *&newEl = ...，這可能是所有。