[Algorithm] 이진 트리

이진 트리

• 이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리입니다.

이진 트리의 종류

• 포화 이진 트리: 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리
• 완전 이진 트리: 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리
  • 포화 이진트리와 노드 번호가 일치함

• 편향 이진트리: 노드들이 한쪽으로 편향되어 생성된 이진 트리
  

이진 트리의 표현

• 트리는 배열과 포인터로 표현하는 2가지 방법이 있습니다.

배열 표현법

• 가장 직관적이고 편리하게 사용할 수 있는 방법으로 다음과 같은 특징을 가집니다.

노드	인덱스	조건
루트 노드	index = 1
부모 노드	index = index/2	현재 노드가 루트 노드가 아님
왼쪽 자식 노드	index = index*2	index*2 <= N
오른쪽 자식 노드	index = index*2 +1	index*2 +1 <= N

포인터 표현법

• 노드는 구조체, 링크는 포인터로 구현하는 방법입니다

typedef struct TreeNode
{
	int data;
    TreeNode* left, *right;
};

이진 트리의 순회

• 트리의 노드들을 체계적으로 방문하는 것으로 3가지의 순회 방법이 있습니다.

전위 순회

• 자손 노드보다 루트 노드를 먼저 방문

중위 순회

• 왼쪽 자손 노드 -> 루트 노드 -> 오른쪽 자손 노드 순서로 방문

후위 순회

• 루트 노드 보다 자손 노드를 먼저 방문