뭐?정렬 트 리 에서 k 번 째 요 소 를 찾 는 평균 시간 복잡 도 는 O (lgn) 입 니까? |나무.

프로젝트: 트 리 를 찾 는 토대 위 에 현재 하위 트 리 의 요소 개 수 를 기록 하 는 요 소 를 추가 하 였 습 니 다.

//   k         
typedef struct BiNode_K{
    ElemType data;
    struct BiNode_K *lchild,*rchild;
    //                   
    int NbrOfChild;
}BiNode_K,*BiTree_K;

//BST-  
template 
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(Numdata))
    {
        return BST_Insert(&((*Tree)->lchild),Num);
    }
    else if (Num>((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->rchild),Num);
    }
    else
    {
        return false;
    }
}

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

    for (int i=0;i0)
    {
        return false;
    } 
    else
    {
        return true;
    }
}
//            
int CreateKTree1(BiTree_K Tree)
{
    if (Tree==NULL)
    {
        return 0;
    }

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

//     k       
void CreateKTree(BiTree_K *Tree, ElemType Buff[],int len)
{
    BST_Bulid(Tree,Buff,len);

    CreateKTree1(*Tree);
}

//   k   
//  0  k    
ElemType KTreeFindKthNum(BiTree_K Tree,int k)
{
    int NbrOfLeftChild = 0,NbrOfRightChild = 0;

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

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

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

    //            
    if (k<=NbrOfLeftChild)
    {
        KTreeFindKthNum(Tree->lchild,k);
    }
    else if (k==(NbrOfLeftChild+1))
    {
        return Tree->data;
    }
    else
    {
        return KTreeFindKthNum(Tree->rchild,k - NbrOfLeftChild - 1);
    }
}

python 구현:

#             
#                k    ，        O(logn)，             ！
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)