[C언어로 쉽게 풀어쓴 자료구조] Chapter 8 - 트리

선형 자료 구조 (linear data structure) : 리스트, 스택, 큐, ...
계층적인 자료 구조 (hierarchical structure) : 트리 , ...

이진 트리의 표현 방법
1. 배열을 이용하는 방법 : 완전 이진 트리임을 가정하고, 노드번호에 따라서 배열에 할당, 이때 인덱스 0은 편의를 위해서 비움.
단점 : 완전 이진 트리가 아닐 경우 메모리 낭비가 심함.

2. 포인터를 이용하는 방법 (링크 표현법) :[ [left link][data][right link] ] 와 같은 형태. 각 링크 필드는 왼쪽/오른쪽 자식 필드와 연결

 

// 링크법으로 생성된 이진 트리 

// 링크법으로 생성된 이진트리
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right; // 자식노드를 가리킴
} TreeNode;

int main()
{
    TreeNode *n1, *n2, *n3;
    // 동적 메모리 할당
    n1 = (TreeNode *)malloc(sizeof(TreeNode));
    n2 = (TreeNode *)malloc(sizeof(TreeNode));
    n3 = (TreeNode *)malloc(sizeof(TreeNode));

    // n1의 데이터 입력 및 노드 연결
    n1->data = 10;
    n1->left = n2;
    n1->right = n3;

    // n2의 데이터 입력 및 노드 연결
    n2->data = 20;
    n2->left = NULL;
    n2->right = NULL;

    // n3의 데이터 입력 및 노드 연결
    n3->data = 30;
    n3->left = NULL;
    n3->right = NULL;

}


/* 트리 구조
      [n1]
     /  |
  [n2] [n3]
*/

 

 

이진 트리의 순회

이진 트리를 순회(traversal) 한다는 것 : 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 사용하는 것

 

선형 자료 구조 순회 방법 : 차례대로 순회 하는 한가지

 

이진 트리 순회 방법 (루트 노드 : V , 왼쪽 서브 트리 : L , 오른쪽 서브 트리 : R)

1. 전위 순회 방법 : VLR

2. 중위 순회 방법 : LVR

3. 후위 순회 방법 : LRV

 

 

// 이진트리의 3가지 순회방법 (순환 호출 이용)

(노드를 전역 변수로 선언(단점: 실행중 노드의 개수를 바꿀 수 없음))

/*
전위순회 : VLR
중위순회 : LVR
후위순회 : LRV
*/

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

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

// 루트노드부터 생성할 경우, 생성되지 않은 노드의 링크를 걸게 됨으로 오류가 발생
// 터미널 노드부터 역순으로 생성하여야 함
TreeNode n8 ={50, NULL, NULL};
TreeNode n9 ={33, NULL, NULL};
TreeNode n6 ={22, NULL, NULL};
TreeNode n7 ={10, NULL, NULL};
TreeNode n5 ={89, NULL, NULL};
TreeNode n4 ={1, &n8, &n9};
TreeNode n3 ={56, &n6, &n7};
TreeNode n2 ={44, &n4, &n5};
TreeNode n1 ={18, &n2, &n3};

TreeNode *root = &n1; // 루트 노드

//        18
//    44      56
//  1   89  22  10
//50 33




// 전위 순회
void preorder(TreeNode *root) {
    if (root != NULL) {
        printf("[%d]", root->data); // 루트 노드의 데이터 출력
        preorder(root->left); // 왼쪽 서브트리 방문
        preorder(root->right); // 오른쪽 서브트리 방문
    }
}

// 중위 순회
void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left); // 왼쪽 서브트리 방문
        printf("[%d]", root->data); // 루트 노드의 데이터 출력
        inorder(root->right); // 오른쪽 서브트리 방문
    }
}

// 후위 순회
void postorder(TreeNode *root) {
    if (root != NULL) {
        postorder(root->left); // 왼쪽 서브트리 방문
        postorder(root->right); // 오른쪽 서브트리 방문
        printf("[%d]", root->data); // 루트 노드의 데이터 출력
    }
}


int main(void)
{
	printf("전위 순회=");
	preorder(root);
	printf("\n");

	printf("중위 순회=");
	inorder(root);
	printf("\n");

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

/*출력값
전위 순회=[18][44][1][50][33][89][56][22][10]
중위 순회=[50][1][33][44][89][18][22][56][10]
후위 순회=[50][33][1][89][44][22][10][56][18]
*/

 

 

// 반복적 순회 이용

// 반복을 이용한 트리 순회
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

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

// 스택 설정
#define SIZE 100 // 크기
int top = -1; // 가장 위에 쌓인 요소 인덱스
TreeNode *stack[SIZE]; // 스택 요소 자료형

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=");
	inorder_iter(root);
	printf("\n");
	return 0;
}

/*출력값
inorder=[1] [4] [15] [16] [20] [25]
*/

 

 

// 레벨 순회(level order) : 루트 노드(level 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); // ptr에 반횐된 큐의 요소를 저장
		printf(" [%d] ", ptr->data); // 출력
		// if를 사용하여서 존재하는 자식노드를 모두 큐에 삽입
		if (ptr->left) // 기존 ptr의 왼쪽 자식 노드를 큐에 삽입
			enqueue(&q, ptr->left);
		if (ptr->right) // 기존 ptr의 오른쪽 자식노드를 큐에 삽입
			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;
}

/*출력값 
레벨 순회= [15]  [4]  [20]  [1]  [16]  [25]
*/

 

 

// 트리의 응용 : 수식 트리 처리

수식 트리 : 수식을 트리의 형태로 만든 것으로 피연산자는 단말 노드가 되며, 연산자는 비단말 코드로 나타낸다.

수식 트리를 전위 , 중위 , 후위 순회 방식으로 읽은 것을 각각 전위 , 중위 , 후위 표기 수식이라고 한다.

// 수식 트리 계산 프로그램
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
} TreeNode;
//		     +
//	     *		 +
//    1	   4   16  25
TreeNode n1 = { 1,  NULL, NULL };
TreeNode n2 = { 4,  NULL,  NULL };
TreeNode n3 = { '*',  &n1,  &n2 };
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4,  &n5 };
TreeNode n7 = { '+', &n3,  &n6 };
TreeNode *exp = &n7;

// 수식 계산 함수 (순환 호출)
int evaluate(TreeNode *root)
{
    // 루트 노드가 NULL이면, 그냥 종료
	if (root == NULL)
		return 0;
    // 해당 노드의 자식 노드가 없다면, 해당 노드의 데이터를 그대로 반환
	if (root->left == NULL && root->right == NULL)
		return root->data;

	else {
	    // 서브트리들에도 순환 호출을 사용하여, op1, op2에 피연산자를 저장
		int op1 = evaluate(root->left);
		int op2 = evaluate(root->right);
        // 피연산자 : op1, op2 / 연산자 : root->data
        // 계산식 생성
		printf("%d %c %d을 계산합니다.\n", op1, root->data, op2);

		// switch - case 문을 사용하여, 사칙연산 별로 설정.
		switch (root->data) {
		case '+':
			return op1 + op2;
		case '-':
			return op1 - op2;
		case '*':
			return op1 * op2;
		case '/':
			return op1 / op2;
		}
	}
	return 0;
}

int main(void)
{
    // 수식트리의 계산 순서에 맞게 계산식 출력
	printf("수식의 값은 %d입니다. \n", evaluate(exp));
	return 0;
}

/* 출력값
1 * 4을 계산합니다.
16 + 25을 계산합니다.
4 + 41을 계산합니다.
수식의 값은 45입니다.
*/

 

 

 

// 트리의 응용 : 디렉토리 용량 계산

// 디렉토리 용량 계산 프로그램
#include <stdio.h>
#include <stdlib.h>

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

// 디렉토리 용량 계산 함수
int calc_dir_size(TreeNode *root)
{
    // 하나의 디렉토리 안에 하위 디렉토리가 최대 두개일때로 제한
	int left_size, right_size;
	if (root == NULL) return 0;

	left_size = calc_dir_size(root->left);
	right_size = calc_dir_size(root->right);
	// 순환 방식으로 총 디렉토리에 할당된 크기를 반환
	return (root->data + left_size + right_size);
}

int main(void)
{
	TreeNode n4 = { 500, NULL, NULL };
	TreeNode n5 = { 200, NULL, NULL };
	TreeNode n3 = { 100, &n4, &n5 };
	TreeNode n2 = { 50, NULL, NULL };
	TreeNode n1 = { 0, &n2, &n3 };

	//        n1
	//   n2        n3
	//           n4  n5

	printf("디렉토리의 크기=%d\n", calc_dir_size(&n1));
}

/*출력값
디렉토리의 크기=850
*/

 

 

 

// 노드의 개수 , 단말 노드 개수 , 트리 높이를 구하는 함수

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

/*
// fatal error : algorithm : No surch file or directory 오류 발생
#include <algorithm> // max 사용하기 위해
using namespace std;
*/

// 별도로 max()함수를 선언
#define max(a, b) (((a) > (b)) ? (a) : (b))

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

// 노드의 개수를 구하는 함수
int get_node_count(TreeNode *node)
{
    // 초기값 설정
    int count = 0;

    // 터미널 노드를 만날때 까지 계속 더한다.
    if (node != NULL){
            // 순환 방식으로 더함
        count = 1 + get_node_count(node->left) +
        get_node_count(node->right);
    }
    return count; // 결과값 반환
}

// 단말 노드 (터미널 노드)의 개수를 구하는 함수
int get_leaf_count(TreeNode *node)
{
    int count = 0; // 초기값 설정

    if(node != NULL){
        // 자식 노드가 없는 노드 == 터미널 노드 를 발견하면, 1을 반환
        if (node->left == NULL && node->right == NULL)
            return 1;
        // 순환 방식으로 모든 노드 판별
        else
            count = get_leaf_count(node->left)  + get_leaf_count(node->right);
    }
    return count;
}

// 트리의 높이를 구하는 함수
int get_height(TreeNode *node)
{
    int height = 0;

    // 터미널 노드가 아닌 이상 모든 노드에 대해서 get_height()를 수행하고 max + 1을 heigth에 저장한다.
    if (node != NULL){
        height = 1 +max(get_height(node->left), get_height(node->right));
    }

    return height;
}

int main()
{
    TreeNode n8 = {8, NULL, NULL};
    TreeNode n7 = {7, NULL, NULL};
    TreeNode n6 = {6, NULL, NULL};
    TreeNode n5 = {5, NULL, NULL};
    TreeNode n4 = {4, &n8, NULL};
    TreeNode n3 = {3, &n6, &n7};
    TreeNode n2 = {2, &n4, &n5};
    TreeNode n1 = {1, &n2, &n3};
    TreeNode *root = &n1;

    /*
            1
        2        3
      4   5    6   7
    8
    */
    printf("노드의 개수 = %d\n", get_node_count(root));
    printf("트리의 높이 = %d\n", get_height(root));
    printf("트리의 터미널 노드 개수 = %d\n", get_leaf_count(root));

}

/* 출력값
노드의 개수 = 8
트리의 높이 = 4
트리의 터미널 노드 개수 = 4
*/

 

 

 

// 스레드 이진 트리 순회 프로그램

// 스레드 이진 트리
#include <stdio.h>
#define TRUE 1
#define FALSE 0

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
	int is_thread;	// 스레드이면 TRUE
} TreeNode;


//		     G
//	     C		  F
//    A	   B   D     E
TreeNode n1 = { 'A',  NULL, NULL, 1 };
TreeNode n2 = { 'B',  NULL,  NULL, 1 };
TreeNode n3 = { 'C',  &n1,  &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1 };
TreeNode n5 = { 'E', NULL, NULL, 0 };
TreeNode n6 = { 'F', &n4,  &n5, 0 };
TreeNode n7 = { 'G', &n3,  &n6, 0 };
TreeNode * exp = &n7;

TreeNode * find_successor(TreeNode * p)
{
	// q는 p의 오른쪽 포인터
	TreeNode * q = p->right;
	// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
	if (q == NULL || p->is_thread == TRUE)
		return q;

	// 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
	while (q->left != NULL) q = q->left; // 왼쪽 자식 노드가 NULL일때까지 탐색
	return q;
}

void thread_inorder(TreeNode * t)
{
	TreeNode * q;

	q = t;
	while (q->left) q = q->left;// 가장 왼쪽 노드로 간다.
	do {
		printf("%c -> ", q->data);// 데이터 출력
		q = find_successor(q); // 후속자 함수 호출
	} while (q);			// NULL이 아니면
}
int main(void)
{
	// 스레드 설정 
	n1.right = &n3;
	n2.right = &n7;
	n4.right = &n6;
	// 중위 순회
	thread_inorder(exp);
	printf("\n");
	return 0;
}

/*출력값
A -> C -> B -> G -> D -> F -> E ->
*/

 

 

 

// 이진 탐색 트리

 

이진 탐색 트리의 정의

1. 모든 원소의 키는 유일한 키를 가진다.

2. 왼쪽 서브 트리 키들은 루트 키보다 작다.

3. 오른쪽 서브 트리의 키들은 루트의 키보다 크다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

// 이진 탐색 트리
#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct TreeNode {
	element key;
	struct TreeNode *left, *right;
} TreeNode;

// 순환적인 탐색 함수
TreeNode * search(TreeNode * node, int key)
{
	if (node == NULL) return NULL;
	// 1. 원하는 값을 찾았을 경우 : 해당 노드를 반환
	if (key == node->key) return node;
	// 2. 원하는 값보다 더 작은 값을 만났을 경우 : 해당 노드의 왼쪽 자식 노드로 이동
	else if (key < node->key)
		return search(node->left, key);
    // 3. 원하는 값보다 더 큰 값을 만났을 경우 : 해당 노드의 오른쪽 자식 노드로 이동
	else
		return search(node->right, key);
}

// 반복적인 탐색 함수
TreeNode * search_repet(TreeNode * node, int key)
{
    while (node != NULL) {
        if (key == node->key) return node;
        else if (key < node->key)
            node = node->left;
        else
            node = node->right;
    }
    return NULL;
}

// 동적 메모리를 할당하여 새로운 노드를 생성하여 반환하는 함수
TreeNode * new_node(int item)
{
	TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}

// 이진 탐색 트리 삽입 함수 (순환)
TreeNode * insert_node(TreeNode * node, int key)
{
	// 1. 트리가 공백(비어있는 상태)이면 새로운 노드를 반환
	// 2. 순환적으로 트리를 탐색하다, NULL이 발견되면 그 자리에 노드 생성
	if (node == NULL) return new_node(key);

	// 그렇지 않으면 순환적으로 트리를 내려간다.
	if (key < node->key)
		node->left = insert_node(node->left, key);
	else if (key > node->key)
		node->right = insert_node(node->right, key);

	// 변경된 루트 포인터를 반환한다.
	return node;
}

// 주어진 이진 탐색 트리에서 최소키값을 가지는 노드를 찾는 함수
TreeNode * min_value_node(TreeNode * node)
{
	TreeNode * current = node;

	// 맨 왼쪽 단말 노드를 찾으러 내려감
	while (current->left != NULL)
		current = current->left;

	return current;
}

// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고
// 새로운 루트 노드를 반환한다.
TreeNode * delete_node(TreeNode * root, int key)
{
	if (root == NULL) return root;

	// 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
	if (key < root->key)
		root->left = delete_node(root->left, key);
	// 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
	else if (key > root->key)
		root->right = delete_node(root->right, key);
	// 키가 루트와 같으면 이 노드를 삭제하면 됨
	else {
		// 첫 번째 경우 : 삭제하려는 노드가 터미널 노드일 경우
		// 두 번째 경우 : 삭제하려는 노드가 하나의 서브트리를 가지고 있는 경우
		if (root->left == NULL) {
			TreeNode * temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL) {
			TreeNode * temp = root->left;
			free(root);
			return temp;
		}
		// 세 번째 경우 : 삭제하려는 노드가 두개의 서브트리를 가지고 있는 경우
		TreeNode * temp = min_value_node(root->right);

		// 중외 순회시 후계 노드를 복사한다.
		root->key = temp->key;
		// 중외 순회시 후계 노드를 삭제한다.
		root->right = delete_node(root->right, temp->key);
	}
	return root;
}

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

int main(void)
{
	TreeNode * root = NULL;
	TreeNode * tmp = NULL;

	root = insert_node(root, 30);
	root = insert_node(root, 20);
	root = insert_node(root, 10);
	root = insert_node(root, 40);
	root = insert_node(root, 50);
	root = insert_node(root, 60);

	printf("이진 탐색 트리 중위 순회 결과 \n");
	inorder(root);
	printf("\n\n");
	if (search(root, 30) != NULL)
		printf("이진 탐색 트리에서 30을 발견함 \n");
	else
		printf("이진 탐색 트리에서 30을 발견못함 \n");
	return 0;
}

/*출력값
이진 탐색 트리 중위 순회 결과
[10] [20] [30] [40] [50] [60]

이진 탐색 트리에서 30을 발견함
*/