2017-10-19 125 views
1

我真的被困在试图弄清楚这一点。 这是树:在树上搜索一个值

  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是我二叉树类的私有成员。你能看到什么吗?

谢谢。

回答

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

你确定关于'||'吗? 'a ||的结果b'是'bool'。 – Zereges

+0

@Zereges:哎呀!完全正确。 –

1

如果bt为空,则该函数缺少返回语句。此外,由于return语句,最后一个分支未到达。如果btnull,则此功能也可能会崩溃。这可以改变如下。

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

这仍然是错误的。 'return search_for_val(bt-> left(),val);'永远不能执行。 –

+0

@MartinBonner谢谢你的评论,我只是注意到了。 – Codor

+1

如果在右侧找到,也不要搜索左侧。 –