이진 트리의 표현

포화 이진 트리(perfect binary tree)

- 전체의 노드의 개수 구하는 공식:

2^k -1 => 여기서 k은 트리의 높이를 대입하면 된다. 

- 노드에 번호를 부여하는 방법은 왼쪽에서 오른쪽으로 번호를 붙이면 된다.

포화 이진 트리

완전 이진 트리(complete binary tree)

- 완전 이진 트리는 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽에서 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다.

완전 이진 트리

* 완전 이진 트리가 아님(왼쪽이 없음)

트리 표현 - 괄호 표현법

- 트리를 텍스트 상으로 표현하는 방법으로 괄호를 사용한 방법이다.

*완전 이진 트리가 아님이라는 트리를 참고해서 괄호로 표현해 보자 (1(2(4)(5) 3()(6)))

 

트리 표현 - 배열 표현법

- 노드 i의 부모 노드 인덱스 = i/2

- 노드 i의 왼쪽 자식 노드 인덱스 = 2i

- 노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

 

배열 표현

트리 표현 - 링크 표현법

완전 이진트리 - 링크표현법