6-3. 이진 트리의 구현 방법

이진 트리를 구현하는 방법은 크게 두 가지가 있다.

배열을 이용하는 방법과 연결 리스트를 이용하는 방법이다.

배열을 이용해 이진 트리를 구현하는 방법

이진 트리의 높이가 h이면 먼저 2^h-1개의 공간을 배열로 할당한다.

이진 트리의 '위에서 아래로', '왼쪽에서 오른쪽으로'의 순서대로 번호를 할당한다.

이 번호가 배열의 인덱스로 사용된다.

노드간의 부모/자식 관계를 쉽게 파악하기 위해 노드의 번호는 1부터 사용한다.

노드의 번호를 1부터 사용하면 다음과 같은 장점이 있다.

임의의 노드 인덱스 값만 알고 있다면 그 노드의 부모/자식 노드를 쉽게 알 수가 있다.

하지만, 배열을 사용했으므로 메모리 낭비와 한정된 크기라는 단점도 함께 따라온다.

연결 리스트를 이용하면 배열을 이용했을 때의 단점이 극복되지만, 구현이 상대적으로 복잡해진다.

연결 리스트로 이진 트리를 구현하면 삽입/삭제 연산 시에 메모리 동적 할당/해제의 과정을 거치기 때문에 트리의 노드들은 메모리 여기저기에 흩어져 있고, 각 노드는 데이터 필드와 링크 필드를 갖는다.

링크 필드는 각각 왼쪽 자식 노드, 오른쪽 자식 노드를 가리키게 된다.

저작자표시 (새창열림)