c++ - 使用后序遍历递归的深度优先搜索会产生意外的输出

Question

这个递归函数有问题并产生意外的输出。

它应该遍历二叉树并使用预序深度优先遍历来搜索保存数据 x 的给定节点。

找到节点后，它应该返回。我还有另外两个用于预序和中序遍历的函数，它们运行良好。这个在找到节点时不会停止，而是继续向上调用堆栈，直到它到达根并返回树的根值。
我已经包括了下面的所有功能。第一个是不能正常工作的。

//this one does not work
template<typename T>
inline typename BST<T>::Node* BST<T>::depth_first_postorder_s(Node* root,T x)
{
            //if root is null
            if (!root)
                return nullptr;
             depth_first_postorder_s(root->left,x);
             depth_first_postorder_s(root->right,x);
             if (root->data == x) {
                 return root;
             }
}

template<typename T>
inline typename BST<T>::Node* BST<T>::depth_first_inorder_s(Node* root, T x)
{
            //if root is null
            if (!root)
                return nullptr;
              depth_first_inorder_s(root->left,x);
              if (root->data == x) {
                  return root;
              }
             depth_first_inorder_s(root->right,x);
}

template<typename T>
inline typename BST<T>::Node* BST<T>::depth_first_preorder_s(Node* root,T x)
{
            //if root is null
            if (!root)
                return nullptr;
            if (root->data == x) {
                return root;
            }
             depth_first_preorder_s(root->left,x);
             depth_first_preorder_s(root->right,x);
}

Answer 1

您的代码中的所有功能似乎都无效。但是因此，正如您所说，第一个给您错误的值(value)，因此对该功能的修改应该是-

inline typename BST<T>::Node* BST<T>::depth_first_postorder_s(Node* root,T x)
{


             //if root is null
             if (!root)
                 return nullptr;
             Node *lft = depth_first_postorder_s(root->left,x);
             Node *rgt = depth_first_postorder_s(root->right,x);
             if (root->data == x) {
                 return root;
             } else if(lft != nullptr) {
                 return lft;
             } else { 
                 return rgt;
             }
}

在这里，您需要将节点返回到前一个递归调用，它等于 x .

其他功能也应类似实现。