c++ - 使用 C++ 在二叉搜索树中的第 N 个元素

Question

我正在尝试使用中序遍历在 BST 中找到第 N 个元素。我已将这些节点插入到我的 BST 中:5、2、6、7、3、1。当我寻找第三个元素时，它会给我另一个节点。

这是我对 BST 中第 n 个元素的代码(中序遍历):

template <class Comparable>
BinaryNode<Comparable>* AugmentedBinarySearchTree<Comparable>::
NthElement(BinaryNode<Comparable> *t, int *nodesVisited, int n) const
{
    //BinaryNode<Comparable>*  temp  = new BinaryNode<Comparable>();


    if(t !=NULL)
    {
        if (*nodesVisited == n)
        {
            return t;
        }else
        {
            cout << "going left \n";
            NthElement(t->left, nodesVisited, n);


            cout << "visited element= " << t->element << " nodes= " << *nodesVisited <<endl;
            cout << "going right \n";
            if (*nodesVisited < n)
            {               
                (*nodesVisited)++;
                NthElement(t->right, nodesVisited, n);
            }
            else if(*nodesVisited == n)
            {
                return t;
            }
        }
    }
}

这是一个节点:

template <class Comparable>
class BinaryNode
{
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;
    int m_size;

    BinaryNode(const Comparable & theElement = -1, BinaryNode *lt = NULL, BinaryNode *rt = NULL, int size = -1)
        : element(theElement), left(lt), right(rt), m_size(size)  { }
    friend class AugmentedBinarySearchTree<Comparable>;
    friend class BinarySearchTree<Comparable>;

};

它给了我这个结果:

going left 
going left 
going left 
visited element= 1 nodes= 1
going right 
visited element= 2 nodes= 2
going right 
visited element= 5 nodes= 3
going right 
3 nth element 5

Answer 1

我认为下面的方法更简单:

node* findNodeN(node* head, int* nodesVisited, int n) {
    if (head->lt) {
        node* temp = findNodeN(head->lt, nodesVisited, n);
        if (temp) return temp;
    }
    if (*nodesVisited == n) return head;
    ++(*nodesVisited);
    if (head->rt) {
        node* temp = findNodeN(head->rt, nodesVisited, n);
        if (temp) return temp;
    }
    return nullptr;
}