이 진 트 리 의 너 비 를 계산 하 는 두 가지 방식

이 진 트 리 는 매우 특수 한 데이터 구조 로 서 기능 적 으로 큰 역할 을 합 니 다!오늘 은 이 진 트 리 의 가장 큰 폭 을 어떻게 계산 하 는 지 보 자.
귀속 방식 을 채택 하 다
다음은 코드 내용 입 니 다.

int GetMaxWidth(BinaryTree pointer){
    int width[10];//             10
    int maxWidth=0;
    int floor=1;
    if(pointer){
        if(floor==1){//           ，     ++;
            width[floor]++;
            floor++;
            if(pointer->leftChild)
                width[floor]++;
            if(pointer->rightChild)
                width[floor]++;
        }else{
            floor++;
            if(pointer->leftChild)
                width[floor]++;
            if(pointer->rightChild)
                width[floor]++;
        }
        if(maxWidth<width[floor])
            maxWidth=width[floor];
        GetMaxWidth(pointer->leftChild);
        floor--;//      ，     。    Get  ，        。
        GetMaxWidth(pointer->rightChild);
    }
    return maxWidth;
}

비 귀속 방식 을 채택 하 다
비 재 귀 방식 으로 이 진 트 리 의 너 비 를 계산 하려 면 대기 열 을 빌려 야 한다.코드 는 다음 과 같 습 니 다:

int GetMaxWidth(BinaryTree pointer){
    if(pointer==null){
        return 0;
    }
    Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTreeNode>();
    int maxWidth=1;//    
    queue.add(pointer);
    while(true){
        int size=queue.size();//           
        if(size==0){
            break;
        }
        while(size>0){//              
            BinaryTreeNode node=queue.poll();
            size--;
            if(node->leftChild)
                queue.add(node->leftChild);//          
            if(node->rightChild)
                queue.add(node->rightChild);//          
            maxWidth=Math.max(size,queue.size());
        }
    }
    return maxWidth;//                。
}

결론: 어떤 방식 을 사용 하 든 사실은 이 진 트 리 를 옮 겨 다 니 는 특징 을 이용 하여 이 루어 졌 다.