트리 1에서 트리의 구성 요소와 이진트리의 종류에 대해서 알아봤다.
이번에는 연결리스트를 통해 트리가 어떻게 만들어지는지 살펴보자.
트리 구조체
트리는 그림과 같이 노드 구조체에 자신의 데이터 값과, left 노드, right 노드를 포함한다.
코드로 구현해보면 다음과 같다.
typedef struct Node {
struct Node* left;
struct Node* right;
int data;
}Node;트리 노드 생성하기
Node* makeNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}노드 생성하는 것은 연결리스트에서 노드 생성하는 것과 같다.
노드를 동적할당 해준 뒤 data값을 넣어주고 left와 right를 NULL로 초기화 해준다.
트리 노드 연결하기
void makeLeftChild(Node* p, Node* lchild) {
p->left = lchild;
}
void makeRightChild(Node* p, Node* rchild) {
p->right = rchild;
}트리 노드를 연결하는 방법은 구현 방법에 따라 다양하다.
위 코드는 부모 노드를 알 경우 왼쪽 자식과 오른쪽 자식을 연결하는 방법이다.
트리 순회하기
노드를 생성하고 연결하였으면 트리가 만들어진 상태이다.
배열과 같은 선형 구조에서는 index = 0부터 for문을 통해 탐색을 쉽게 할 수 있지만 트리는 비선형 구조이므로 root 노드부터 순차적으로 탐색을 진행한다.
이 방법을순회라고 한다.
순회 방법은 다양하지만 우리는 그중에서 깊이우선 탐색(DFS)을 알아보려고 한다.
DFS는 전위 순회, 중위 순회, 후위 순회가 있다.
각각의 이름은 자기 자신의 노드가 언제 방문되느냐를 기준으로 생각하면 된다.
전위 순회 : 자기 자신 ->왼쪽 서브트리 -> 오른쪽 서브트리
중위 순회 : 왼쪽 서브트리 -> 자기 자신 -> 오른쪽 서브트리
후위 순회 : 왼쪽 서브트리 -> 오른쪽 서브트리 ->자기 자신
전위 순회
void pre_order(Node* p) {
if (p == NULL)
return;
printf("%d", p->data);
pre_order(p->left);
pre_order(p->right);
}중위 순회
void in_order(Node* p) {
if (p == NULL)
return;
pre_order(p->left);
printf("%d", p->data);
pre_order(p->right);
}후위 순회
void post_order(Node* p) {
if (p == NULL)
return;
post_order(p->left);
post_order(p->right);
printf("%d", p->data);
}코드를 보면 print의 위치에 변화에 따라 순회 방식이 달리되는 것을 볼 수 있다.
만약 이런 트리가 있을 때 각 노드의 방문 순서를 확인해보자.
전위 순회 : 1 - 2 - 4 - 5 - 3 - 6 - 7
중위 순회 : 4 - 2 - 5 - 1 - 6 - 3 - 7
후위 순회 : 4 - 5 - 2 - 6 - 7 - 3 - 1
순회가 재귀 방식이므로 처음에 헷갈려서 하나하나 그려보며 연습하니 확실히 이해가 갔다.
트리 노드 찾기
위에 트리노드 연결 부분에서 부모노드를 안다고 가정했을 때 부모와 자식을 바로 연결해줄 수 있다.
하지만 우리는 보통 연결해 줄 노드를 직접 찾아야 한다.
따라서 data값이 주어지면 트리의 root 노드부터 순회하여 찾고자 하는 부모 노드를 반환해줘야 한다. 코드는 다음과 같다.
Node* searchNode(Node* p, int target) {
if (p == NULL)
return NULL;
if (p->data == target)
return p;
Node* t = searchNode(p->left, target);
if (t != NULL)
return t;
return searchNode(p->right, target);
}처음에 root노드와 찾으려는 target값을 인자로 전달해줘 트리를 탐색해 target에 해당하는 노드를 반환하는 코드이다.
위에 트리 순회에서 설명한 방식과 비슷하다.
외부노드일 때 NULL을 return해주고 target값을 찾았다면 그 노드를 return 해준다.
재귀를 통해 왼쪽에서 target노드를 찾았다면 그 노드를 return 해주어 오른쪽 탐색을 진행하지 않고, 만약 왼쪽에서 찾지 못했다면 재귀를 통해 오른쪽 탐색을 진행한다.
코드로 트리 구현해보기
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
typedef struct Node {
struct Node* left;
struct Node* right;
int data;
}Node;
Node* makeNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void makeLeftChild(Node* p, Node* lchild) {
p->left = lchild;//
}
void makeRightChild(Node* p, Node* rchild) {
p->right = rchild;
}
Node* searchNode(Node* p, int target) {
if (p == NULL)
return NULL;
if (p->data == target)
return p;
Node* t = searchNode(p->left, target);
if (t != NULL)
return t;
return searchNode(p->right, target);
}
void _free(Node* p) {
if (p == NULL)
return;
_free(p->left);
_free(p->right);
free(p);
}
void post_order(Node* p) {
if (p == NULL)
return;
post_order(p->left);
post_order(p->right);
printf("%d", p->data);
}
void find(Node* p, char* command) {
if (command == NULL)
return;
printf(" %d", p->data);
if (*command == 'R')
find(p->right, command + 1);
else if (*command == 'L')
find(p->left, command + 1);
}
int main() {
int N;
Node* root = NULL;
scanf("%d", &N);
while (N--) {
int p, l_child, r_child;
Node* t;
scanf("%d%d%d", &p, &l_child, &r_child);
if (root == NULL) {
Node* newNode = makeNode(p);
root = newNode;
}
t = searchNode(root, p);
if (l_child) {
Node* lNode = makeNode(l_child);
makeLeftChild(t, lNode);
}
if (r_child) {
Node* rNode = makeNode(r_child);
makeRightChild(t, rNode);
}
}
int count;
scanf("%d", &count);
getchar();
while (count--) {
char command[101];
gets(command);
find(root, command);
puts("");
}
_free(root);
return 0;
}