[자료구조/java] 이진 트리 (Binary Tree) - 순차 자료구조 방식, 연결 자료구조 방식

* 이진 트리 (Binary Tree) 구현 - 순차 자료구조 방식

- 이진트리를 배열로 표현하는 방법은 높이가 h인 포화 이진 트리의 노드번호를 배열의 인덱스로 사용하여 1차원 배열로 표현

- 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비워두고 항상 인덱스 1번에 루트를 저장

이진 트리를 표현한 1차원 배열에서의 인덱스 관계를 나타낸 표이다.

 

 

* 이진 트리 (Binary Tree) 구현 - 연결 자료구조 방식

- 배열을 이용한 순차 자료구조 방식은 쉽게 만들 수 있고, 인덱스 규칙에 따라 노드를 찾는 것이 쉽다. 

- 하지만 메모리 사용에 있어서 완전 이진 트리의 경우 최적의 공간 사용이 되지만, 편향 이진 트리의 경우 많은 공간이 낭비된다.

- 메모리 문제와 삽입, 삭제 연산의 비효율에 의해 연결 자료구조 방식을 많이 사용한다.

완전 이진 트리를 아래와 같은 방식으로 표현할 수 있다.