트리의 개념과 자바로 구현해보기

1. 트리란?

• 노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)
• 계층적 구조를 나타낼 때 사용
  • 폴더 구조 (디렉토리, 서브 디렉토리)
  • 조직도, 가계도 등

2. 구조

- 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위

- 엣지(Edge) : 노드 간의 연결선(=link, branch)

- 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드

- 잎새 노드(Leaf) : 자식이 없는 노드(=단말)

- 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드

- 부모(Parent) : 연결된 두 노드 중 상위의 노드

- 자식(Child) : 연결된 두 노드 중 하위의 노드

- 형제(Sibling) : 같은 부모를 가지는 노드

- 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수

- 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합

- 높이(Height) : 트리에서 가장 큰 레벨 값

- 크기(Size) : 자신을 포함한 자식 노드의 개수

- 차수(Degree) : 각 노드의 지닌 가지의 수

   ex) B 노드의 차수 : D, E

- 트리의 차수 : 트리의 최대 차수

 

 

 

 

3. 특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일
• 노드가 N개인 트리의 Edge의 수는 N-1개
• Acyclic (Cycle이 존재하지 않음)
• 모든 노드는 서로 연결되어 있음
• 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨

4. 이진 트리 (Binary Tree)

• 각 노드는 최대 2개의 자식을 가질 수 있음
• 자식 노드는 좌우를 구분함
  • 왼쪽 자식 : 부모 노드의 왼쪽 아래
  • 오른쪽 자식 : 부모 노드의 오른쪽 아래

5. 이진 트리 종류

• 포화 이진 트리 (Perfect Binary Tree)
  • 모든 레벨에서 노드들이 꽉 채워져 있는 트리

• 완전 이진 트리 (Complete Binary Tree)
  • 마지막 레벨을 제외하고 노드들이 모드 채워져 있는 트리

• 정 이진 트리(Full Binary Tree)
  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

• 편향 트리 (Skewed Binary Tree)
  • 사향 트리라고도 함
  • 한 쪽으로 기울어진 트리

• 균형 이진 트리 (Balanced Binary Tree)
  • 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
  • 균형 이진 트리 경우 탐색 속도가 빠르다

6. 이진 트리 특징

- 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N-1

 

 

 

 

7. 이진 트리의 순회(Traversal)

• 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
• 순회 종류 4가지
  • 전위순회 (DFS)
    • Preorder Traversal
    • 방문 순서 : 현재 노드 → 왼쪽 노드 → 오른쪽 노드
                                       
  • 중위순회 (DFS)
    • InOrder Traversal
    • 방문순서 : 왼쪽 노드 → 현재 노드 → 오른쪽 노드

• 후위순회 (DFS)
  • PostOrder Traversal
  • 방문 순서 : 왼쪽 노드 → 오른쪽 노드 → 현재 노드

• 레벨 노드 (BFS)
  • LevelOrder Traversal
  • 방문 순서 : 위쪽 레벨 부터 왼쪽 노드 -> 오른쪽 노드

8. 이진 트리 구현

• 배열
  • 레벨 순회 순으로   배열에 구성
  • 레벨 순으로 차례대로 배열에 입력

- 배열은 0 부터 시작이므로

   왼쪽 노드 : X 2 + 1

   오른쪽 노드 : X 2 + 2

- 배열 0번 째를 비우고 1부터 시작

 

 

 

 

 

• 연결 리스트
  • 값과 간선을 관리하기 위한 노드로 연결리스트 구성

---

class BinaryTree {
	char[] arr;

	public BinaryTree(char[] arr) {
		this.arr = arr.clone();
	}

	public void preOrder(int idx) {
		System.out.print(this.arr[idx] + " ");

		int left = 2 * idx + 1;
		int right = 2 * idx + 2;
		if (left < this.arr.length) {
			this.preOrder(left);
		}

		if (right < this.arr.length) {
			this.preOrder(right);
		}
	}

	public void inOrder(int idx) {
		int left = 2 * idx + 1;
		int right = 2 * idx + 2;

		if (left < this.arr.length) {
			this.inOrder(left);
		}

		System.out.print(this.arr[idx] + " ");

		if (right < this.arr.length) {
			this.inOrder(right);
		}
	}

	public void postOrder(int idx) {
		int left = 2 * idx + 1;
		int right = 2 * idx + 2;

		if (left < this.arr.length) {
			this.postOrder(left);
		}

		if (right < this.arr.length) {
			this.postOrder(right);
		}

		System.out.print(this.arr[idx] + " ");
	}

	public void levelOrder(int idx) {
		for (int i = 0; i < this.arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

}

public class Practice1 {

	public static void main(String[] args) {
		char[] arr = new char[10];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (char) ('A' + i);
		}

		BinaryTree bt = new BinaryTree(arr);

		System.out.println("== PreOrder == ");
		bt.preOrder(0);
		System.out.println();

		System.out.println("== InOrder == ");
		bt.inOrder(0);
		System.out.println();

		System.out.println("== PostOrder == ");
		bt.postOrder(0);
		System.out.println();

		System.out.println("== LevelOrder == ");
		bt.levelOrder(0);
		System.out.println();

	}

}