[자료구조&알고리즘] 트리, 이진 트리, 이진 검색 트리

트리

• 비선형구조
• 그래프는 사이클이 있고, 트리는 사이클이 존재하지 않음
• 계층 관계를 나타내는 자료구조
• 트리는 저장위치를 찾아서 저장해야 하고, 삭제시 트리의 일부를 재구성해야하므로 링크드 리스트보다 추가/삭제 시간이 더 걸리는 대신 배열이나 링크드 리스트에 비해 검색과 정렬 기능이 더 뛰어남

용어

노드(node)	마디	A, B, C, D, E, F, G
간선(edge)	가지, 링크
루트(root)	트리의 가장 윗부분에 위치하는 노드	A
리프(leaf) 단말 노드(terminal node) 바깥 노드(external node)	트리의 가장 아랫부분(가장 마지막)에 위치하는 노드	D, E, F, G
간 노드(non-terminal node) 안쪽 노드	루트 포함, 리프가 아닌 노드	A, B, C
자식(child) 부모(parent) 형제(sibling) 조상(ancestor) 자손(descendant)	리프는 자식을 가질 수 없음 루트는 부모를 가질 수 없음
레벨(level)	루트로부터 얼마나 떨어져 있는지에 대한 값 = 노드의 층 시작 레벨이 0일때는 level: 2	3
깊이(depth)	루트 노드부터 해당 노드까지의 경로에 있는 엣지(간선)의 수 = 몇 번 걸쳐서 내려오느냐	A의 depth: 0 D의 depth: 2
높이(length)	루트로부터 가장 멀리 떨어진 리프까지의 거리 (리프 레벨의 최댓값)	2
차수(degree)	노드가 갖는 자식의 수 차수가 0 = 단말 노드 트리의 차수 = 노드의 차수 중에서 가장 큰 차수	2
서브 트리(subtree)	루트가 사라질 때 생기는 트리	B, C 서브 트리
널 트리(null tree)	노드, 가지가 없는 트리

순서 트리 탐색

1. 너비 우선 탐색

• 낮은 레벨에서 시작해 왼 → 오 방향으로 검색 후 한개의 레벨이 끝나면 다음 레벨로 내려감
• A → B → C → D → E → F → G

2. 깊이 우선 탐색

• 리프까지 내려가면서 검색하는 것을 우선 순위로 탐색하며, 리프에 도달하면 부모에게 돌아감 이후 반복
• A → B → D , B → E → B → A → C → F → C → G → C → A
  대략 이런식으로 진행, 언제 노드를 방문할지는 3가지로 A노드를 총 3번 지나감

3. 순회

전위 순회 (Preorder)

• 루트 → 왼 → 오
• A → B → D → H → I → E → C → F → G
• A를 기준으로 B, C 노드 트리가 되고, B가 루트가 될 때 D, E 노드 트리가 됨, D가 루트가 되면 H, I 트리가 되며 이것을 기준으로 전위 순회를 함

중위 순회 (Inorder)

• 왼 → 루트 → 오
• H → D → I →  B → E → A → F → C → G

후위 순회 (Postorder)

• 왼 → 오 → 루트
• H → I → D → E → B → F → G → C → A

---

이진 트리 & 완전 이진 트리

이진 트리

• binary tree
• 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리

완전 이진  트리

• complete binary tree
• 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져있는 이진 트리
• 높이가 k인 완전 이진 트리가 가질 수 있는 노드의 최댓값: 2^k+1 - 1
• n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log n

---

이진 검색 트리

• binary search tree
• 이진 트리가 다음 조건을 만족하면 됨
• treeSet 사용

2022.10.26 - [프로그래밍 언어/Java] - [Java] API_ Collection Framework (List, Set, Map)

1. 어떤 노드의 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 함
2. 오른쪽 서브 트리 노드의 값은 노드 N의 키 값보다 커야 함
3. 같은 키 값을 갖는 노드는 없음

생성

노드 Node<K, V> 클래스

	//노드
	static class Node<K, V> {
		private K key;
		private V data;
		private Node<K, V> left; //왼쪽 자식 노드
		private Node<K, V> right; //오른쪽 자식 노드
		
		//생성자
		public Node(K key, V data, Node<K, V> left, Node<K, V> right) {
			super();
			this.key = key;
			this.data = data;
			this.left = left;
			this.right = right;
		}
		
		//키 값을 반환
		K getKey() {
			return key;
		}
		
		//데이터를 반환
		V getValue() {
			return data;
		}
		
		//데이터를 출력
		void print() {
			System.out.println(data);
		}
	} //end Node class

이진검색트리 BinTree<K, V> 클래스

	private Node<K, V> root; //루트
	private Comparator<? super K> comparator = null; //비교자
	
    //생성자
	//노드 키 값의 대소 관계를 자연 순서에 따라 수행
	//비교자를 설정하지 않으므로 필드 comparator의 값 = null
	public BinTree() { //루트를 null로 설정하여 노드가 하나도 없는 이진 검색 트리 생성
		root = null;
	}
	
    //생성자
	//노드 키 값의 대소 관계를 판단할 때 비교자를 전달받아서 수행
	public BinTree(Comparator<? super K> c) {
		this(); //인수를 전달받지 않으면 위의 생성자 실행
		comparator = c;
	}
	
	//두 키 값을 비교하는 comp 메서드
	private int comp(K key1, K key2) {
		return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2) //key1을 Comparable<K>로 형변환, compareTo로 key2와 비교
				: comparator.compare(key1, key2);
	}

---

검색

• 노드 값: 유일한 값
  왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값
• K값을 찾는 과정, 루트는 가운데 노드
  루트 == K : 찾음, 종료
  루트 < K : 오른쪽 서브 트리
  루트 > K : 왼쪽 서브 트리

	//키에 의한 검색
	public V search(K key) {
		Node<K, V> p = root; //루트에 주목
		
		while(true) {
			if(p == null) //더이상 진행하지 않으면
				return null; //검색 실패
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키를 비교
			if(cond == 0)
				return p.getValue(); //검색 성공
			else if (cond < 0) //key쪽이 작으면
				p = p.left; //왼쪽 서브트리에서 검색
			else //key 쪽이 크면
				p = p.right; //오른쪽 서브트리에서 검색
		}
	}

• 위의 코드는 key와 노드 p를 비교한 변수 cond를 사용하므로
  cond가 음수 = 루트가 더 크다
  cond가 양수 = 찾는 K가 더 크다

---

삽입

• 노드를 삽입한 다음 트리의 형태가 이진 검색 트리의 조건을 유지해야 함
• 삽입할 노드의 키와 같은 값을 가지는 노드가 이미 있다면 노드를 삽입해서는 안 됨

삽입 알고리즘

1. 루트를 선택

2. key와 선택 노드의 키 값을 비교
     - 값이 같으면 삽입 실패
     - 값이 다르면

        1. key < 삽입할 값

            - 왼쪽 자식 노드가 없는 경우 노드 삽입

            - 있는 경우 선택한 노드를 왼쪽 자식 노드로 옮김

        2. key > 삽입할 값

            - 오른쪽 자식 노드가 없는 경우 노드 삽입

            - 있는 경우 선택한 노드를 오른쪽 자식 노드로 옮김

3. 2로 되돌아 감

	//node를 루트로 하는 서브 트리에 노드<K, V>를 삽입
	private void addNode(Node<K, V> node, K key, V data) {
		int cond = comp(key, node.getKey()); //key와 노드 p를 비교
		if(cond == 0)
			return; //삽입 실패, 이미 있음
		else if(cond < 0) { //key값이 삽입할 값보다 작음
			if(node.left == null)
				node.left = new Node<K, V>(key, data, null, null);
			else
				addNode(node.left, key, data); //왼쪽 서브 트리에 주목
		} else { //key값이 삽입할 값보다 큼
			if(node.right == null)
				node.right = new Node<K, V>(key, data, null, null);
			else
				addNode(node.right, key, data); //오른쪽 서브 트리에 주목
		}
	}

	//노드를 삽입
	public void add(K key, V data) {
		if(root == null) //트리가 비어있는 상태
			root = new Node<K, V>(key, data, null, null);
		else //addNode 메서드를 호출하여 노드를 삽입
			addNode(root, key, data);
	}

---

삭제

//키 값이 key인 노드를 삭제
	public boolean remove(K key) {
		Node<K, V> p = root; //스캔 중인 노드 (맨 처음은 루트)
		Node<K, V> parent = null; //스캔 중인 노드의 부모 노드
		boolean isLeftChild = true; //p는 부모 노드의 왼쪽 자식인가?
		
		//key의 위치 찾기
		while(true) {
			if(p == null)  //키 값 없음 or 비어있음
				return false; //진행 안 함
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키 값을 비교
			if(cond == 0) //같으면 검색 성공
				break;
			else {
				parent = p; //가지로 내려가기 전 부모를 설정 (맨 처음은 루트를 부모로 설정)
				if(cond < 0) { //key값이 노드 p보다 작으면
					isLeftChild = true; //왼쪽 자식으로 내려감
					p = p.left; //왼쪽 서브 트리에서 검색
				} else {
					isLeftChild = false;
					p = p.right; //오른쪽 서브트리에서 검색
				}
			} //end else
		} //end while
		//여기까지 마치면 key의 위치를 찾음
		//p == key, parent == p의 부모 노드
        
        ... 삭제 코드 아래에서 추가 ...
        
	}

삭제 노드가 단말 노드인 경우

1. 탐색 후 삭제
2. 삭제한 노드의 부모의 링크 값을
     ▶ NULL로 저장

 

삭제할 노드에 자식 노드가 하나 있는 경우

1. 탐색 후 삭제
2. 삭제한 노드의 부모의 링크 값을
     ▶ 삭제한 노드의 자식 노드로 저장

//1. 단말 노드인 경우, 자식 노드가 하나인 경우
	if(p.left == null) { //p에는 왼쪽 자식이 없음
		if(p == root)
			root = p.right;
		else if(isLeftChild)
			parent.left = p.right; //부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
			//기존에 p.right 포인터를 parent.left에 연결
		else
			parent.right = p.right; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
			//기존에 p.right 포인터를 parent.right에 연결
		
	} else if(p.right == null) { //p에는 오른쪽 자식이 없음
		if(p == root)
			root = p.left;
		else if(isLeftChild)
			parent.left = p.left; //부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
		else 
			parent.right = p.left; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
	} //end if

 

삭제할 노드(왼쪽에 위치)에 자식 노드가 두 개 있는 경우

1. 탐색 후 삭제 
2. 삭제한 노드의 왼쪽 자식 중 가장 큰 값
 ▶ 삭제한 노드에 위치 시킴
     ▶ 공백이 생긴 트리는 다시 정렬

 

삭제할 노드(오른쪽에 위치)에 자식 노드가 두 개 있는 경우

1. 탐색 후 삭제
2. 삭제한 노드의 오른쪽 자식 중 가장 작은 값
     ▶삭제한 노드에 위치 시킴
     ▶공백이 생긴 트리는 다시 정렬

//2. 자식 노드가 두 개인 경우
	else {
		parent = p;
		Node<K, V> left = p.left; //서브 트리 가운데 가장 큰 노드
		isLeftChild = true;
		while(left.right != null) { //가장 큰 노드 left를 검색
			parent = left;
			left = left.right;
			isLeftChild = false;
		}
		
		p.key = left.key; //left의 키 값을 p로 옮김
		p.data = left.data; //left의 데이터를 p로 옮김
		if(isLeftChild)
			parent.left = left.left; //left 삭제
		else
			parent.right = left.left; //left 삭제
	} //end else

---

출력

• 오름차순으로 출력하기 위해 중위순회 사용
• root를 매개변수로 하여 printSubTree 메서드 호출

오름차순

	//node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력
	private void printSubTree(Node node) {
		if(node != null) {
			printSubTree(node.left);
			System.out.println(node.key + " " + node.data);
			printSubTree(node.right);
		}
	}
	
	//모든 노드를 키 값의 오름차순으로 출력
	public void print() {
		printSubTree(root);
	}

내림차순

	//node를 루트로 하는 서브 트리의 노드를 키 값의 내림차순으로 출력
	private void printSubTreeReverse(Node node) {
		if(node != null) {
			printSubTreeReverse(node.right); //오른쪽 서브트리를 키값의 오름차순으로
			System.err.println(node.key + " " + node.data);
			printSubTreeReverse(node.left); //왼쪽 서브트리를 키값의 오름차순으로
		}
	}
	
	//모든 노드를 키 값의 내림차순으로 출력
	public void printReverse() {
		printSubTreeReverse(root);
	}

최소, 최대 key 값을 갖는 노드

	//최소 key값을 갖는 노드 반환
	private Node<K, V> getMinNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.left != null) //p의 왼쪽에 값이 없으면 p가 가장 작은 것
				p = p.left;
			return p;
		}
	}
	
	//최대 key값을 갖는 노드 반환
	private Node<K, V> getMaxNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.right != null) //p의 오른쪽에 값이 없으면 p가 가장 큰 것
				p = p.right;
			return p;
		}
	}

//가장 작은 키 값 반환
	public K getMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getKey();
	}
	
	//가장 작은 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getValue();
	}
	
	
	//가장 큰 키 값을 반환
	public K getMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getKey();
	}
	
	//가장 큰 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getValue();
	}

---

전체 코드

BinTree.java

package chap10_1;

import java.util.Comparator;

//이진 검색 트리
public class BinTree<K, V> {
		
	//노드
	static class Node<K, V> {
		private K key;
		private V data;
		private Node<K, V> left; //왼쪽 자식 노드
		private Node<K, V> right; //오른쪽 자식 노드
		
		//생성자
		public Node(K key, V data, Node<K, V> left, Node<K, V> right) {
			super();
			this.key = key;
			this.data = data;
			this.left = left;
			this.right = right;
		}
		
		//키 값을 반환
		K getKey() {
			return key;
		}
		
		//데이터를 반환
		V getValue() {
			return data;
		}
		
		//데이터를 출력
		void print() {
			System.out.println(data);
		}
	} //end Node class
	
	private Node<K, V> root; //루트
	private Comparator<? super K> comparator = null; //비교자
	
	//생성자
	//노드 키 값의 대소 관계를 자연 순서에 따라 수행
	//비교자를 설정하지 않으므로 필드 comparator의 값 = null
	public BinTree() { //루트를 null로 설정하여 노드가 하나도 없는 이진 검색 트리 생성
		root = null;
	}
	
	//생성자
	//노드 키 값의 대소 관계를 판단할 때 비교자를 전달받아서 수행
	public BinTree(Comparator<? super K> c) {
		this(); //인수를 전달받지 않으면 위의 생성자 실행
		comparator = c;
	}
	
	//두 키 값을 비교하는 comp 메서드
	private int comp(K key1, K key2) {
		return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2) //key1을 Comparable<K>로 형변환, compareTo로 key2와 비교
				: comparator.compare(key1, key2);
	}
	
	//키에 의한 검색
	public V search(K key) {
		Node<K, V> p = root; //루트에 주목
		
		while(true) {
			if(p == null) //더이상 진행하지 않으면
				return null; //검색 실패
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키를 비교
			if(cond == 0)
				return p.getValue(); //검색 성공
			else if (cond < 0) //key쪽이 작으면
				p = p.left; //왼쪽 서브트리에서 검색
			else //key 쪽이 크면
				p = p.right; //오른쪽 서브트리에서 검색
		}
	}
	
	//node를 루트로 하는 서브 트리에 노드<K, V>를 삽입
	private void addNode(Node<K, V> node, K key, V data) {
		int cond = comp(key, node.getKey()); //key와 노드 p를 비교
		if(cond == 0)
			return; //삽입 실패, 이미 있음
		else if(cond < 0) { //key값이 삽입할 값보다 작음
			if(node.left == null)
				node.left = new Node<K, V>(key, data, null, null);
			else
				addNode(node.left, key, data); //왼쪽 서브 트리에 주목
		} else { //key값이 삽입할 값보다 큼
			if(node.right == null)
				node.right = new Node<K, V>(key, data, null, null);
			else
				addNode(node.right, key, data); //오른쪽 서브 트리에 주목
		}
	}
	
	//노드를 삽입
	public void add(K key, V data) {
		if(root == null) //트리가 비어있는 상태
			root = new Node<K, V>(key, data, null, null);
		else //addNode 메서드를 호출하여 노드를 삽입
			addNode(root, key, data);
	}
	
	//키 값이 key인 노드를 삭제
	public boolean remove(K key) {
		Node<K, V> p = root; //스캔 중인 노드 (맨 처음은 루트)
		Node<K, V> parent = null; //스캔 중인 노드의 부모 노드
		boolean isLeftChild = true; //p는 부모 노드의 왼쪽 자식인가?
		
		//key의 위치 찾기
		while(true) {
			if(p == null)  //키 값 없음 or 비어있음
				return false; //진행 안 함
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키 값을 비교
			if(cond == 0) //같으면 검색 성공
				break;
			else {
				parent = p; //가지로 내려가기 전 부모를 설정 (맨 처음은 루트를 부모로 설정)
				if(cond < 0) { //key값이 노드 p보다 작으면
					isLeftChild = true; //왼쪽 자식으로 내려감
					p = p.left; //왼쪽 서브 트리에서 검색
				} else {
					isLeftChild = false;
					p = p.right; //오른쪽 서브트리에서 검색
				}
			} //end else
		} //end while
		//여기까지 마치면 key의 위치를 찾음
		//p == key, parent == p의 부모 노드
		
		
		//1. 단말 노드인 경우, 자식 노드가 하나인 경우
		if(p.left == null) { //p에는 왼쪽 자식이 없음
			if(p == root)
				root = p.right;
			else if(isLeftChild)
				parent.left = p.right; //부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
				//기존에 p.right 포인터를 parent.left에 연결
			else
				parent.right = p.right; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
				//기존에 p.right 포인터를 parent.right에 연결
			
		} else if(p.right == null) { //p에는 오른쪽 자식이 없음
			if(p == root)
				root = p.left;
			else if(isLeftChild)
				parent.left = p.left; //부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
			else 
				parent.right = p.left; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
		} //end if
		
		//2. 자식 노드가 두 개인 경우
		else {
			parent = p;
			Node<K, V> left = p.left; //서브 트리 가운데 가장 큰 노드
			isLeftChild = true;
			while(left.right != null) { //가장 큰 노드 left를 검색
				parent = left;
				left = left.right;
				isLeftChild = false;
			}
			
			p.key = left.key; //left의 키 값을 p로 옮김
			p.data = left.data; //left의 데이터를 p로 옮김
			if(isLeftChild)
				parent.left = left.left; //left 삭제
			else
				parent.right = left.left; //left 삭제
		} //end else
		
		return true;
	} //end remove

	//node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력
	private void printSubTree(Node node) {
		if(node != null) {
			printSubTree(node.left);
			System.out.println(node.key + " " + node.data);
			printSubTree(node.right);
		}
	}
	
	//모든 노드를 키 값의 오름차순으로 출력
	public void print() {
		printSubTree(root);
	}
	
	//node를 루트로 하는 서브 트리의 노드를 키 값의 내림차순으로 출력
	private void printSubTreeReverse(Node node) {
		if(node != null) {
			printSubTreeReverse(node.right); //오른쪽 서브트리를 키값의 오름차순으로
			System.err.println(node.key + " " + node.data);
			printSubTreeReverse(node.left); //왼쪽 서브트리를 키값의 오름차순으로
		}
	}
	
	//모든 노드를 키 값의 내림차순으로 출력
	public void printReverse() {
		printSubTreeReverse(root);
	}
	
	
	//최소 key값을 갖는 노드 반환
	private Node<K, V> getMinNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.left != null) //p의 왼쪽에 값이 없으면 p가 가장 작은 것
				p = p.left;
			return p;
		}
	}
	
	//최대 key값을 갖는 노드 반환
	private Node<K, V> getMaxNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.right != null) //p의 오른쪽에 값이 없으면 p가 가장 큰 것
				p = p.right;
			return p;
		}
	}
	
	
	//가장 작은 키 값 반환
	public K getMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getKey();
	}
	
	//가장 작은 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getValue();
	}
	
	
	//가장 큰 키 값을 반환
	public K getMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getKey();
	}
	
	//가장 큰 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getValue();
	}
	
}

BinTreeTester.java

package chap10_1;

import java.util.Scanner;

//이진 검색 트리 클래스 BinTree<K, V>의 이용 예
public class BinTreeTester {

	static Scanner scan = new Scanner(System.in);

	//데이터(회원번호 + 이름)
	static class Data {
		static final int NO = 1; //번호를 입력 받습니까?
		static final int NAME = 2; //이름을 입력 받습니까?

		private int no; //회원번호
		private String name; //이름

		//키 값
		Integer keyCode() {
			return no;
		}
		
		//문자열을 반환
		public String toString() {
			return "(" + no + ") " + name;
		}

		//데이터를 입력
		void scanData(String guide, int sw) {
			System.out.println(guide + "할 데이터를 입력하세요.");

			if((sw & NO) == NO) {
				System.out.print("번호: ");
				no = scan.nextInt();
			}
			if((sw & NAME) == NAME) {
				System.out.print("이름: ");
				name = scan.next();
			}
		}
	} //end Data class

	//메뉴 열거형
	enum Menu {
		ADD("삽입"),
		REMOVE("삭제"),
		SEARCH("검색"),
		PRINT("표시"),
		TERMINATE("종료");

		private final String message; //출력할 문자열

		static Menu MenuAt(int idx) { //서수가 idx인 열거를 반환
			for(Menu m : Menu.values())
				if(m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) { //생성자
			message = string;
		}

		String getMessage() { //출력할 문자열을 반환
			return message;
		}
	} //end enum

	//메뉴 선택
	static Menu SelectMenu() {
		int key;

		do {
			for(Menu m : Menu.values()) {
				System.out.printf("(%d) %9s   ", m.ordinal(), m.message);
				if((m.ordinal() % 3) == 2 &&
						m.ordinal() != Menu.TERMINATE.ordinal()	)
					System.out.println();
			}
			System.out.print("  : ");
			key = scan.nextInt();
		} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());
		return Menu.MenuAt(key);
	} //end SelectMenu

	public static void main(String[] args) {
		Menu menu;
		Data data;
		Data ptr;
		Data temp = new Data(); //입력용 데이터
		
		BinTree<Integer, Data> tree = new BinTree<Integer, Data>();
		
		do {
			switch (menu = SelectMenu()) {
				case ADD :
					data = new Data();
					data.scanData("삽입", Data.NO | Data.NAME);
					tree.add(data.keyCode(), data);
					break;
					
				case REMOVE :
					temp.scanData("삭제", Data.NO);
					tree.remove(temp.keyCode());
					break;
					
				case SEARCH :
					temp.scanData("검색", Data.NO);
					ptr = tree.search(temp.keyCode());
					if(ptr != null) {
						System.out.println("그 번호의 이름은 " + ptr + "입니다.");
					} else {
						System.out.println("해당 데이터가 없습니다.");
					} break;
					
				case PRINT :
					tree.print();
					break;
			}
		} while (menu != Menu.TERMINATE);
	} //end main
}

Quiz3.java - 비교자 사용

package chap10_1;

import java.util.Scanner;
import java.util.Comparator;
// 이진검색트리 클래스 BinTree<K,V>의 사용 예 (comparator를 사용)

class Quiz3 {
	static Scanner stdIn = new Scanner(System.in);

	// 데이터(회원번호+이름)
	static class Data {
		public static final int NO = 1; // 번호를 입력 받습니까?
		public static final int NAME = 2; // 이름을 입력 받습니까?

		private Integer no; // 회원번호 (키 값)
		private String name; // 이름

		// 키 값
		Integer keyCode() {
			return no;
		}

		// 문자열을 반환합니다.
		public String toString() {
			return name;
		}

		// 데이터를 입력 받음
		void scanData(String guide, int sw) {
			System.out.println(guide + "하는 데이터를 입력하세요.");

			if ((sw & NO) == NO) {
				System.out.print("번호：");
				no = stdIn.nextInt();
			}
			if ((sw & NAME) == NAME) {
				System.out.print("이름：");
				name = stdIn.next();
			}
		}
	}

	// 메뉴열거형
	enum Menu {
		ADD("삽입 "), REMOVE("삭제"), SEARCH("검색"), PRINT("출력"), TERMINATE("종료");

		private final String message; // 표시용 문자열

		static Menu MenuAt(int idx) { // 서수가 idx인 열거를 반환
			for (Menu m : Menu.values())
				if (m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) { // 생성자
			message = string;
		}

		String getMessage() { // 출력용 문자열 반환
			return message;
		}
	}

	// 메뉴선택
	static Menu SelectMenu() {
		int key;
		do {
			for (Menu m : Menu.values()) {
				System.out.printf("(%d) %s  ", m.ordinal(), m.getMessage());
				if ((m.ordinal() % 3) == 2 && m.ordinal() != Menu.TERMINATE.ordinal())
					System.out.println();
			}
			System.out.print("：");
			key = stdIn.nextInt();
		} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());

		return Menu.MenuAt(key);
	}

	public static void main(String[] args) {
		Menu menu; // 메뉴
		Data data; // 추가용 데이터 참조
		Data ptr; // 검색용 데이터 참조
		Data temp = new Data(); // 입력 받기용 데이터

		//기존에는 자연 순서로 판단해서 아래처럼 BinTree 객체 생성 후 사용
		//BinTree<Integer, Data> tree = new BinTree<Integer, Data>();
		
		//compare 메서드를 구현한 클래스 작성 - 내림차순
		class IntegerDecComparator implements Comparator<Integer> {
			public int compare(Integer n1, Integer n2) {
				return (n1 > n2) ? 1 : (n1 < n2) ? -1 : 0;
			}
		}

		//IntegerDecComparator 인스턴스 생성
		// 정수의 내림차순으로 순서매기기를 수행하는 comparator
		final IntegerDecComparator INT_DEC_COMP = new IntegerDecComparator();
		BinTree<Integer, Data> tree = new BinTree<Integer, Data>(INT_DEC_COMP);

		do {
			switch (menu = SelectMenu()) {
			case ADD: // 노드의 삽입
				data = new Data();
				data.scanData("삽입 ", Data.NO | Data.NAME);
				tree.add(data.keyCode(), data);
				break;

			case REMOVE: // 노드의 삭제
				temp.scanData("삭제", Data.NO);
				tree.remove(temp.keyCode());
				break;

			case SEARCH: // 노드의 검색
				temp.scanData("검색", Data.NO);
				ptr = tree.search(temp.keyCode());
				if (ptr != null)
					System.out.println("그 번호의 이름은 " + ptr + "입니다.");
				else
					System.out.println("해당 데이터가 없습니다.");
				break;

			case PRINT : // 노드의 출력
				tree.print();
				break;
			}
		} while (menu != Menu.TERMINATE);
	}
}