c++ - 在树中搜索值

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 函数提供的答案来解决这个问题。问题是当我想删除一个实际的叶子时，它仍然打印出它不是叶子。我认为它来 self 的 is_Leaf 函数，但无法准确指出问题所在。这是我的 is_Leaf 函数:

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

leftTree 和 rightTree 是我的 BinaryTree 类的私有(private)成员。你能看到什么吗？

谢谢。

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