트리 - 이진트리 정의/ 성질/ 분류/ 표현법

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

이전글: 트리-개념/용어정리

이진트리 binary tree

모든 노드가 2개의 서브 트리를 가지고 있는 트리

 

※ 단, 서브트리가 공집합일 수 있음.

• 모든 노드의 차수 ≤  2
• 공집합도 이진트리
• 서브 트리간의 순서 존재: 왼쪽, 오른쪽

성질

• n 개의 노드를 가진 이진트리는 (n - 1)개의 간선을 가진다.
• 트리의 높이 = h → h ≤ 노드의 개수 ≤ 2^h - 1
• 노드의 개수 = n →  ⌈log(n+1)⌉ ≤ 트리의 높이 ≤n

* ⌈x⌉ : x 보다 작지 않은 최소의 정수(올림 연산) ex. ⌈2.4⌉ = 3

 

분류

1. 포화이진트리 full binary tree

트리의 각 레벨에 노드가 꽉 차있는 이진트리

높이 = k -> 이진트리의 노드 개수 = 2^k - 1

 

2. 완전이진트리 complete binary tree

높이가 k일 때,

레벨1부터 k-1까지는 노드가 모두 채워져 있고,

마지막 레벨 k에서 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진트리

단, 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있으면 안 됨.

 

포화이진트리 ⊃ 완전이진트리

노드에 번호 매기기

아래의 트리는 완전이진트리로 볼 수 있고,

트리의 각 노드에 번호는 아래와 같이 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있다.

이진트리의 표현법

1. 배열 표현법

앞서 살펴본 '노드에 번호 매기기'의 번호가 곧 배열에서의 인덱스가 된다.

단, 인덱스 0은 사용하지 않는다.

배열 표현법은 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다.

• 노드 i의 부모 인덱스 = i/2
• 노드 i의 왼쪽 자식 인덱스 = 2*i
• 노드 i의 오른쪽 자식 인덱스 = 2*i + 1

2. 포인터(링크) 표현법

트리에서의 노드가 구조체로 표현되고, 각 노드가 갖고 있는 포인터는 부모와 자식 노드를 가리킨다.

하나의 노드의 구조를 구조체로 표현하면 다음과 같다.

typedef struct TreeNode{ // 하나의 노드
	int data;
	struct TreeNode *left, *right;
} TreeNode;