方案：查找樹(shù)的基礎(chǔ)上添加了一個(gè)元素，用來(lái)記錄當(dāng)前子樹(shù)的元素個(gè)數(shù)案站。

//查找第k個(gè)元素轉(zhuǎn)用數(shù)據(jù)結(jié)構(gòu)
typedef struct BiNode_K{
    ElemType data;
    struct BiNode_K *lchild,*rchild;
    //存放的是包括其自身在內(nèi)的子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
    int NbrOfChild;
}BiNode_K,*BiTree_K;

//BST-插入
template <typename Node>
bool BST_Insert(Node **Tree,int Num)
{
    if ((*Tree)==NULL)
    {
        (*Tree) = (Node *)malloc(sizeof(Node));
        (*Tree)->data = Num;
        (*Tree)->lchild = (*Tree)->rchild = NULL;
        return true;
    }
    else if(Num<((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->lchild),Num);
    }
    else if (Num>((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->rchild),Num);
    }
    else
    {
        return false;
    }
}

//BST-建立
template <typename TreePtr>
bool BST_Bulid(TreePtr Tree,ElemType Buff[],int len)
{
    int ErrorCnt=0;

    for (int i=0;i<len;i++)
    {
        if (!BST_Insert(Tree,Buff[i]))
        {
            ErrorCnt++;
        }
    }

    if (ErrorCnt>0)
    {
        return false;
    } 
    else
    {
        return true;
    }
}
//遞歸統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)孩子個(gè)數(shù)
int CreateKTree1(BiTree_K Tree)
{
    if (Tree==NULL)
    {
        return 0;
    }

    return  Tree->NbrOfChild = CreateKTree1(Tree->lchild) + CreateKTree1(Tree->rchild) + 1;
}

//創(chuàng)建查找第k個(gè)元素的排序樹(shù)
void CreateKTree(BiTree_K *Tree, ElemType Buff[],int len)
{
    BST_Bulid(Tree,Buff,len);

    CreateKTree1(*Tree);
}

//查找第k個(gè)數(shù)字
//返回0表示k超出范圍
ElemType KTreeFindKthNum(BiTree_K Tree,int k)
{
    int NbrOfLeftChild = 0,NbrOfRightChild = 0;

    if (Tree==NULL)
    {
        return 0;
    }

    if ((Tree->NbrOfChild)<k)
    {
        return 0;
    }

    if (Tree->lchild!=NULL)
    {
        NbrOfLeftChild = Tree->lchild->NbrOfChild;
    }

    if (Tree->rchild!=NULL)
    {
        NbrOfRightChild = Tree->rchild->NbrOfChild;
    }

    //要查找的數(shù)字在左孩子里面
    if (k<=NbrOfLeftChild)
    {
        KTreeFindKthNum(Tree->lchild,k);
    }
    else if (k==(NbrOfLeftChild+1))
    {
        return Tree->data;
    }
    else
    {
        return KTreeFindKthNum(Tree->rchild,k - NbrOfLeftChild - 1);
    }
}

python實(shí)現(xiàn)：

# 節(jié)點(diǎn)記錄了子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
# 此樹(shù)的優(yōu)點(diǎn)在于可以二分法查找第k小的節(jié)點(diǎn)躬审，平均時(shí)間復(fù)雜度為O(logn)，普通或者平衡二叉樹(shù)都做不到蟆盐！
class MySearchTreeWithCount(MySearchTree):
    # def __init__(self,data):
    #     if type(data) is list:
    #         if len(data) < 2:
    #             self.root = None
    #             return
    #
    #     self.root = Node(data[1])
    #
    #     root = self.root
    #     for elem in data[2:]:
    #         self.insert_node(root,elem)

    # 重載

    def insert_node(self, root, elem):
        root.node_count += 1
        if elem <= root.data:
            if root.lc:
                self.insert_node(root.lc, elem)
            else:
                root.lc = Node(elem)
        else:
            if root.rc:
                self.insert_node(root.rc, elem)
            else:
                root.rc = Node(elem)

    def find_kth_elem(self,root,k):
        # k: 1~n
        if k > root.node_count or k <= 0:
            return None

        lc_num = root.lc.node_count if root.lc else 0

        if k <= lc_num:
            return self.find_kth_elem(root.lc)
        elif lc_num == (k-1):
            return root.data
        else:
            return self.find_kth_elem(root.rc,k - lc_num - 1)