C++函数总是returns同一个指针

Question

我正在尝试实现一个从二叉树中搜索节点的函数和 return 一个指向找到的节点的节点指针，如下所示：

template <class T>
Node<T>* BST<T>::findNode(T a,Node<T>* node)
{
  cout<<node->value<<endl;
  if(a == node->value)
  {
    return node;
  }
  if(a < node->value)
  {
    if(node->left==NULL)
    {
      return NULL;
    }
    findNode(a, node->left);
  }
  if(a > node->value)
  {
    if(node->right==NULL)
    {
      return NULL;
    }
    findNode(a, node->right);
  }
}

在主程序中，我有一个指针（称为bst）指向一个由一些节点填充的二叉搜索树实例。我声明了一个节点指针并调用了这样的函数：

    Node <int> * n = bst-> findNode(3,bst->head);

问题：如果找不到匹配值，该函数运行良好，但是，如果找到匹配值（即转到 if(a==node->value) block, 它总是 return 相同的值（在我的计算机中，节点 n 总是获得 0x6 的值），它是如何发生的以及如何解决这个问题？

TIA!!

Answer 1

您的递归调用实际上并未返回节点：它们需要看起来像

return findNode(a, node->left);

Answer 2

该函数仅针对条件

具有return语句

if(a == node->value)
{
    return node;
}

或像这样的条件

if(node->left==NULL)
{
  return NULL;
}

在所有其他情况下，该函数具有未定义的行为。

函数开头也有这条语句

cout<<node->value<<endl;

以及上面显示的条件都是错误的，因为一般来说 node 可以等于 nullptr.

我会这样写函数

template <class T>
Node<T>* BST<T>::findNode( Node<T> *node, const T &value )
                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
{
    if ( node == nullptr || node->value == value )
    {
        return node;
    }
    else if ( node->value < value )
    {
        return findNode( node->right, value );
    }
    else
    {
        return findNode( node->left, value );
    }
}

C++函数总是returns同一个指针

C++ Function always returns the same pointer

c++

pointers

function

binary-search-tree