이진 트리는 재귀적인 특성을 지니고 있다. 이는 앞서 보인 이진 트리의 정의에서도 확인할 수 있었다. 이진 트리의 이러한 재귀적인 트것ㅇ 떄문에 이진트리와 관련된 일부 연산은 재귀호출의 형태를 띈다.
배열기반으로도 구현이 가능하지만 연결 리스트가 더 유연하기 때문에 연결 리스트 기반으로 구현할 것이다. 하지만 다음과 같은 특성을 갖는 완전 이진 트리라면 배열 기반의 구현도 고려해 볼만 하다.
“트리가 완성 된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다.”
위와 같이 0번 인덱스는 사용하지 않는 편이 구현에 편의를 가져다 주고, 실수를 줄여준다.
배열기반 트리는 별 의미가 없는건가요? 신경 쓰지 않아도 되나요?
그렇지 않다. 완전 이진 트리의 구조를 갖는 ‘힙(heap)’이라는 자료구조는 배열을 기반으로 구현한다. 힙이 요구하는 바를 만족시키기가 배열이 훨씬 용이하기 때문이다.