[자료구조] 트리_상 : C언어

728x90

1. 트리의 개념

리스트, 스택, 큐 등은 선형 자료 구조(linear data structure)

선형으로 나열되어 있는 구조

트리는 계층적인 구조를 나타내는 자료구조

트리는 부모 - 자식 관계의 노드들로 이루어진다
가족의 가계도나 회사의 조직도 등

트리에서 사용되는 용어

노드(node): 트리의 구성요소
루트(root): 부모가 없는 노드(A)
서브 트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리
비말단노드: 적어도 하나의 자식을 가지는 노드(A, B, C, D)
단말 노드(terminal node): 자식이 없는 노드(E, F, G, H, I, J)

자식, 부모, 형제, 조상, 자손 노드: 인간과 동일
레벨(level): 트리의 각층의 번호
높이(height): 트리의 최대 레벨(3)
차수(degree): 노드가 가지고 있는 자식 노드의 개수 (A의 차수는 3), (B의 차수는 3), (C의 차수는 1), (D의 차수는 2)

2. 트리의 종류

일반 트리는 차수의 개수가 규칙적이지 않음
이진트리는 모든 노드의 차수가 최대 2인 트리

3. 이진 트리의 성질

이진트리(binary tree):

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

서브 트리는 공집합일 수 있음

이진트리의 노드에는 최대 2개까지의 자식 노드가 존재

모든 노드의 차수는 2 이하

구현하기 용이함

이진 트리에는 서브 트리 간의 순서가 존재

: 왼쪽 - 가운데 - 오른쪽

이진트리는 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의
이진트리의 서브 트리들은 모두 이진 트리

* 이진 트리의 성질

1. 노드의 개수가 n개이면 간선의 개수는 n-1

ex) 노드의 개수: 7, 간선의 개수: 6

2. 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가진다.

3. n개의 노드를 가지는 이진 트리의 높이

최대 n
최소 [ log₂(n+1) ]

4. 이진 트리의 분류

포화 이진트리(full binary tree)
완전 이진트리(complete binary tree)
기타 이진 트리

완전 이진 트리 : 마지막 노드가 단말 노드이거나 왼쪽 서브 트리부터 가지는 노드

5. 포화 이진 트리

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

*포화 이진트리의 노드 개수 연산

전체 노드 개수 : 2k - 1( 높이가 k인 경우)

포화 이진트리에서는 각 노드에 번호를 붙일 수 있음

항상 일정하게 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙임

6. 완전 이진 트리

: 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

중간에 빈 곳이 있으면 안 됨
포화 이진트리와 노드 번호가 일치

7. 이진트리의 표현

7-1) 배열 표현법

: 모든 이진트리를 포화 이진트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

*배열 표현법에서 부모와 자식 인덱스 관계

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

4. 이진트리의 순회

이진트리는 계층적인 관계의 데이터를 저장하기 위한 자료구조
순회(traversal)란 트리의 노드들을 체계적으로 방문하는 것
이진트리의 순회는 이진트리의 모든 노드를 방문하여 노드에 저장된 데이터를 처리하는 것

1. 3가지의 기본적인 순회 방법

*항상 L 쪽이 R 쪽보다 먼저, 순회 방법의 이름은 이름(V) 중심으로

1-1 전위 순회(preorder traversal) : VLR

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

1) 루트 노드를 방문

2) 왼쪽 서브 트리를 방문

3) 오른쪽 서브트리를 방문

*전위 순회는 특성상 오른쪽 끝 말단 노드가 마지막에 방문된다.

1-2 중위 순회(inorder traversal) : LVR

왼쪽 자손, 루트, 오른쪽 자손 순으로 방문

1) 왼쪽 서브 트리를 방문

2) 루트 노드를 방문

3) 오른쪽 서브트리를 방문

*중위 순회는 특성상 오른쪽 끝의 단말 노드를 가장 마지막에 방문하게 된다.

1-3 후위 순회(postorder traversal) : LRV

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

1) 왼쪽 서브 트리를 방문

2) 오른쪽 서브트리를 방문

3) 루트 노드를 방문

*후위 순회는 특성상 맨 처음 루트 노드를 가장 마지막에 방문하게 된다.

순회 프로그램 코드

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

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

//		  15
//	   4     20
// 	1	   16  25

TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;

// 중위 순회
inorder(TreeNode* root) {
	if (root) {
		inorder(root->left);		// 왼쪽서브트리 순회
		printf("%d ", root->data); 	// 노드 방문
		inorder(root->right);		// 오른쪽서브트리 순회
	}
}

// 전위 순회
preorder(TreeNode* root) {
	if (root) {
		printf("%d ", root->data); 	// 노드 방문
		preorder(root->left);		// 왼쪽서브트리 순회
		preorder(root->right);		// 오른쪽서브트리 순회
	}
}

// 후위 순회
postorder(TreeNode* root) {
	if (root) {
		postorder(root->left);		// 왼쪽 서브 트리 순회
		postorder(root->right);		// 오른쪽 서브 트리 순회
		printf("%d ", root->data); 	// 노드 방문
	}
}

//
int main(void)
{
	printf("중위 순회=");
	inorder(root);
	printf("\n");

	printf("전위 순회=");
	preorder(root);
	printf("\n");

	printf("후위 순회=");
	postorder(root);
	printf("\n");
	return 0;
}

실행 결과

중위 순회=1 4 15 16 20 25
전위 순회=15 4 1 20 16 25
후위 순회=1 4 16 25 20 15

5. 반복적 순회

똑같은 로직을 재귀가 아닌 반복문을 이용하여 구현할 수 있다.

재귀와 반복은 각각의 장점을 이용해서 바꿀 수 있다.

반복을 이용한 중위 순회

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SIZE 100

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

TreeNode* stack[SIZE];
int top = -1;

void push(TreeNode* p)
{
	if (top < SIZE - 1)
		stack[++top] = p;
}

TreeNode* pop()
{
	TreeNode* p = NULL;
	if (top >= 0)
		p = stack[top--];
	return p;
}

void inorder_iter(TreeNode* root)
{
	while (1) {
		for (; root; root = root->left) {
			push(root);
		}
		root = pop();
		if (!root) {
			break;
		}
		printf("[%d] ", root->data);
		root = root->right;
	}
}

//		       15
//	       4		 20
//     1	     16     25
TreeNode n1 = { 1,  NULL, NULL };
TreeNode n2 = { 4,  &n1,  NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3,  &n4 };
TreeNode n6 = { 15, &n2,  &n5 };
TreeNode* root = &n6;

int main(void)
{
	printf("중위 순회=");
	inorder_iter(root);
	printf("\n");
	return 0;
}

실행결과

중위 순회=[1] [4] [15] [16] [20] [25]

6. 레벨 순회

: 각 노드를 레벨 순으로 검사하는 순회 방법

루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨이 증가됨
동일한 레벨인 경우에는 왼쪽에서 오른쪽으로 방문
다른 순회와 다르게 스택이 아닌 큐를 이용하는 순회

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

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

// ================ 원형큐 코드 시작 =================
#define MAX_QUEUE_SIZE 100
typedef TreeNode* element;

// 큐 타입
typedef struct { 
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 공백 상태 검출 함수
void init_queue(QueueType* q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType* q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType* q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 삽입 함수
void enqueue(QueueType* q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType* q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

void level_order(TreeNode* ptr)
{
	QueueType q;

	init_queue(&q);	 // 큐 초기화

	if (ptr == NULL) {
		return;
	}

	enqueue(&q, ptr);

	while (!is_empty(&q)) {

		ptr = dequeue(&q);

		printf(" [%d] ", ptr->data);

		if (ptr->left) {
			enqueue(&q, ptr->left);
		}

		if (ptr->right) {
			enqueue(&q, ptr->right);
		}
	}
}

//		         15
//	        4		   20
//     1	        16     25
TreeNode n1 = { 1,  NULL, NULL };
TreeNode n2 = { 4,  &n1,  NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3,  &n4 };
TreeNode n6 = { 15, &n2,  &n5 };
TreeNode* root = &n6;

int main(void)
{
	printf("레벨 순회=");
	level_order(root);
	printf("\n");
	return 0;
}