매일 하나의 알고리즘 (이 배열 이 특정한 이원 에서 트 리 의 뒷 순 서 를 찾 아 옮 겨 다 니 는 결과 인지 판단 합 니 다)

1446 단어
제목: 정수 배열 을 입력 하여 이 배열 이 특정한 이원 에서 트 리 의 뒤 순 서 를 찾 아 옮 겨 다 니 는 결과 인지 판단 합 니 다.true 로 돌아 가 는 것 이 라면, 그렇지 않 으 면 false 로 돌아 갑 니 다.예 를 들 어 5, 7, 6, 9, 11, 10, 8 을 입력 하 십시오. 이 정수 서열 은 다음 과 같은 나무의 뒷 순서 로 결 과 를 옮 겨 다 니 기 때 문 입 니 다.
    　　8  　　  / \  　　6   10 　　/ \    / \ 　 5  7911 그래서 true 로 돌 아 왔 습 니 다.7, 4, 6, 5 를 입력 하면 나무의 뒷 순 서 를 옮 겨 다 니 는 결과 가 이 순서 가 없 기 때문에 false 로 돌아 갑 니 다.
분석:        이원 탐색 트 리 의 뒷 순 서 를 옮 겨 다 니 는 지 여 부 를 판단 하려 면 뒷 순 서 를 옮 겨 다 니 는 특정한 요 소 를 알 아야 합 니 다. 마지막 요 소 는 뿌리 입 니 다.또한 이원 찾기 트 리, 즉 임의의 원소 의 값 은 왼쪽 노드 의 값 보다 크 고 오른쪽 노드 의 값 보다 작 기 때문이다.따라서 이 서열 을 옮 겨 다 닐 때 뿌리 요소 보다 큰 첫 번 째 값 을 만 날 때 부터 뿌리 요소 까지 모두 이 요소 의 오른쪽 서브 트 리 에 있 고 첫 번 째 요소 부터 이 요소 보다 큰 값 까지 모두 이 요소 의 왼쪽 서브 트 리 에 있 습 니 다.우 리 는 이에 따라 이 서열 에 대해 좌우 자 수 를 구분 한 다음 에 분 단 된 좌우 자 수 를 재 귀 할 수 있다.
bool IsAfer(int squ[], int length)
{
      if(squ == NULL || length <= 0)
            return false;

      int root = squ[length - 1];

      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squ[i] > root)
                  break;
      }

      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squ[j] < root)
                  return false;
      }

      bool left = true;
      if(i > 0)
            left = IsAfer(squ, i);

      bool right = true;
      if(i < length - 1)
            right = IsAfer(squ + i, length - i - 1);

      return (left && right);
}
Optional-Chaning
1. 교통 분류: 편집 거리 (Levenshtein 거리) 자바 실현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage