※ 이 글은 코드 위주이니 설명은 아래 링크로 확인 !
※ C 트리(Tree) 설명
C 트리(Tree) 설명
트리 - 비선형 자료구조의 일종이다. - 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. ※ 사용 예로 컴퓨터의 디렉터리 구조를 들 수 있다. 용어 정리 1. 노드(Node) : 트리의 구성요소
srdeveloper.tistory.com
이진 탐색 트리에 사용할 구조체
typedef struct Node
{
int data;
struct Node* Left, * Right;
}Node; ※ 2개의 자식 노드를 가질것이므로 왼쪽, 오른쪽 참조 변수를 가진다.
데이터 삽입(Insert)
Node* Insert(Node* node, int data)
{
if(node == NULL)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->Left = NULL;
newNode->Right = NULL;
return newNode;
}
else
{
if(node->data > data)
{
node->Left = Insert(node->Left, data);
}
else if(node->data < data)
{
node->Right = Insert(node->Right, data);
}
else
{
//중복 된 데이터이므로 추가하지 않는다.
}
return node;
}
} ※ 간결한 코드를 위해 재귀함수로 작성했다. (밑에 나올 수정, 탐색, 삭제, 순회 또한 재귀로 구성한다.)
※ 인수로 받은 데이터와 노드가 가진 키값의 대소관계에 따라 재귀 함수를 호출해준다.
데이터 수정(Modify) void Modify(Node* node, int data, int newData)
{
if(node == NULL) return;
if(node->data == data)
{
node->data = newData;
}
else
{
if(node->data > data)
{
Modify(node->Left, data, newData);
}
else
{
Modify(node->Right, data, newData);
}
}
} ※ 더 이상 newData와 같은 키값을 가진 노드가 없거나, 같은 키값을 가진 노드가 나올때까지 재귀함수를 호출해서 만약 존재하면 데이터를 변경한다.
※ 수정할 때 이진 탐색 트리의 규칙에 위배되는 값이 들어가도 수정되는 코드는 따로 넣지 않았다. (기능의 본질에만 중점을 두고 작성되었다.)
데이터 탐색(Search)
Node* Search(Node* node, int data)
{
if(node == NULL) return NULL;
if(node->data == data)
{
return node;
}
else
{
if(node->data > data)
{
return Search(node->Left, data);
}
else
{
return Search(node->Right, data);
}
}
} ※ 더 이상 data와 같은 키값을 가진 노드가 없으면 NULL, 같은 키값을 가진 노드가 나올때까지 재귀함수를 호출해서 만약 노드가 존재하면 찾은 노드를 반환한다.
데이터 삭제(Delete)
Node* FindMinNode(Node* node, Node** minNode)
{
if(node->Left == NULL)
{
*minNode = node;
node = node->Right;
return node;
}
else
{
node->Left = FindMinNode(node->Left, minNode);
return node;
}
}
Node* Delete(Node* node, int data)
{
if(node == NULL) return NULL;
if(node->data == data)
{
Node* deleteNode = node;
if(node->Left == NULL && node->Right == NULL)
{
node = NULL;
}
else if(node->Left != NULL && node->Right == NULL)
{
node = node->Left;
}
else if(node->Left == NULL && node->Right != NULL)
{
node = node->Right;
}
else
{
Node* minNode = NULL;
node->Right = FindMinNode(node->Right, &minNode);
minNode->Left = deleteNode->Left;
minNode->Right = deleteNode->Right;
node = minNode;
}
free(deleteNode);
return node;
}
else
{
if(node->data > data)
{
node->Left = Delete(node->Left, data);
}
else
{
node->Right = Delete(node->Right, data);
}
return node;
}
} ※ 이진탐색트리에서의 삭제는 다른 자료구조와는 다르게 다소 복잡한 형태를 가지고 있다.
1. 삭제할 키 값을 가지고 있는 노드를 재귀함수로 탐색한다.
2. 노드를 찾게되면 조건을 다음과 같이 나눈다.
2-1) 찾은 노드에서 양쪽의 자식이 없을 때 : 찾은 노드만 삭제하면 된다. (반환값 NULL)
2-2) 왼쪽 자식 노드만 있을 때 : 찾은 노드를 삭제하고 왼쪽 노드를 반환한다.
2-3) 오른쪽 자식 노드만 있을 때 : 찾은 노드를 삭제하고 오른쪽 노드를 반환한다.
2-4) 양쪽 자식 노드가 전부 존재할 때 : 왼쪽 자식 노드 중 가장 큰 키값을 가진 노드를 찾거나, 오른쪽 자식 노드 중 가장 작은 키값을 가진 노드를 찾아서 키값이 일치한 노드의 자리에 넣어주고 기존의 노드는 삭제한다. (이렇게 찾는 이유는 이진 탐색 트리의 규칙 때문에 그렇다.)
※ 위의 코드를 기준으로는 오른쪽 자식 노드에서 가장 작은 키값을 가진 노드를 탐색하고있다.
※ 즉, 왼쪽 자식이 없는 노드가 가장 작은 키값을 가진 노드가 될것이므로 왼쪽 자식이 없는 노드를 찾을때까지 FindMinNode로 재귀함수를 호출한다.
※ 위 과정중에서 2-4의 방법이 제일 복잡한데, 이유는 FindMinNode 함수로 찾은 노드가 오른쪽 자식 노드를 갖고 있을 수도 있기 때문이다.
※ 즉, FindMinNode로 찾은 노드(이하 minNode)에서 Delete함수에서 인수로 받은 data와 같은 키값을 가지고 있는 노드(이하 rootNode)의 위치로 교체하기전에 minNode의 자식을 minNode의 부모노드와 연결 시키고 rootNode의 위치로 교체되어야 한다.
풀 소스코드는 다음과 같다.
#include <stdio.h>
typedef struct Node
{
int data;
struct Node* Left, * Right;
}Node;
Node* Insert(Node* node, int data)
{
if(node == NULL)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->Left = NULL;
newNode->Right = NULL;
return newNode;
}
else
{
if(node->data > data)
{
node->Left = Insert(node->Left, data);
}
else if(node->data < data)
{
node->Right = Insert(node->Right, data);
}
else
{
//중복 된 데이터이므로 추가하지 않는다.
}
return node;
}
}
void Modify(Node* node, int data, int newData)
{
if(node == NULL) return;
if(node->data == data)
{
node->data = newData;
}
else
{
if(node->data > data)
{
Modify(node->Left, data, newData);
}
else
{
Modify(node->Right, data, newData);
}
}
}
Node* Search(Node* node, int data)
{
if(node == NULL) return NULL;
if(node->data == data)
{
return node;
}
else
{
if(node->data > data)
{
return Search(node->Left, data);
}
else
{
return Search(node->Right, data);
}
}
}
Node* FindMinNode(Node* node, Node** minNode)
{
if(node->Left == NULL)
{
*minNode = node;
node = node->Right;
return node;
}
else
{
node->Left = FindMinNode(node->Left, minNode);
return node;
}
}
Node* Delete(Node* node, int data)
{
if(node == NULL) return NULL;
if(node->data == data)
{
Node* deleteNode = node;
if(node->Left == NULL && node->Right == NULL)
{
node = NULL;
}
else if(node->Left != NULL && node->Right == NULL)
{
node = node->Left;
}
else if(node->Left == NULL && node->Right != NULL)
{
node = node->Right;
}
else
{
Node* minNode = NULL;
node->Right = FindMinNode(node->Right, &minNode);
minNode->Left = deleteNode->Left;
minNode->Right = deleteNode->Right;
node = minNode;
}
free(deleteNode);
return node;
}
else
{
if(node->data > data)
{
node->Left = Delete(node->Left, data);
}
else
{
node->Right = Delete(node->Right, data);
}
return node;
}
}
void ShowInOrder(Node* node)
{
if (node == NULL) return;
ShowInOrder(node->Left);
printf("%d ", node->data);
ShowInOrder(node->Right);
}
void main()
{
Node* root = NULL;
//INSERT
root = Insert(root, 20);
root = Insert(root, 10);
root = Insert(root, 32);
root = Insert(root, 4);
root = Insert(root, 13);
root = Insert(root, 25);
root = Insert(root, 55);
// 내부 구조
// 20
// 10 32
// 4 13 25 55
ShowInOrder(root);
//결과 : 4 10 13 20 25 32 55
//MODIFY
Modify(root, 10, 12);
ShowInOrder(root);
//결과 : 4 12 13 20 25 32 55
//SEARCH
printf("%d", Search(root, 12)->data);
//결과 : 12
//DELETE
root = Delete(root, 32);
// 내부 구조
// 20
// 10 55
// 4 13 25
ShowInOrder(root);
//결과 : 4 12 13 20 25 55
} ※ 중위순회함수는 트리의 이해를 돕기 위해 잠시 넣은 함수이다.
※ 내부 구조 주석에서 보여지는 트리 데이터는 게시물 상단의 링크에서 사용한 트리를 바탕으로 세팅했다.
