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

Question

此递归函数有问题并产生意外输出。

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

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

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

这里你需要return前一个递归调用的节点等于x。

其他功能类似实现。

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

Depth First search using postorder traversal recursion produces unexpected output

c++

recursion

depth-first-search

binary-search-tree