이진 트리(Binary Tree)

이진 트리란?

트리 자료구조 중에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조.

자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 한다.

왼쪽 서브 노드의 값은 루트의 값보다 작고, 오른쪽 서브 노드의 값은 루트보다 큰 값을 가지도록 구성한다.

 

용도

주로 빠른 검색이 필요한 곳에서 사용. 그래서 이진 검색 트리라고도 한다.

프로그램 로직을 구성하면서 사용자가 입력한 정보를 관리한다. (주로 수식 표현)

 

모양에 따른 분류

포화 이진 트리(Full Binary Tree) : 레벨의 노드가 꽉 차 있는 트리

완전 이진 트리(Complete Binary Tree) : 마지막 레벨 전까지는 노드가 꽉 차있고, 마지막 레벨의 왼쪽에서 오른쪽으로 노드가 채워져 있는 트리. (마지막 레벨이 다 채워지지 않아도 됨)

편향 이진 트리(Skewed Binary Tree) : 왼쪽 혹은 오른쪽 서브 트리만을 가지는 트리

 

구현 방법

순차 자료구조(리스트), 연결 자료구조(연결 리스트) 둘 다 가능.

 

자바로 구현하기

public class TreeNode {

private int itsKey;
private Object itsValue;
private TreeNode nodes[]=new TreeNode[2];

//생성자
public TreeNode(int key, Object value) { 
	itsKey=key; 
	itsValue=value; 
	System.out.println("start TreMapNode");
}

//key로 value를 찾는 메서드
public Object find(int key) {
	if(key == itsKey ) { 
		return itsValue; 
	} 
	return findSub(selectSubNode(key), key);
}

//왼쪽 자식 노드를 선택할지, 오른쪽 자식 노드를 선택할지
//매개변수 key가 현재 노드의 키보다 작으면 0, 크면 1을 반환
private int selectSubNode(int key) {
	return (key <itsKey) ? 0 : 1;
}

//서브 노드의 값을 검색하는 메서드
private Object findSub(int node, int key) { 
	return nodes[node]==null ? null:nodes[node].find(key);
}

//값을 추가하는 메서드
public void add(int key, Object value) { 
	if(key == itsKey) 
		itsValue=value; 
	else
		SubNode(selectSubNode(key), key, value);
}

//서브 노드에 값을 추가하는 메서드
private void SubNode(int node, int key, Object value) { 
	if(nodes[node]==null) 
		nodes[node]=new TreeNode(key, value); 
	else                                                                                                                                                                                                                                                                                                  
		nodes[node].add(key, value);
	}
}

public class Tree { 

	//TreeNode 객체 생성 후 초기화
	TreeNode topNode=null;
	
	public void add(int key,Object value) {
	if(topNode==null) 
		topNode=new TreeNode(key, value); 
	else 
		topNode.add(key, value); 
	}
	
	public Object get(int key) { 
		return topNode==null ? null:topNode.find(key); 
	}
}