자료구조 - 트리(Tree) with C

트리란?

트리는 데이터 사이의 계층 관계를 나타내는 자료구조입니다.

이렇게 생김

• 루트는 트리의 가장 위쪽에 있는 노드입니다. 하나의 트리에는 하나의 루트가 있습니다. 그림을 거꾸로 보면 나무처럼 생겼죠?

 

• 리프는 트리의 가장 아랫부분에 있는 노드를 리프라고 합니다. 엄밀히 말하면 해당 노드가 더 이상 아래로 뻗어 나갈 수 없으면 리프노드입니다. external node 라고도 합니다.

 

• 레벨은 루트로 부터 얼마나 떨어져 있는가를 나타냅니다. 루트의 레벨은 0이고 루트부터 가지가 하나씩 뻗어 나갈때 마다 레벨이 1씩 늡니다.

 

• 차수는 노드가 갖는 자식의 수를 차수라고 합니다. 예를 들어 위 루트의 차수는 2입니다. 모든 노드의 자식 수가 2개 이하인 경우는 특별히 이진트리 라고 합니다.

 

• 트리의 특징중 하나는 임의의 두 노드를 연결하는 간선 경로(연결 경로)가 한가지 밖에 없다는 것입니다.

 

• 만약 노드의 수가 N개라면 노드들을 연결하는 간선들의 수는 N-1개 입니다.

 

이진트리의 노드

이진트리를 만드려면 노드를 먼저 만들어야 합니다. 이진트리의 노드는 데이터와 2개의 자식 노드를 가지는 포인터로 이루어져 있습니다.

 

2개의 포인터를 지님

typedef struct {
    Data data;
    struct Node *Lptr, *Rptr; //struct가 붙는 이유는 Node가 완전히 정의되지 않았기 때문
}Node;

만약 노드를 가리키지 않는 포인터가 존재하면 해당 ptr은 NULL을 가리키게 됩니다.

 

이진검색트리 만들기

이진검색트리는 자료를 저장하여 이진검색처럼 빠르게 검색할 수 있고 정보의 추가&제거가 쉽다는 장점이 있습니다. 이진트리에서 다음 조건을 만족하면 됩니다.

 

• 어떤 노드N을 기준으로 왼쪽 부분 트리의 모든 값은 N의 값보다 작아야 합니다

 

• 오른쪽 부분 트리노드의 값은 N의 값보다 커야합니다.

 

• 같은 값을 갖는 노드는 없습니다.

   

   

   

   

위에서 만든 노드를 바탕으로 이진검색트리를 구현해 보겠습니다. 자료형은 int입니다.

#include<stdio.h>
#include<stdlib.h>
typedef struct {
	int data;
	struct Node *Lptr, *Rptr; //struct가 붙는 이유는 Node가 완전히 정의되지 않았기 때문
}Node;

//노드 동적할당
Node *allocNode() {
	return calloc(1, sizeof(Node));
}

//노드 값 설정
void setNode(Node *n, const int *x, const Node *Lptr, const Node *Rptr) {
	n->data = *x;
	n->Lptr = Lptr;
	n->Rptr = Rptr;
}

//주어진곳부터 탐색
Node *Search(Node *p, const int *x) {
	if (p == NULL)
		return NULL;
	else if (p->data == *x)
		return p;
	else if (p->data > *x)
		Search(p->Lptr, *x);
	else
		Search(p->Rptr, *x);
}

//트리에 값을 추가
Node *Add(Node *p, const int *x) {
	if (p == NULL) {
		p = allocNode();
		setNode(p, x, NULL, NULL);
	}
	else if (p->data == *x) //같은 값이 들어올 수 없습니다.
		printf("Error! Same data is exist!\n"); 
	else if (p->data > *x)
		p->Lptr = Add(p->Lptr, x);
	else
		p->Rptr = Add(p->Rptr, x);
	return p;
}

//특정값의 노드 삭제
int Remove(Node **root, const int *x) {
	Node *next, *temp;
	Node **left;
	Node **p = root;

	while (1) { //지울 노드를 찾습니다
		if (*p == NULL) { //그런 값이 없나봐
			printf("There is no such value of node! Error!");
			return -1;
		}
		else if(*(&(*p)->data) == *x)//찾았다!
			break;
		else if (*(&(*p)->data) > *x) 
			p = &((*p)->Lptr);
		else 
			p = &((*p)->Rptr);
	}

	if ((*p)->Lptr == NULL)
		next = (*p)->Rptr; 
	else {
		left = &((*p)->Lptr);
		while ((*left)->Rptr != NULL)
			left = &(*left)->Rptr;
		next = *left;
		*left = (*left)->Lptr;
		next->Lptr = (*p)->Lptr;
		next->Rptr = (*p)->Rptr;
	}
	temp = *p;
	*p = next;
	free(temp);

	return 0;
}

//트리를 출력함 올림차순이니까 중위순회겠죠?
void PrintTree(const Node *p) {
	if (p != NULL) {
		PrintTree(p->Lptr);
		printf("%d ", p->data);
		PrintTree(p->Rptr);
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	Node *root = NULL;
	int n, t; scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &t);
		root = Add(root, &t);
	}
	Remove(&root, &t);
	PrintTree(root);
}

---

입력:

10 //입력할 수의 개수
3 88 43 7 23 98 48 33 95 1 //입력할 수

 

출력:

올림차순 순서대로~

---

 수를 입력받고 입력받은 수를 중위순회하여 올림차순으로 출력하는 프로그램을 간단한 예제로 짜봤습니다. Remove 부분이 조금 어려웠습니다. 집중해서 볼 필요가 있는 부분이라고 생각합니다.

문제 풀어보기

안녕하세요 PostBarca의 December 입니다. 오늘은 이진검색트리를 응용한 문제를 풀어볼건데요

 

백준 2957 이진탐색트리 링크 : https://www.acmicpc.net/problem/2957

2957번: 이진 탐색 트리

문제에서 주어진 pseudo 코드대로 제출하면 그대로 시간초과가 나버립니다.

 

이진트리에 대한 이해도가 더 생기면 다시 풀어보도록 하겠습니다.

 

정보가 유익하셨다면 구ㄷ..

 

아직은 풀기가 좀 버거운것 같아요 ^^;

 

일단 생각을 해보자면 C의 값이 추가되는 회수는 추가되는 노드의 레벨값과 같다는 아이디어를 이용하면 될것 같은데.