트리의 형태 중 하나인 이진트리를 세부적으로 확인해보자.

1. Specific

⭕️ 이진 트리는 루트를 가지는 트리 구조이다.
⭕️ 모든 노드는 두 개의 자식 노드를 가질 수 있다.
⭕️ 자식 노드를 정렬하면 왼쪽, 오른쪽 자식 노드를 구분할 수 있다.

2. kinds

🆕 루트 이진 트리

하나의 루트 노드를 가지면서 각 노드가 최대 두 개의 자식 노드를 갖는 구조

🆕 정 이진 트리

모든 노드가 0개 혹은 2개의 자식 노드를 갖는 구조

🆕 포화 이진 트리

모든 노드가 0개 혹은 2개의 자식노드를 가지며 모든 리프 노드가 똑같은 레벨을 갖는 구조

🆕 완전 이진 트리

왼쪽 자식 노드부터 채워지며 마지막 레벨을 제외하고는 모든 자식노드가 채워져있는 구조

3. 이진 트리 탐색

중위순회: 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순서로 순회
전위순회: 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 순회
후위순회: 왼쪽 자식 노드, 오른쪽 자식 노드, 부모 노드 순서로 조회
레벨순회: 부모 노드, 부모 노드로부터 깊이1인 노드들, 깊이 2인 노드들,..., 깊이가 n인 노드들 순서로 조회

4. 이진 트리 표현 방법

🔴 1차원 배열: 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법

장점: 노드의 위치에 쉽게 접근
단점: 특정 트리에서 공간의 낭비

출처

🔴 연결리스트 표현: 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법

장점: 기억 장소를 절약 / 노드의 삽입과 삭제 용이
단점: 접근성의 어려움