Tree

Tree

• 비선형 구조
• 원소들 간에 1:N 관계를 갖는 자료구조
• 원소들 간에 계층 관계를 갖는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조

• 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.
  • 노드 중 최상위 노드를 root라고 한다.
• 나머지 노드들은 n(>=0)개의 분리 집합으로 T1 ... TN으로 분리될 수 있다.
  • 이들을 각각 하나의 트리가 되며, 재귀적 정의루트의 부트리(subTree)라 한다.

• 연결 리스트하나도 트리의 일종이다. (편형트리)
• 비선형 구조는 선형 구조가 될 수 있지만, 선형 구조는 비선형 구조가 될 수 없다.

---

용어 정리

노드 - 트리의 원소 ( A,B,C,D,E,F,G,H,I,J,K )
간선 - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
루트 노드 - 트리의 시작 노드

형제 노드 - 같은 부모 노드의 자식 노드들 ( B,C,D는 하나의 형제 )
조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 (k의 조상 : F,B,A )
서브 트리 - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
자손 노드 - 서브트리에 있는 하위 레벨의 노드들 ( B의 자손 노드 - E,F,K )
단말 노드 - 연결된 간선이 없는 노드 ( E,K,G,H,I,J )

• 차수
  • 노드의 차수 : 노드에 연결된 자식 노드의 수 ( B : 2 / C : 1 )
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 ( 트리 T : 3 )

• 높이
  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨 ( B : 1 / F : 2 )
  • 트리의 높이 : 트리에 있는 노드의 높이 중 가장 큰 값, 최대 레벨 ( 트리 T : 3 ).

---

---

이진 트리

• 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리

• 노드의 최대 개수는 2^i 개가 된다.
• 높이가 h인 이진 트리 : 최소 갯수 = h+1 / 최대 갯수 = 2^(h+1) - 1

---

---

이진 트리 종류

포화 이진 트리

• 모든 레벨의 노드가 포화 상태로 차 있는 이진트리
• 높이가 h인 이진 트리에서 노드 개수가 2^(h+1) - 1인 트리

완전 이진 트리

• 높이가 h이고 높이가 n 개일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리
• 높이가 낮은 쪽부터, 왼쪽에서 오른쪽으로 번호를 맞춘다.

• 만약 5번의 자식이 없는데, 6번에 자식이 있다면, 완전 이진 트리로 볼 수 없다.
• 또한 10번이 좌측이 아닌 우측 자식이라면 완전 이진 트리가 될 수 없다.
• 포화 이진 트리는 완전 이진 트리가 될 수 있지만, 완전 이진 트리가 반드시 포화 이진 트리가 되는 건 아니다.

편향 이진 트리

• 높이 h에 대한 최소 개수의 노드를 가지면서, 한쪽 방향의 자식 노드만을 가진 이진 트리
• 연결 리스트로 표현될 수 있는 노드들.

---

배열을 이용한 이진 트리의 표현

• 이진 트리의 노드는 루트를 1번으로, 왼쪽부터 오른쪽으로 번호를 차례대로 부여

• 만약 12번 노드가 들어온다면, 6번의 왼쪽으로 들어오게 된다.

• 노드 번호를 배열의 인덱스로 사용한다.

• 배열을 이용한 이진 트리의 표현
  • 노드 번호가 i인 노드의 부모 노드 번호 : i/2
  • 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 : 2 * i
  • 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 : 2 * i + 1
  • 레벨 n의 노드 번호 시작번호 : 2^n
    

• 최대 노드 개수는 2^(h+1) - 1 이지만, 배열의 0번을 사용하지 않으므로, 배열 사이즈는 2^(h+1)가 되어야 한다.

이와 같이 편향 노드를 사용하게 되는 경우, 메모리 용량을 과하게 차지한다.
트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경이 어려워 비효율적이다.

• 다만, 배열의 삽입, 삭제가 자주 일어나지 않고 완전 이진 트리의 경우 탐색이 효율적이다.

---

이러한 단점을 보완하기 위해 연결 리스트 를 이용한 트리를 표현할 수 있다. .

• 마지막 자식 노드는 표현할 주소가 없어 null이 된다.

---

---

이진 트리 - 순회

• 순회 : 중복되지 않게 전부 방문하는 것. 트리는 비선형 구조기이기 때문에, 선형 구조에서와 같이 선후 연결 관계를 알 수 없다.

• 순회 방법 = 부모 노드를 기준으로 생각하면 된다

  • 전위 순회 : 부모 노드 방문 후, 자식 노드를 좌, 우로 방문
  • 중위 순회 : 왼쪽 자식 노드, 부모 노드, 우측 부모 노드 ( L - V - R )
  • 후위 순회 : 자식 노드를 좌, 우 순서로 방문하고 부모 노드 ( L - R - V )

순회

public class Tree_전위순회 { 
	
	static char[] tree = { 0,'A','B','C','D','E','F','G', 0,0, 'H','I'};
	
	public static void main(String[] args) {
		System.out.println("전위 순회 : ");
		preorder(1);
		System.out.println();
		
		System.out.println("중위 순회 : ");
		inorder(1);
		System.out.println();
		
		System.out.println("후위 순회 : ");
		postorder(1);
		System.out.println();
	}

	// 매개변수로 트리의 루트 index 받기 
	
	// 전위 순회 
	// V -> L -> R	
	static public void preorder(int root) {
		if(root >= tree.length || tree[root] == 0) { // 0은 root를 뜻하므로 돌려준다. 
			return;
		}
		
		System.out.print(tree[root] + "->");
		preorder(root * 2);
		preorder(root * 2 + 1);
	}
	
	// 중위 순회 
	// L -> V -> R
	static public void inorder(int root) {
		if(root >= tree.length || tree[root] == 0) { // 0은 root를 뜻하므로 돌려준다. 
			return;
		}
		
		inorder(root * 2);
		System.out.print(tree[root] + "->");
		inorder(root * 2 + 1);
	}
	
	
	// 후위 순회 
	// L -> R -> V
	static public void postorder(int root) {
		if(root >= tree.length || tree[root] == 0) { // 0은 root를 뜻하므로 돌려준다. 
			return;
		}
		postorder(root * 2);
		postorder(root * 2 + 1);
		System.out.print(tree[root] + "->");
	}
	
}

---

수식 트리

• 수식을 표현하는 이진 트리
• 연산자는 루트 노드이거나 가지 노드
• 피연산자는 모두 잎 노드가 된다.

• 사칙연산만 고려한 경우, 모든 연산자에 필요한 피연산자는 2개이므로 완전 이진 트리가 된다.
• 순회의 순서에 따라서 표현식이 달라지게 된다.

public class Tree2_수식트리 {

	static char[] tree = {0, '+', '*', '-', '1', '2', '3', '4'};
	
	public static void main(String[] args) {
		inorder(1); // 1*2+3-4
		
	}
	
	// 중위 순회 
	static void inorder(int root) {
		// 기저조건
		// 1. 인덱스가 배열 범위를 벗어난 경우
		if(root >= tree.length && root > 0) return;
		// 2. 리프 노드인 경우 (항상 피연산자, 즉 숫자인 것인지 확인
		if( tree[root] >= '0' && tree[root] <= '9') {
			System.out.print(tree[root]);
			return;
		}
		
		inorder(root*2); // 좌측 잎 
		System.out.print(tree[root]); // 루트 방문
		inorder(root*2 + 1); // 우측 잎
	}

}