기존의 트리 순회 알고리즘(중위, 전위, 후위) 은 모두 순환호출(=스택)을 이용한 알고리즘이었습니다.

순환의 특성 상 트리의 높이가 커질수록 순환의 깊이가 깊어져서 상당히 비효율적일 수 있습니다.

쓰레드 이진트리는 노드의 NULL링크를 활용하여 순환 호출없이, 즉 반복문으로 순회할 수 있는 방법입니다.


선행 노드인 중위 선행자나 중위 순회 시 후속노드인 중위 후속자를 저장 시켜놓은 트리가 쓰레드 이진트리입니다.


중위 순회를 한다고 가정하여 중위 후속자를 저장한 쓰레드 이진트리를 구현해 보겠습니다.

일단 treeNode구조체에 쓰레드 정보를 가질 is_thread변수를 추가합니다. 값이 1이면 쓰레드를 가지고, 0이면 일반적인 트리입니다.


구현 함수는 2가지가 있습니다.

1. 쓰레드 중위순회 함수

후속자를 찾아 순서대로 출력합니다.


2. 중위 후속자를 찾는 함수( 중위 후속자를 반환)

=> 노드가 쓰레드를 가지면(is_thread==1) 오른쪽 자식을 반환합니다.

위 트리를 구성하는 과정에서 A와 C, B와G, D와F를 연결시켜놨기 때문에 쓰레드를 갖는 노드의 오른쪽 자식은 후속자가 됩니다.

현재 노드의 오른쪽자식 노드가 NULL이거나 p가 쓰레드를 가지면 q를 반환합니다.

(NULL일경우 1번함수에서 걸러지고, p가 쓰레드를 가지면 오른쪽 자식노드가 있음을 알기 때문)

그리고 G나 F같은 일반 노드 같은경우, 중위순회를 위해 서브 트리의 가장 왼쪽으로 가는 연산식이 필요합니다.


순회 순서는 순환방법과 똑같기 때문에 후속자를 찾는 포인트만 알고 있으면 구현이 어렵지 않습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define size 10
typedef struct treeNode
{
    int data;
    struct treeNode* left, * right;
    int is_thread;
}treeNode;
 
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;
void thread_inorder(treeNode* t);
treeNode* find_successor(treeNode* p);
int main()
{
    //쓰레드를 설정한다.
    n1.right = &n3;
    n2.right = &n7;
    n4.right = &n6;
    thread_inorder(exp);
}
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);
    puts("");
}
treeNode* find_successor(treeNode* p)
{
    treeNode* q = p->right;
    //q가 NULL일 때도 반환(어짜피 중위순회 함수에서 NULL을 받아 걸러짐
    //p가 (q의 오른쪽자식이) 쓰레드면 바로 반환
 
    if (q == NULL || p->is_thread == TRUE)
        return q;
    //G, F 같은 일반 노드의 경우 중위순회를 위해 맨 왼쪽노드를 찾음
    while (q->left != NULL)q = q->left;
    return q;
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


트리를 이용한 순회기법들을 알아봤고 그 외에 더 몇가지 살펴볼만한 트리의 연산 몇가지를 구현해보았습니다.

노드의갯수+ 단말노드의갯수+ 트리의 높이를 구하는 3가지 연산인데, 각 연산이 순환 호출이 주된 연산이므로

코드를 잘 살펴보고 이해해야합니다. 각 연산의 핵심 키워드는 아래와 같습니다.


1. 노드의 갯수

각 노드를 전체적으로 순회하여 각 서브트리에 대해 순환호출 한 뒤 반환되는 값에 1을 더하여 반환합니다.

(반환된 서브트리의 갯수와 루트노드의 갯수1을 더한값을 반환해야합니다.) 


2. 단말 노드의 갯수

역시 각 노드를 전체적으로 순회하면서 만약 왼쪽, 오른쪽 자식이 동시에 0이면 단말노드이므로 1을 반환합니다.

그렇지않으면 더 깊게 내려가 서브트리에 대해 순환 호출하여 단말노드를 탐색합니다.


*3. 트리의 높이

전체 순회하되 1,2처럼 반환된 값을 단순히 더하는게 아니라 서브트리에서 반환된 서브트리의 높이 중  최댓값을 구하여 반환합니다.

1,2 번에 비해 약간 까다로운 편인데 노드의 갯수가 작은 경우를 직접그려서 이해해보면 쉽게 이해할 수 있습니다.

주의: 매크로함수 정의 시 괄호를 잘 설정해야합니다.(괄호 설정 오류 시 높이 0출력)

수식 사이에는 괄호를 하나씩 더 쳐주는게 좋습니다. 


계산할 수식트리는 아래와 같습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b) (((a)>(b))?(a):(b))//괄호를 무조건 둘러싸자
 
//#define max(a,b) (((a)>(b))?(a):(b)) => 오류발생 
typedef struct treeNode
{
    int  data;
    struct treeNode* left, * right;
}treeNode;
 
treeNode n1 = { 0,NULL,NULL };
treeNode n2 = { 1,NULL,NULL };
treeNode n3 = { 3,&n1,&n2 };
treeNode n4 = { 2,NULL,NULL };
treeNode n5 = { 4,&n3,&n4 };
treeNode* root = &n5;
int calc_node_count(treeNode* root)
{
    int cnt = 0;
    if (root != NULL)
    {
        cnt = 1 + calc_node_count(root->left) + calc_node_count(root->right);
    }
    return cnt;
}
int calc_leaf_count(treeNode* root)
{
    int cnt = 0;
    if (root != NULL)
    {
        if (root->left == NULL && root->right == NULL)//단말 노드이면
        {
            return 1;
        }
        else
        {
            cnt = calc_leaf_count(root->left) + calc_leaf_count(root->right);
        }
    }
    return cnt;
}
int calc_height(treeNode* root)
{
    int height = 0;
    if (root != NULL)
    {
        height = 1 + max(calc_height(root->left), calc_height(root->right));
    }
    return height;
}
int main()
{
    printf("트리의 전체노드 갯수는 %d개입니다.\n",calc_node_count(root));
    printf("트리의 단말노드 갯수는 %d개입니다.\n",calc_leaf_count(root));
    printf("트리의 높이는 %d입니다.\n", calc_height(root));
}
cs



결과







저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


왼쪽자식+오른쪽 자식+루트 순으로 탐색하는 후위순회를 이용해 트리구조처럼 되어있는 컴퓨터의 디렉토리 용량을 계산할 수 있습니다.

단, 이진트리임을 가정하므로 각 디렉토리안에 2개를 초과하는 디렉토리 존재X


루트 디렉토리의 왼쪽 서브 디렉토리의 총 디렉토리 용량과 오른쪽 서브 디렉토리의 총 디렉토리의 용량을 구하고

그 두개의 용량합에 루트디렉토리의 용량을 합하면 총 디렉토리의 용량이 계산됩니다.

후위순회를 약간 응용하여 쉽게 구현할 수 있습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
typedef struct treeNode
{
    int data;
    struct treeNode* left, * right;
}treeNode;
 
int calc(treeNode* root)
{
    int left_size, right_size;
    if (root == NULL)return 0;
    else
    {
        left_size = calc(root->left);//후위
        right_size = calc(root->right);//후위
        return left_size + right_size + root->data;//계산한 용량값을 리턴한다.
    }
}
int main()
{
    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(&n1));
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


순환을 이용한 트리의 순회방법에는 3가지(전위,중위,후위) 순회 기법이있었습니다.

이런 표준적인 순회방법 외에도 레벨 순회가 많이 사용되는데, 레벨순회는 각 노드를 레벨순으로 검사하는 순회방법입니다.

위에서 부터 아래로 내려가면서 동일한 레벨의 경우 좌에서 우로 방문하며 순회를 진행합니다.


저번에 살펴본 순회기법들은 순환기법, 즉 스택구조를 이용했습니다.(순환호출==간접적인 스택의사용)

이번에 알아볼 레벨순회기법들은 큐를 이용합니다. 이 방식은 나중에 배울 그래프 파트의 BFS탐색과 거의 동일한 기법입니다.

즉 First-in First-out 속성을 이용하여 먼저 들어온 데이터를 먼저 출력하게끔 하기위해 큐를 사용합니다.


먼저, 큐에 있는 노드를 꺼내어 방문하고 그 노드의 자식노드를 큐에 삽입하는 작업을 큐에 더 이상의 노드가 없을 때 까지 반복합니다.


루트노드 큐에 삽입-> 큐가 empty하지 않을 때 까지 꺼내고 출력하고 자식노드를 큐에 삽입하는 연산 반복


결국, while(is_empty(&q)) 함수를 빠져나오게되면 최종적인 레벨순회가 끝나게됩니다.


구현을 위해 원형큐를 사용했고, 큐에 담겨지는 데이터는 트리노드이므로 큐의 데이터 타입을 treeNode*로 지정해야합니다.

결국 큐에 삽입되는 것은 트리노드가 되고 큐에담겨진 트리의 정보를 이용하여 순회를 진행합니다. 


아래의 수식트리를 이용하여 레벨순회를 구현해보았습니다.




코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_QSIZE 10
typedef struct treeNode
{
    char data;
    struct treeNode* left, * right;
}treeNode;
typedef treeNode* element;
typedef struct QType
{
    element queue[MAX_QSIZE];
    int front, rear;
}QType;
treeNode n1 = { 'A',NULL,NULL };
treeNode n2 = { 'B',NULL,NULL };
treeNode n3 = { 'C',NULL,NULL };
treeNode n4 = { 'D',NULL,NULL };
treeNode n5 = { '*',&n1,&n2 };
treeNode n6 = { '/',&n3,&n4 };
treeNode n7 = { '+',&n5,&n6 };
treeNode* root = &n7;
 
 
void init(QType* q)
{
    q->front = 0, q->rear = 0;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int is_full(QType* q)
{
    return (q->rear + 1) % MAX_QSIZE == q->front;
}
void enqueue(QType* q, element item)
{
    if (is_full(q))
    {
        printf("요소가 꽉 찼습니다.\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QSIZE;
    q->queue[q->rear] = item;
}
treeNode* dequeue(QType* q)
{
    if (is_empty(q))
    {
        printf("요소가 비었습니다.\n");
        exit(1);
    }
    else
    {
        q->front = (q->front + 1) % MAX_QSIZE;
        return q->queue[q->front];
    }
}
void level_order(treeNode* root)
{
    QType q;
    init(&q);
    if (root == NULL)return;
    enqueue(&q, root);
    while (!is_empty(&q))
    {
        root = dequeue(&q);
        printf("%c ", root->data);
        if (root->left)//왼쪽 자식이 존재하면
            enqueue(&q, root->left);
        if (root->right)//오른쪽 자식이 존재하면
            enqueue(&q, root->right);
    }puts(" ");
}
int main()
{
    level_order(root);
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


이진트리의 순회방법에는 전위순회, 중위순회, 후위순회의 3가지 방법이 있습니다.

이는 루트와 왼쪽 서브트리, 오른쪽 서브 트리 중에서 루트를 언제 방문 하느냐에 따라 구분할 수 있습니다.

기본적으로 트리의 순회는 순환구조를 이용합니다. 즉, 문제의 구조는 같고 크기만 작아지는 경우 순환을 적용할 수 있습니다.

루트:V, 왼쪽 서브 트리:L, 오른쪽 서브트리:R 이라고 할 때 순회과정은 아래와 같습니다.


V->L->R : 전위순회(preorder traversal)

L->V->R : 중위순회(inorder traversal)

L->R->V : 후위순회(postoreder traversal)


트리를 보고 각 순회방법에 따라 순회방법을 나열할 경우 아래처럼 순회방법을 적어놓고 생각하면 편합니다.



1. 전위 순회

 1) 루트 노드를 방문한다.

 2) 왼쪽 서브 트리를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.


2. 중위 순회

 1) 왼쪽 서브 트리를 방문한다.

 2) 루트 노드를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.


3. 후위 순회

 1) 왼쪽 서브 트리를 방문한다.

 2) 루트 노드를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.


트리의 순회과정을 코드를 보고 분석 할 때는 직접 작은 단위(예를들어 높이2의 노드가3인 간단한 트리구조)부터 직접 손으로 그려가며

이해하는게 편합니다. (노드갯수가 조금만 많아져도 복잡해짐) 


이제 아래와 같은 트리를 이용해 각 순회방법을 적용해 보겠습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
typedef struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
}treeNode;
 
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;
void preorder(treeNode* root)
{
    //루트가 존재할 때
    if (root)
    {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
void inorder(treeNode* root)
{
    if (root)
    {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
void postorder(treeNode* root)
{
    if (root)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}
int main()
{
    printf("전위순회: ");
    preorder(root); puts(" ");
    printf("중위순회: ");
    inorder(root); puts(" ");
    printf("후위순회: ");
    postorder(root); puts(" ");
 
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16

+ Recent posts

티스토리툴바