[자료구조] - 트리 /이진트리/순회/응용

트리

자료들이 계층적으로 나열 되어 있는 구조

트리 용어 --> 트리 용어

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

• 이진 트리의 모든 노드는 차수가 2개 이하이다. 즉 자식 노드의 개수가 2 이하이다(공집합도 포함). 반면 일반 트리는 자식 노드의 개수에 제한이 없다.
• 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수 도 있다.
• 서브트리간에 순서가 존재한다는 점도 다른 점이다. 따라서 왼쪽 서브트리와 오른쪽 서브트리를 구별한다.

이진 트리의 성질

n개의 노드를 가진 이진트리

간선의 개수 : n-1개
이진트리의 높이 : 최대 -> n, 최소 -> upper(log2(n+1))

높이가 h인 이진트리

노드의 개수 : 최대 -> $2^h-1$, 최소 -> h

이진 트리의 분류

• 포화 이진트리 : 각 레벨에 노드가 꽉 차여있음
• 완전 이진트리 : 공집합이 한쪽으로 모아져있음
• 기타 이진트리 : 공집합이 한쪽으로 모아져 있지 않음

이진 트리의 표현

배열 표현법

일단 완전 이진 트리라고 가정하고 이진 트리의 깊이가 k이면 최대 $2^k-1$개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드들을 저장한다.

부모와 자식의 인덱스 사이에는 다음과 같은 공식이 성립된다.

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

다음의 공식이 성립할려면 i는 0이 될 수 없다. 즉 1부터 시작

링크 표현법

노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 노드와 노드를 연결한다. 노드는 3개의 필드를 가지는데, 데이터 저장 필드, 왼쪽 자식 노드, 오른쪽 자식 노드를 가르키는 2개의 포인터 필드가 있다.

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

링크드 리스트는 1차원적인 연결된 구조라면 링크 표현법 이진 트리는 2차원적인 연결된 구조이다. 자식이 없는 노드 ( 단말 노드) 는 각 포인터가 NULL이 되겠다.

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

typedef struct TreeNode 
{
	int data;
	struct TreeNode *left, *right;
} TreeNode;
//  	    n1
//		   / |
//		  n2  n3
int main(void)
{
	
	TreeNode *n1, *n2, *n3;
	n1 = (TreeNode *)malloc(sizeof(TreeNode));		// 동적으로 트리 생성
	n2 = (TreeNode *)malloc(sizeof(TreeNode));
	n3 = (TreeNode *)malloc(sizeof(TreeNode));

	n1->data = 10;		// 첫 번째 노드를 설정한다.
	n1->left = n2;
	n1->right = n3;

	n2->data = 20;		// 두 번째 노드를 설정한다.
	n2->left = NULL;
	n2->right = NULL;

	n3->data = 30;		// 세 번째 노드를 설정한다.
	n3->left = NULL;
	n3->right = NULL;

	free(n1); free(n2); free(n3);
	return 0;
}

이진 트리의 순회

: 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것

이진 트리 순회 방법

왼쪽 서브트리를 L, 오른쪽 서브트리를 R, 루트를 V라고 하자.

• 전위순회 : VLR
• 중위순회 : LVR
• 후위순회 : LRV

각각의 서브트리 또한 이진 트리이기에 전체 이진 트리와 똑같은 방법을 적용할 수 있다. - 순환(재귀) 사용

전위 순회

• 알고리즘
  1. 노드 x가 NULL이면 더 이상 순환 호출을 하지 않는다.
  2. x의 데이터를 출력한다.
  3. x의 왼쪽 서브트리를 순환 호출하여 방문한다.
  4. x의 오른쪽 서브트리를 순환 호출하여 방문한다.

전위 순회 구현

// 전위 순회
void preorder(TreeNode *root, FILE* rp) {//파일에다 결과 출력
	if (root != NULL) {
		fprintf(rp,"[%d] ", root->data);  // 노드 방문
		preorder(root->left, rp);// 왼쪽서브트리 순회
		preorder(root->right, rp);// 오른쪽서브트리 순회
	}
}

중위 순회

• 알고리즘
  1. 노드 x가 NULL이면 더 이상 순환 호출을 하지 않는다.
  2. x의 왼쪽 서브트리를 순환 호출하여 방문한다.
  3. x의 데이터를 출력한다.
  4. x의 오른쪽 서브트리를 순환 호출하여 방문한다.

중위 순회 구현

// 중위 순회
void inorder(TreeNode *root, FILE *rp) {	//파일에다 결과 출력
	if (root != NULL) {
		inorder(root->left, rp);// 왼쪽서브트리 순회
		fprintf(rp,"[%d] ", root->data);  // 노드 방문
		inorder(root->right, rp);// 오른쪽서브트리 순회
	}
}

후위 순회

• 알고리즘
  1. 노드 x가 NULL이면 더 이상 순환 호출을 하지 않는다.
  2. x의 왼쪽 서브트리를 순환 호출하여 방문한다.
  3. x의 오른쪽 서브트리를 순환 호출하여 방문한다.
  4. x의 데이터를 출력한다.
  

후위 순회 구현

// 후위 순회
void postorder(TreeNode *root, FILE* rp) {
	if (root != NULL) {
		postorder(root->left, rp);// 왼쪽서브트리 순회
		postorder(root->right, rp);// 오른쪽서브트리 순회
		fprintf(rp,"[%d] ", root->data);  // 노드 방문
	}
}

반복적 순회 스택

이진 트리의 왼쪽 노드들은 NULL노드에 도달할 때까지 스택에 추가 되었다가 NULL 노드에 도달하면 스택에서 하나씩 삭제된다. 그 후 노드의 오른쪽 노드로 이동한다. 이 과정을 공백 스택이 될 때까지 되풀이 하면 중위 순회 할 수 있다.

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

레벨 순회

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

먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입한는 것으로 한 번의 반복을 끝낸다. 이러한 반복을 큐에 더 이상의 노드가 없을 때까지 계속한다.

즉 반복문으로만 구현 -> 큐 사용

#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;
}

// 결과 : 15->4->20->1->16->25

다양한 순회 방법이 있는데 사용자는 자신에게 필요한 순회 방법을 택하여 프로그램에 응용하면 되겠다.

이진 트리 추가 연산

• 노드의 개수

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) {
		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;

	if (node != NULL)
		height = 1 + max(get_height(node->left),
			get_height(node->right));

	return height;
}

트리의 응용

수식 트리 처리

• 단말노드에는 피연산자를 넣는다. 1,2,3....
• 비단말노드에서는 연산자를 넣는다. -,+,*....
• 후위순회를 노드를 읽는다면 수식을 계산할 수 있다.

#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)
{
	if (root == NULL)// 수식 트리가 공백 상태라면
		return 0;	
	if (root->left == NULL && root->right == NULL) // 단말노드라면 데이터 반환
		return root->data;
	else {			// 후위 순회 
		int op1 = evaluate(root->left);			// 왼쪽 서브트리 순환 호출
		int op2 = evaluate(root->right);		// 오른쪽 서브 트리 순환 호출
		printf("%d %c %d을 계산합니다.\n", op1, root->data, op2);	
		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;
}

디렉토리 용량 계산

컴퓨터 디렉토리 용량을 알려면 어떻게 하여야 할까?
하나의 디렉토리 안에 다른 디렉토리가 있을 수 있으므로 먼저 서브 디렉토리의 용량을 모두 계산한 다음에 루트 디렉토리의 용량을 계산하여야 한다.

즉, 후의 순회를 사용하여 순환 호출되는 순환 함수가 용량을 반환하도록 만든다.

#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)
{
	//      0
          /   \
         50    100
         	  /   \
            500    200
	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 };

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