두 갈래 나무(8)- - 두 갈래 나무 K층의 노드 수와 두 갈래 나무 K층의 잎 노드 수, 귀속 방식과 비귀속 방식을 구하다

1, 두 갈래 나무 정의

typedef struct BTreeNodeElement_t_ {
    void *data;
} BTreeNodeElement_t;


typedef struct BTreeNode_t_ {
    BTreeNodeElement_t *m_pElemt;
    struct BTreeNode_t_    *m_pLeft;
    struct BTreeNode_t_    *m_pRight;
} BTreeNode_t;

2. 두 갈래 트리 K층의 노드 수를 구한다
(1) 귀속 방법:
주어진 루트 pRoot:
만약 pRoot가 비어 있거나 층수 KthLevel<=0이면 빈 트리이거나 요구에 맞지 않으면 0을 되돌려줍니다.
만약 pRoot가 비어 있지 않고 이때 층수 KthLevel==1이면 이때 pRoot가 K층 노드 중 하나이고 1을 되돌려줍니다.
만약 pRoot가 비어 있지 않고 이때 층수 KthLevel > 1이면 pRoot 왼쪽 트리(KthLevel-1) 층절 포인트와 pRoot 오른쪽 트리(KthLevel-1) 층절 포인트를 구해야 합니다.

int  GetBTreeKthLevelNodesTotal( BTreeNode_t *pRoot, int KthLevel){
    if( pRoot == NULL || KthLevel <= 0 )
        return 0;
    if( pRoot != NULL && KthLevel == 1 )
        return 1;

    return (GetBTreeKthLevelNodesTotal( pRoot->m_pLeft, KthLevel-1) + GetBTreeKthLevelNodesTotal( pRoot->m_pRight, KthLevel - 1 ) );
}

(2) 비귀속 방식
대기열 사용:

int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
    if( pRoot == NULL )
        return 0;

    queue <BTreeNode_t *>  que;
    que.push( pRoot );
    int curLevelNodesTotal = 0;
    int curLevel = 0;
   
    while( !que.empty() ){
        ++curLevel;// 
        curLevelNodesTotal = que.size();
        if( curLevel == KthLevel )// 
            break;

        int cntNode = 0;
        while( cntNode < curLevelNodesTotal){// 
            ++cntNode;
            pRoot = que.front();
            que.pop();
            if( pRoot->m_pLeft != NULL )
                que.push(pRoot->m_pLeft);
            if( pRoot->m_pRight != NULL )
                que.push( pRoot->m_pRight);
        }
    }
    
    while ( !que.empty() )
        que.pop();

    if( curLevel == KthLevel )
        return curLevelNodesTotal;
    return 0;  // KthLevel 
}

3. 두 갈래 나무 K층 잎 노드 수 구하기
(1) 귀속 방식
주어진 노드 pRoot:
만약 pRoot가 비어 있거나 층수 KthLevel<=0이면 빈 나무이거나 층수가 불법이면 0을 되돌려줍니다.
pRoot가 비어 있지 않고 이때 KthLevel==1 레벨이 되면 잎 노드 여부를 판단해야 합니다.
만약 pRoot 좌우 서브트리가 모두 비어 있다면 pRoot는 K층 잎 노드 중 하나이고 1을 되돌려줍니다.
만약에 pRoot 좌우 하위 나무 중 하나가 존재한다면 pRoot는 잎 노드가 아니면 0으로 되돌아간다.
만약 pRoot가 비어 있지 않고 이때 층수 KthLevel > 1이 되면, KthLevel-1층의 왼쪽 트리와 오른쪽 트리 결점을 되돌려야 합니다.

int GetBTreeKthLevelLeafNodesTotal( BTreeNode_t *pRoot, int KthLevel){
    if( pRoot == NULL || KthLevel <= 0 )
        return 0;

    if( pRoot != NULL && KthLevel == 1 ){
        if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL )
            return 1;
        else
            return 0;
    }

    return ( GetBTreeKthLevelLeafNodesTotal(  pRoot->m_pLeft,  KthLevel - 1) + GetBTreeKthLevelLeafNodesTotal( pRoot->m_pRight, KthLevel -1) );
}

(2) 비귀속 방식
대열을 빌려 실현하다

int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
    if( pRoot == NULL )
        return 0;

    queue <BTreeNode_t *>  que;
    que.push( pRoot );
    int curLevelNodesTotal = 0;
    int curLevel = 0;
   
    while( !que.empty() ){
        ++curLevel;// 
        curLevelNodesTotal = que.size();
        if( curLevel == KthLevel )// 
            break;

        int cntNode = 0;
        while( cntNode < curLevelNodesTotal){// 
            ++cntNode;
            pRoot = que.front();
            que.pop();
            if( pRoot->m_pLeft != NULL )
                que.push(pRoot->m_pLeft);
            if( pRoot->m_pRight != NULL )
                que.push( pRoot->m_pRight);
        }
    }
    
    if( curLevel == KthLevel ){
        int cntNode = 0;
        int leafNodes = 0;
        while( cntNode < curLevelNodesTotal ){
                ++cntNode;
                pRoot = que.front();
                que.pop();
                
               if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL )
                    leafNodes++;
        }
        return leafNodes; // 
    }

   return 0;  // KthLevel 
}