一千萬個為什麽

搜索

二叉搜索樹中的第N個最大元素

如何在BST中找到第N個最大節點?

在進行BST的In Order Traversal時,我是否保留計數變量?當count = N時返回元素???

最佳答案

這個想法很簡單:按每個節點值的降序遍歷樹。到達第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);

轉載註明原文: 二叉搜索樹中的第N個最大元素