[알고리즘] 트리1 - 트리와 이진트리

목차

01 트리의 이해

트리(Tree)는 자료들이 리스트, 스택 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이며, 계층 자료구조이다.

트리의 구조

트리의 구성 요소

노드 Node: 트리를 구성하는 원소(자료)를 노드(Node)라고 한다.

간선 Edge: 노드를 연결하는 선.

루트 Root 노드, Level 0: 트리의 시작 노드.

형제 Sibling 노드: 같은 부모 노드를 가진 자식 노드들.

조상 Ancestor 노드: 루트 노드까지 이르는 경로에 있는 노드는 모두 그 노드의 조상.

(노드 K의 조상은 F, B, A)

 

서브 트리 Subtree: 자식 노드들은 독립하여 새로운 트리 구성이 가능 따라서 각 노드는 자식 노드 수만큼 서브트리를 가짐.

(노드 B의 자손 노드는 서브트리 E의 노드와 서브트리 F의 노드이므로 E, F, K, L이 된다.)

차수 Degree: 한 노드가 가지는 서브 트리의 수, 즉 자식 노드의 차수 Degree. 

(노드 A의 차수는 3, 노드 B의 차수는 2, 노드 C의 차수는 1, 노드 D의 차수는 3이다.)

단만 Terminal 노드: 차수가 0인 노드, 즉 자식 노드가 없는 노드(리프 노더라고도 함.)

(A의 단말 노드는 E, K, L, G, H, I, J이다.)

내부 Internal 노드 : 차수가 1 이상인 노드.

 

높이 : 한 노드의 높이는 루트에서 그 노드에 이르는 경로에 있는 간선의 수이고, 노드의 높이 중에서 가장 큰 값, 즉 최대 레벨이 트리의 높이가 된다. (노드 A의 전체 높이는 3, B의 높이는 1...)

포레스트(Forest/ 부분집합): 나무가 모이면 숲이 되는 것처럼 여러 개의 트리 집합을 포레스트라 한다. n개의 자식노드, 즉 n개의 서브트리를 가진 루트 노트를 제거하면 n개로 분리된 트리가 숲을 이룬다.

루트 노드 A를 제거하여 만든 포리스트

---

02 이진트리

이진트리란

트리의 구조를 일정하게 제한하여 정의하면 트리의 연산이 단순해지고 명확해진다.

트리의 모든 노드의 차수를 2개 이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의한 것이 이진트리 Binary Tree이다.

이진 트리의 기본 구조

하나의 노드는 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child) 두 개만 가질 수 있고 위의 그림처럼 공백도 하나의 자식으로 취급한다.

 그러면 일반 트리를 이진트리로 변환하는 과정은?

일반 트리의 이진트리로의 변환 과정

1. ① 일반 트리가 있다면 루트부터 하위 레벨로 내려가면서 각 노드의 ②첫 번째 자식 노드로의 간선(왼쪽 자식)만 남겨두고 나머지 자식 노드의 간선은 제거한다.
2. ③형제 (Sibling) 노드끼리 간선을 연결한다.
3. 간선 정리 작업이 다 끝난 트리를 ④ 시계 방향으로 45도 회전하면 이진트리가 된다.

이진트리의 특징

• 노드가 n개인 이진트리는 간선이 항상 n - 1 개다.
• 높이가 h인 이진트리가 가질 수 있는 노드 개수는 최소 (h + 1) 개이며, 최대 ( 2^{h+1}-1)이다.

이진트리의 종류

• 포화 이진트리(Full Binary Tree) : 모든 레벨에 노드가 꽉 차 높이를 늘리지 않는 한 노드를 추가할 수 없는 포화 상태의 이진트리.

높이가 3인 포화 이진트리

• 완전 이진트리(Complete Binary Tree) : 높이가 h이고, 노드 수가 n개일 때 (단 n < 2^{h+1}-1)) 포화 이즌트리에서의 노드 1번부터 n번까지의 위치가 일치하는 이진트리이다. (순서대로 채워져야지만 완전)

높이가 3인 완전 이진트리

• 편향 이진트리(Skewed Binary Tree) :이진트리 중에서 최소 노드, 즉 높이가 h일 때 h+1개의 노드를 가지면서 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브 트리를 가지고 있는 트리.

왼쪽 편향 이진트리, 오른쪽 편향 이진트리

이진트리의 구현

1. 순차 자료구조를 이용한 이진 트리의 구현.

이진트리를 1차원 배열로 표현할 때는 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용.

단, 노드 1번부터 시작하기에 1차원 배열에서 인덱스 계산을 쉽게 하기 위해 밑에 그림처럼 배열 사용.

완전 이진 트리의 1차원 배열 표현

 

노드	인덱스	성립조건
노드 i의 부모 노드	i/2	i > 1
노드 i의 왼쪽 자식 노드	2 * 1	(2 * i) <= n
노드 i의 오른쪽 자식 노드	(2 * i) + 1	(2 * i + 1) <= n
루트노드	1	n >0

 

2 연결 자료구조를 이용한 이진트리의 구현

포인터가 포함된 노드(구조체) 기반의 연결 자료구조 구현 방식을 이용하여 이진트리를 구현하는 방법은...

데이터를 저장하는 데이터 필드와 왼쪽 자식 노드를 연결하는 왼쪽 링크 필드, 오른쪽 자식 노드를 연결하는 오른쪽 링크 필드로 구성이 되며

자식 노드가 없으면 링크 필드에 NULL을 저장하여 NULL 포인터로 설정하는 것이다.

이진 트리 노드 구조

typedef struct treeNode{
    struct treeNode* left;
    char data;
    struct treeNode* right;
}treeNode;