두 갈래 나무(11)----- 두 갈래 나무의 거울, 귀속과 비귀속 방식을 구하다

2106 단어 두 갈래 나무
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. 두 갈래 나무 거울 구하기
예를 들면 다음과 같습니다.
                   A                                                                    A
        B                C                    ====>                    C             B
    D     E                                                                             E       D
(1) 귀속 방식
pRoot이 NULL이면 빈 트리이고
만약에 pRoot이 NULL이 아니라면 pRoot의 좌우 결점을 교환한 다음에 좌우 서브트리의 거울을 구한다.
void  BTreeMirror( BTreeNode_t *pRoot){
    if( pRoot == NULL )
        return ;

    BTreeNode_t *pTemp = pRoot->m_pLeft;
    pRoot->m_pLeft = pRoot->m_pRight;
    pRoot->m_pLeft = pTemp;

    BTreeMirror( pRoot->m_pLeft);
    BTreeMirror( pRoot->m_pRight);
    return;
}

(2) 비귀속 방식
단계 설명: 큐를 사용한 작업
우선 루트 pRoot을 입대시키기;
첫 번째 단계: 대기열이 비어 있지 않을 때 현재 단계의 노드 총수, 즉 현재 대기열의 길이를 가져옵니다.두 번째 단계 실행하기;
두 번째 단계: 현재 층의 노드 총수에 따라 출대하여 노드를 두루 훑어보고 두루 훑어보고 좌우 노드를 교환한다. 만약에 좌우 노드가 존재하면 입대한다.현재 층의 모든 노드를 훑어보았을 때 다음 층을 훑어보고 첫 번째 단계를 실행합니다.
void   BTreeMirror( BTreeNode_t *pRoot){
    if( pRoot == NULL )
        return NULL;

    queue <BTreeNode_t *> que;
    que.push(pRoot);
    int curLevelNodesTotal = 0;
    while( !que.empty()){
        curLevelNodesTotal = que.size();
        int cnt = 0;
        while( cnt < curLevelNodesTotal ){
            ++cnt;
            pRoot = que.front();
            que.pop();
            BTreeNode_t *pTemp = pRoot->m_pLeft:
            pRoot->m_pLeft = pRoot->m_pRight;
            pRoot->m_pRight = pTemp;

            if( pRoot->m_pLeft != NULL)
                que.push( pRoot->m_pLeft);
            if( pRoot->m_pRight != NULL )
                que.push( pRoot->m_pRight);
        }
    }

    return;
}

좋은 웹페이지 즐겨찾기