이진 트리 (Binary Tree) - 구현

이진 트리 (Binary Tree) - 구현

---

배열 구현

이진 트리를 배열로 구성할 시 연결 리스트에 비해 탐색이 빠르고 쉽습니다.

위와 같은 이진 트리를 배열로 구현한다고 했을 때,

루트 노드를 배열 인덱스 0으로 설정 후 완전 이진 트리를 채워나가는 방식으로 인덱스를 부여합니다. (=다시 말하면 이진 트리에 노드가 추가될 때 그 순서를 뜻하는 것과 같습니다.)

따로 구현은 하지 않았는데 어떻게 생각해보면 트리라고 이해하기는 힘들 것 같습니다 ㅠ;;

연결 리스트 구현

연결 리스트를 통한 구현이 훨씬 더 트리의 모양을 잘 이해할 수 있는?? 구조라고 생각됩니다.

왼쪽에서 뻗어나오는 파란 팔은 양방향 연결 리스트를 생각했을 때 왼쪽 팔, 주황색 팔은 오른쪽 팔을 뜻합니다.

그냥 봐도 모양이 트리와 똑같기 때문에 직관적으로 이해하기 쉬운데요, 트리가 채워지는 방식은 배열 구현처럼 완전 이진 트리를 향해 가는 형태로 채워갈 수도 있고, (예: 서브 트리 추가 함수 하나) 오른팔/왼팔 선택하여 추가할 수도 있습니다. (예: 오른팔 서브 이진 트리 추가 함수/왼팔 서브 이진 트리 추가 함수 = 총 두 개)

트리의 주소값은 루트 노드의 주소값입니다.

노드 하나도 트리이기에, 위 그림에서 모든 트리를 찾으면 아래와 같이 표현될 수 있습니다.