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

Question

如何在BST中找到第N个最大节点？

在进行BST的In Order Traversal时,我是否保留计数变量？当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);

Answer 2

提示:使用inorder遍历树.它可以按排序顺序打印出项目,因此您可以确定找到第N个最大的项目.当你"走路"时保持一个计数器,每次"访问"一个节点时递增.

编辑:虽然IVlad的答案确实更快,但它要求您在节点中保留额外的信息.这个答案不是,但它是O(n).只是指出这是一个权衡,你必须要注意.

Answer 3

在这里看到我的答案.您可以O(log n)平均执行此操作,其中n =节点数.最糟糕的情况仍然O(n)是树不平衡(总是O(log n)如果它是平衡的).O(n)然而,总是顺序遍历.