이진 트리를 구현하는 방법은 크게 두 가지가 있다.
배열을 이용하는 방법과 연결 리스트를 이용하는 방법이다.
배열을 이용해 이진 트리를 구현하는 방법
이진 트리의 높이가 h이면 먼저 2h-1개의 공간을 배열로 할당한다.
이진 트리의 '위에서 아래로', '왼쪽에서 오른쪽으로'의 순서대로 번호를 할당한다.
이 번호가 배열의 인덱스로 사용된다.
노드간의 부모/자식 관계를 쉽게 파악하기 위해 노드의 번호는 1부터 사용한다.
노드의 번호를 1부터 사용하면 다음과 같은 장점이 있다.
- 노드 i 의 부모 노드 인덱스 : i / 2
- 노드 i 의 왼쪽 자식 노드 인덱스 : 2 * i
- 노드 i 의 오른쪽 자식 노드 인덱스 : 2 * i + 1
임의의 노드 인덱스 값만 알고 있다면 그 노드의 부모/자식 노드를 쉽게 알 수가 있다.
하지만, 배열을 사용했으므로 메모리 낭비와 한정된 크기라는 단점도 함께 따라온다.
연결 리스트를 이용해 이진 트리를 구현하는 방법
연결 리스트를 이용하면 배열을 이용했을 때의 단점이 극복되지만, 구현이 상대적으로 복잡해진다.
연결 리스트로 이진 트리를 구현하면 삽입/삭제 연산 시에 메모리 동적 할당/해제의 과정을 거치기 때문에 트리의 노드들은 메모리 여기저기에 흩어져 있고, 각 노드는 데이터 필드와 링크 필드를 갖는다.
링크 필드는 각각 왼쪽 자식 노드, 오른쪽 자식 노드를 가리키게 된다.
'Computer Science > Data Structure' 카테고리의 다른 글
6-5. [C++] 이진 트리의 순회(전위/중위/후위/레벨 순회) 구현 (0) | 2023.07.24 |
---|---|
6-4. [C++] 연결 리스트로 구현한 이진 트리 (0) | 2023.07.24 |
6-2. 이진 트리란? (0) | 2023.07.24 |
6-1. 트리란? (0) | 2023.07.24 |
4-4. [C++] 연결 리스트로 구현한 큐 (0) | 2023.07.11 |