排序二叉樹能解決好多問題，除了基本的插入、刪除、遍歷、查找鍵值以外，還有查找第K小（大）的數的操作。看了一天程序，總算明白了，其實本質和二分查找相似。

從根節點開始查找第r小的數，如果r<=(k的左子樹節點的總個數)，那麼第r小的節點一定在k的左子樹，在k的左子樹繼續查找第r小的節點。 如果r>(k的左子樹節點的總個數+節點k的重複單元個數)，那麼第r小的節點一定在k的右子樹，在k的右子樹繼續查找第r-(k的左子樹節點的總個數+節點k的重複單元個數)小的節點。 如果以上都不滿足，那麼k就是第r小的數，返回k的鍵值。

（其實我很不習慣用靜態數據存儲二叉樹，但考慮到效率和iRachex大牛的建議，還是使用了靜態存儲）

查找以k爲根的樹中，第r小的節點的值：

int find(int k,int r)
{
    if (r<=p[p[k].l].size)
        return find(p[k].l,r);
    else if (r> p[p[k].l].size+p[k].cnt)
        return find(p[k].r,r-(p[p[k].l].size+p[k].cnt));
    return p[k].key;
}