在树上搜索一个值
我真的被困在试图弄清楚这一点。 这是树:在树上搜索一个值
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是我二叉树类的私有成员。你能看到什么吗?
谢谢。
你的逻辑不能搜索左边的树。如果正确的搜索失败,则需要返回左侧的树。
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;
}
如果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;
}
这仍然是错误的。 'return search_for_val(bt-> left(),val);'永远不能执行。 –
@MartinBonner谢谢你的评论,我只是注意到了。 – Codor
如果在右侧找到,也不要搜索左侧。 –
你确定关于'||'吗? 'a ||的结果b'是'bool'。 – Zereges
@Zereges:哎呀!完全正确。 –