使用 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

您忽略了问题的一个重要部分。您必须有一种方法可以在对 return 结果进行递归搜索的过程中停止。至少有两种方法可以解决这个问题。您可以 return 一个 "failed" 值（如 NULL）并对其进行测试以确定搜索尚未成功，因此请继续。或者您可以像往常一样继续并抛出异常以一步展开递归。这是第一种方法：

template <class Comparable>
BinaryNode<Comparable>* AugmentedBinarySearchTree<Comparable>::
    NthElement(BinaryNode<Comparable> *root, int *nodesVisited, int n) const
{
  if (!root) return NULL;
  BinaryNode<Comparable> *left = NthElement(root->left, nodesVisited, n);
  if (left) return left;  // Node found in left subtree. Stop searching.
  if (++(*nodesVisited) >= n) return root; // Count and skip right subtree if found.
  return NthElement(root->right, nodesVisited, n);
}

Answer 2

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

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

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

Nth element in Binary Search Tree using C++

c++

algorithm

binary-search-tree