在樹上搜索一個值

Question

我真的被困在試圖弄清楚這一點。 這是樹：

  5 
     /\ 
     4 8 
     //\ 
     11 13 4 
    / \  \ 
    7  2  1 

問： 創建一個函數來搜索上面給出的二叉樹的值。如果找到該值，該函數應返回指向該節點的指針;否則函數應該返回一個空指針。這些參數應該是一個指向二叉樹根節點的指針和一個要搜索的值。

BinaryTree *search_for_val(BinaryTree *bt, int val) 
    { 
     if(!bt->isEmpty()) 
     { 
     if(bt->getData() == val) 
      return bt; 
     else 
      return search_for_val(bt->right(), val); 
     return search_for_val(bt->left(), val); 
     } 
    } 

我已經成功創建了樹，其他一切正常。只是這個。沒有編譯或運行時錯誤。這是邏輯我猜...我改變了很多次，但似乎是如果正確的節點顯示，然後左節點將不會，反之亦然。請幫幫我。

非常感謝您的回覆。我瞭解我出錯的地方，並感謝您的幫助。我還有一個問題......我可以再次發佈，但它與這個有點相關。如果這違反發佈規則，我真的很抱歉。如果是這樣的話，我會把它拿下來再發布。

問：

我必須創建一個函數來刪除葉節點。

該函數將取指針指向二叉樹的根節點和要刪除的值。如果在函數中傳遞的值不是葉，那麼函數應該顯示一個適當的消息。否則，函數應該刪除一個具有該值的節點

void delete_val(BinaryTree *bt, int val) 
{ 
    BinaryTree *temp; 
    temp = search_val(bt, val); 
    //cout << " " << temp->left()->getData() << " " << temp->left()->getData() << endl; 
    if(temp->isLeaf()) 
    { 
     delete temp; 
     cout << " Leaf " << temp->getData() << " deleted" << endl; 
    } 
    else { cout << " " << val << " is not a Leaf" << endl; } 
} 

我用你提供給search_val函數的答案來解決這個問題。問題是，當我想刪除一個實際的葉子，它仍然打印它不是葉子。我認爲這是從我的is_Leaf功能來，但無法查出究竟是什麼wrong.This是我is_Leaf功能：

bool BinaryTree::isLeaf() 
{ 
    return ((this->leftTree == NULL) && (this->rightTree == NULL)); 
} 

leftTree和rightTree是我二叉樹類的私有成員。你能看到什麼嗎？

謝謝。

Answer 1

你的邏輯不能搜索左邊的樹。如果正確的搜索失敗，則需要返回左側的樹。

BinaryTree *search_for_val(BinaryTree *bt, int val) 
    { 
     BinaryTree *result; 
     if(bt->isEmpty()) // Reverse sense of test. 
     result = nullptr; 
     else if (bt->getData() == val) 
     result = bt; 
     else 
     result = search_for_val(bt->right(), val); 
     if (result == nullptr) 
      result = search_for_val(bt->left(), val); 

     return result; 
    } 

Answer 2

如果bt爲空，則該函數缺少返回語句。此外，由於return語句，最後一個分支未到達。如果bt爲null，則此功能也可能會崩潰。這可以改變如下。

BinaryTree *search_for_val(BinaryTree *bt, int val) 
{ 
    BinaryTree* Result = null; 
    if(null != bt && !bt->isEmpty()) 
    { 
     if(bt->getData() == val) 
     { 
      Result = bt; 
     } 
     else 
     { 
      Result = search_for_val(bt->right(), val); 
      if (null == Result) 
      { 
       Result = search_for_val(bt->left(), val); 
      } 
     } 
    } 
    return Result; 
}