나무 한 그루 가 이 진 트 리 인지 아 닌 지 를 판단 합 니 다.

2031 단어 #데이터 구조
개요
이 진 트 리 의 중간 순 서 를 옮 겨 다 닐 때 얻 는 것 은 반드시 하나의 오름차 순 서 였 기 때문에 우 리 는 이 성질 에 따라 중간 순 서 를 이용 하여 판단 할 수 있다.
알고리즘
1) 전역 변수 max 를 무한소 로 설정 합 니 다.2) 나무 가 비어 있 으 면 true 로 돌아간다.3) 그렇지 않 으 면 왼쪽 하위 트 리 가 이 진 트 리 인지 재 귀적 으로 판단 하고 flag 1 로 결 과 를 저장 합 니 다.3) flag 1 이 가짜 또는 루트 노드 키워드 가 왼쪽 트 리 와 같은 키워드 보다 작 으 면 false 로 돌아 갑 니 다.4) 그렇지 않 으 면 오른쪽 하위 트 리 가 이 진 트 리 인지 재 귀적 으로 판단 하고 flag 2 로 결 과 를 저장 합 니 다.5) flag 2 로 되 돌아 갑 니 다.

//           
bool Judge(BinaryTree* root,int& MAX){
    if(root == NULL){//           
        return true;
    }
    bool bst_l,bst_r;
    bst_l = Judge(root->lchild,MAX);//             
    if(!bst_l || MAX >= root->data){
        return false;
    }
    MAX = root->data;
    bst_r = Judge(root->rchild,MAX);//             
    return bst_r;
}

후기
이 진 트 리 의 기본 적 인 스 트 리밍 작업 에 대해 서 는 블 로그: 이 진 트 리 의 구축 과 스 트 리밍 알고리즘 이 이 진 트 리 에 대한 기본 적 인 작업 에 대해 서 는 블 로그: 이 진 트 리 검색 트 리 를 참조 하 십시오.

좋은 웹페이지 즐겨찾기