c++ - 在 C++ 中使用中序遍历对 BST 中的节点进行排序

Question

我一直在追尾寻找节点在 BST 中的等级。我有一个 void 函数，它接受一个元素并使用递归找到节点的等级。
我按以下顺序插入节点:12、3、7、4、11、17、15、9。我的问题是，每当我找到匹配项时，递归就不会停止!这是我的算法:

template <class Comparable>
void AugmentedBinarySearchTree<Comparable>::
Rank(const Comparable & x, BinaryNode<Comparable> *t, int *nodesVisited) const
{  

    // x is the element I am looking for
    // t is the root
    if (t->left != NULL)
    {

    Rank(x, t->left, nodesVisited);                         
    if(t->left->element == x)
        return; 
    }
    cout << "element " << t->element << ", x " << x << ", nodesVisited "<< *nodesVisited << endl;
    if (x == t->element) 
    {               

        cout << "found the node " << endl;
        return ; // exiting the recursion, nodesVisited will be the rank 
                // nodesVisited starts counting from 1
    }

    ++(*nodesVisited); // incrementing the count

    if (t->right != NULL)
    {       
        Rank(x, t->right, nodesVisited);    
    }
}

当我执行 Rank(3) 时它有效，但是当我执行 Rank(4) 时递归不会停止并且我得到不同的结果:

element 3, x 4, nodesVisited 1
element 4, x 4, nodesVisited 2
found the node 
element 12, x 4, nodesVisited 2
element 15, x 4, nodesVisited 3
element 17, x 4, nodesVisited 4
RANK: 5

如何在找到匹配时停止递归？

Answer 1

如果在左子节点中找到该项目，则终止递归。
如果在左侧子树 中找到它，则需要停止。

像这样的事情可能会做到(我修改了它以返回等级，正如你所说的那样)。
在我看来，使用“空”基本情况通常会导致更简单的树递归。
(顺便说一句，完全未经测试的代码。可能存在错误。)

int Rank(const Comparable & x, const BinaryNode<Comparable> *t) const
{
    int rank = 0;
    return FindRank(x, t, &rank) ? rank : -1;
}

// Returns 'true' if and only if the node was found in 't'.
bool FindRank(const Comparable & x, const BinaryNode<Comparable> *t, int* nodesVisited) const
{
    if (t == nullptr)
    {
        return false;
    }

    if (FindRank(x, t->left, nodesVisited))
    {
        return true;
    }

    *nodesVisited += 1;
    return t->element == x || FindRank(x, t->right, nodesVisited);
}