정수 서열 이 이 진 트 리 인지 아 닌 지 판단 한 후 순 서 를 옮 겨 다 니 며 결 과 를 찾 습 니 다.

1681 단어 html알고리즘
정의: 두 갈래 정렬 트 리 (Binary Sort Tree) 는 두 갈래 찾기 트 리 라 고도 부른다.그것 은 혹은 빈 나무 이다.또는 다음 과 같은 성질 을 가 진 이 진 트 리: (1) 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 의 값 이 뿌리 노드 의 값 보다 작 습 니 다.(2) 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 이 뿌리 노드 의 값 보다 크다.(3) 왼쪽, 오른쪽 트 리 도 각각 이 진 트 리 이다.
/*
 *               */

public class JudgePostOrderSearchTree {

	static boolean ifIsPostOrderSerachTree(int[] array,
						int start,int end) { // start end-1
		if(array == null || start > end )
			return false;
		if(start == end) //        
			return true;
		int root = array[end-1];
		int i=start;
		while( array[i] < root && i<end-1) //             position
			i++;
		int position = i;
		while( i<end-1) {
			if(array[i] <root) { //   position        ,        
				return false;
			}
			i++;
		}
		//               ,          
		boolean left = true;
		left = ifIsPostOrderSerachTree(array,start,position);
		boolean right = true;
		right = ifIsPostOrderSerachTree(array,position,end-1);
		return (left && right);
			
	} 
	public static void main(String[] args) {
		int[] a = {5,7,6,9,11,10,8};
		System.out.println(ifIsPostOrderSerachTree(a,0,a.length));
		int[] b = {7,4,6,5};
		System.out.println(ifIsPostOrderSerachTree(b,0,b.length));		

	}

}

알고리즘 사상 이 참고 되 었 다.
http://www.cnblogs.com/Jessy/archive/2010/11/03/1868289.html

좋은 웹페이지 즐겨찾기