algorithm - 二叉搜索树中的第 N 个最大元素

Question

如何找到BST中的第N大节点？

我在执行 BST 的有序遍历时是否保留计数变量？当count = N时返回元素???

Answer 1

思路很简单:按照每个节点值的降序遍历树。当您到达第 N 个节点时，打印该节点值。这是递归代码。

void printNthNode(Node* root, int N)
{
   if(root == NULL)
       return;

   static int index = 0; //These will initialize to zero only once as its static

   //For every Node go to the right of that node first.
   printNthNode(root->right, N);


   //Right has returned and now current node will be greatest
   if(++index == N)
   {
    printf("%d\n", root->data);
    return;
   }

   //And at last go to the left
   printNthNode(root->left, N);
}

编辑 - 根据下面的评论，由于静态局部变量，看起来这是一次性调用函数。这可以通过为 index 传递包装器对象来解决，如下所示:

    class WrapIndex {
         public: int index;
    };

并且方法签名将更改为

void printNthNode(Node* root, int N, WrapIndex wrapInd)

现在，我们不需要局部静态变量；而是使用包装器对象的 index。这个电话看起来像

WrapIndex wrapInd = new WrapIndex();
wrapInd.index=0;
printNthNode(root,7,wrapInd);

wrapInd.index=0;
printNthNode(root,2,wrapInd);