데이터 구조 제목, 후속 옮 겨 다 니 기

주어진 배열 이 이 진 트 리 의 후속 적 인 결과 인지 아 닌 지 를 판단 하 는 사상 은:
주어진 배열, 배열 의 마지막 차 점 값, 구 덩이 는 뿌리 노드 의 값 으로 정 해 집 니 다. 배열 의 첫 번 째 노드 부터 뿌리 노드 보다 작은 값 은 반드시 왼쪽 서브 트 리 노드 이 고 뿌리 노드 보다 큰 값 은 반드시 오른쪽 서브 트 리 노드 입 니 다.이 어 왼쪽 트 리 의 상황 을 재 귀적 으로 판단 한다. 예 를 들 어 첫 번 째 테스트 사례.5, 7, 6, 9, 11, 10, 8 곶 근 노드 는 8 이다.  5, 7, 6 은 모두 왼쪽 나무 노드 이 고 9, 11, 10 은 모두 오른쪽 나무 노드 이다.이어서 귀속 판단 하 다
package Abc;
/**
 *                    
 * */
public class Bestfor {
	public static void main(String[] args){
		int[] array={9,6,9};
		if(isAfterResult(array,0,array.length-1)){
			System.out.println("             ");
		}else{
			System.out.println("              ");
		}
	}
	//                     ,      
	private static boolean isAfterResult(int[] array,int start,int stop){
		if(null == array){
			throw new NullPointerException();
		}
		//    start  stop    
		if(start < 0 || start >array.length || stop <0 || stop >array.length || start >stop){
			throw new ArrayIndexOutOfBoundsException();
		}
		//           ,             3
		//             3,        ,    。
		//     。        3   ,    
		int count= stop -start +1;
		if(count < 3){
			return true;
		}else if(count == 3){
			//  3   ,           ,            	  		
			if(array[stop] >= array[start] && array[stop]<= array[start+1]){
				return true;
			}else{
				return false;
			}
		}else{
			//      
			int index=-1;
			for(int i=start;i<stop;i++){
				//   i           
				if(array[i]>=array[stop]){
					index=i;
					break;
				}
			}
			if(index == -1 || index ==0){
				return isAfterResult(array,start,stop-1);
			}else{
				return isAfterResult(array,start,index-1) && isAfterResult(array,index,stop-1);
			}
		}
	}

}

좋은 웹페이지 즐겨찾기