자주 사용 하 는 데이터 구조 (5): 트 리

나무 에서 원소 의 도 는 그 아이의 개 수 를 가리 키 며 나무의 도 는 그 원소 도의 최대 치 를 가리 키 며 나무의 급 은 나무의 층수, 나무의 뿌리의 급 은 1 을 가리킨다.
     이 진 트 리 의 모든 요소 의 도 는 2 보다 작 으 면 되 고 다른 추가 적 인 제한 이 없다.
     이 진 트 리 의 높이 를 h 로 설정 하면 h 층 을 제외 하고 다른 각 층 (1 ～ h - 1) 의 결 점 수 는 모두 최대 개수 에 달 하고 h 층 의 모든 노드 는 연속 적 으로 가장 왼쪽 에 집중 된다. 이것 이 바로 완전 이 진 트 리 이다. 완전 이 진 트 리 는 통속 적 으로 말 하면 위 에 있 는 불만 이 아래 에 요 소 를 추가 할 수 없 는 나무 입 니 다. 좋 은 점 은 번호 로 지정 한 위치의 요 소 를 찾 을 수 있 고 쌓 는 것 은 완전 이 진 트 리 입 니 다.
     이 진 트 리 는 깊이 가 h 이 고 2h - 1 개의 결점 이 있 는 이 진 트 리 입 니 다.
 
 
     나 무 를 옮 겨 다 니 는 순서 중 순서 중 앞 뒤 는 현재 노드 의 값 을 말 하 며 한 층 씩 옮 겨 다 니 면 대기 열 로 이 루어 집 니 다.
        나무의 높이 얻 기:

 int getHeight(BinaryTreeNode t)
{
   if(!t)return 0;//t        
   int lHeight=getHeight(t->leftChild);
   int rHeight=getHeight(t->rightChild);
   return (lHeigt>rHeight?lHeight:rHeight)++;
} 

 최대 더 미 는 모든 노드 의 값 이 하위 노드 의 값 보다 크 거나 같은 완전 이 진 트 리 를 말한다.
더미 에 요소 삽입:

//       
void Insert(int x)
{
    int i=++Size;//size       
    while(i!=1&&x>heap[i/2])
    {
        heap[i]=heap[i/2];
        i=i/2;
    }
    heap[i]=x;
}

 
/ / 삭제: 루트 노드 를 삭제 하고 마지막 노드 를 추출 합 니 다.

//                

int HeapDelete(int h[])
{
    int x = h[1]; //    ，  
    //-------------   ---------------
    int y = h[CurrSize--]; //      
    int i=1/*    */,pi=2/*i   */;
    while(pi <= CurrSize)
    {
        if(pi < CurrSize && h[pi] < h[pi+1])
            pi++; //            ， pi     
        //  pi   i       
        if(y >= h[pi]) break; //y   h[i]
        h[i] = h[pi]; //           
        i = pi; pi = pi*2;  //       
    }
    h[i] = y;  //  
    return x;  //       
}

 

/*--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --
   ：                 ，          ，
                           ，       
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --*/
void HeapInit(int h[],int cs,int ms)
{
    int i,y,pi;
    CurrSize = cs;  MaxSize = ms;
    for(i = CurrSize/2; i >= 1; i--)
    {
        y = h[i];  //    
        pi = 2*i;  //    
        while(pi <= CurrSize) //           
        {
            if(pi < CurrSize && h[pi] < h[pi+1])
                pi++; //            ， pi     
            //  pi   i       
            if(y >= h[pi]) break; //y   h[i]
            h[pi/2] = h[pi]; //           
            pi = pi*2;  //       
        }
        h[pi/2] = y;  //  
    }
}

 
왼쪽 고목 이나 하프 만 나무 같은 건 안 써 요.