알고리즘 시험공부) 이진탐색 트리와 연산

실습 - 1: 이진 탐색트리 만들기 

메소드	역할
BinaryTree copy(BinaryTree btree)	매개 변수로 받은 btree를 복사
boolean equal(BinaryTree btree, BinaryTree ctree)	매개변수로 받은 btree와 ctree가 같은지 확인
BinaryTree swap(BinaryTree btree)	btree를 swap
boolean isLeaf()	리프노드인지 확인하는 함수
int size()	이진 트리의 노드의 개수를 구하는 함수
int height()	이진 트리의 높이를 구하는 함수
int numLeaves()	터미널 노드의 개수를 확인하는 함수
void printNode(BinaryTree T)	이진트리T 출력
BinaryTree insertKey(BinaryTree T, String x)	이진트리 T에 x삽입
BinaryTree find(String x)	x원소가 이진트리에 있는지 확인

  이러한 이진 트리 만들기

  

  BinaryTree T = new BinaryTree();

 

  T.insert("S");

  T.insert("J");

  T.insert("B");

  T.insert("D");

  T.insert("U");

  T.insert("M");

  T.insert("R");

  T.insert("Q");

  T.insert("A");

  T.insert("G");

  T.insert("E");

  T.printBST();

 

실습 - 2: 이진트리의 주요 연산

  1) insert(삽입) 알고리즘:

private BinaryTree insert(BinaryTree T, String x){
	//공백 노드일 때 최상위 노드에 삽입
    if(inEmpty(T)){
    	BinaryTree newNode = new BinaryTree(null, x, null);
        return newNode;
    }
    //입력 문자가 data보다 작으면 왼쪽링크에 삽입
    else if(x.compareTo((String) T.data) < 0){
    	//왼쪽 링크에 insertKeyf를 사용해 반환값 저장
        T.llink = insertKey(T.llink, x);
        return T;
    }
    //입력 문자가 data보다 크면 오른쪽링크에 삽입
    else if(x.compareTo((String) T.data) > 0){
    	//오른쪽 링크에 insertKey를 사용해 반환겂 저장
        T.rlink = insertKey(T.rlink, x);
        return T;
    }
    else return T;
}

  2) printNode 알고리즘

private void printNode(BinaryTree T){
	if(T != null){
    	System.out.println("("); //왼쪽 괄호 출력
        printNode(T.llink); // 왼쪽 서브트리 호출
        System.out.print(T.data); //이진트리 데이터 출력
        printNode(T.rlink); //오른쪽 서브트리 호출
        System.out.println(")"); //오른쪽 괄호 출력
    }
}

public void printBST(){
	// printNode 이용해 이진트리 출력
    printNode(btree);
    System.out.println();
}

 3) find 알고리즘

public BinaryTree find(String x){
	BinaryTree T = btree;
    int result;
    
    while(T != null){
    	// 비교 후 data보다 작다면 왼쪽 링크를 쫓아감
        if((result = x.compareTo((String) T.data)) < 0)
        	T = T.llink;
        else if (result == 0) return T;
        else T = T.rlink;
    }
    return T;
}

  4) copy(복사) 알고리즘:

public boolean copy(BinaryTree btree){
	BinaryTree Stree;
    
    Stree = new BinaryTree();
    if(btree == null)
    	Stree = null;
    else
    	llink = copy(Stree);
    return Stree;
}

  5) equal 알고리즘:

public boolean euqal(BinaryTree btree, BinaryTree ctree){
	boolean ans = false;
    if((btree == null) && (ctree != null))
    	ans = true
    else if((btree != null) && (ctree != null)){
    	if(btree.data == ctree.data)
        	ans = equal(btree.llink, ctree.llink);
        if(ans)
        	ans = equal(btree.rlink, ctree.rlink);
    }
    return ans;
}

  6) swap 알고리즘:

public BinaryTree swap(BinaryTree btree){
	BinaryTree Stree;
    BibaryTree ltree;
    BinartTree rtree;
    
    Stree = null;
    if(btree != null){
    	ltree = swap(btree.rlink);
        rtree = swap(btree.llink);
        Stree = new BinaryTree(ltree, btree.data, rtree);
    }
    return Stree;
}

실습 - 3: 이진 트리의 기타 주요 연산

   a. 리프 노드인지 확인하는 함수: isLeaf()

public boolean isLeaf(){
	if(llink == null && rlink == null)
    	return true;
    else return false;
}

   b. 이진 트리의 노드 개수를 구하는 함수: size()

public int size(){
	if(llink == null && rlink == null)	return 1;
    // 왼쪽 링크만 null이면, 오른쪽 랑크 크기 + 루트크기(1)을 더함
    else if(llink == null && rlink != null)	return rlink.size() + 1;
    else if(llink != null && rlink == null) return llink.size() + 1;
    else return 1 + llink.size() + rlink.size();
}

   c. 이진 트리의 리프 노드의 갯수를 구하는 함수: numLeaves()

public int numLeaves(){
	if(llink == null && rlink == null) return 1;
    if(llink == null) return rlink.numLeaves();
    if(rlink == null) return llink.numLeaves();
    return 1 + rlink.numLeaves() + llink.numLeaves();
}