深度使用后遍历递归的第一个搜索会产生意外的输出

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

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

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的上一个递归调用。

其他功能应类似地实现。