8장 트리

1. 트리(TREE)

1.1 트리란?

계층적인 구조를 나타태는 자료구조.
부모-자식 관계의 노드들로 이루어진다.

1.2 트리의 용어

노드(node) : 트리 구성요소
루트(root) : 부모가 없는 노드
서브트리(subtree) : 하나의 노드와 그 자손들로 이루어진 트리
단말노드 : 자식이 없는 노드
비단말노드 : 자식을 가지는 노드
레벨(level) : 트리 각층의 번호
높이(height) : 트리의 최대 레벨
차수(degree) : 노드가 가지는 자식 노드의 개수

1.3 이진트리(binary tree)

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

노드의 개수가 n이면 간선의 개수는 n-1
높이가 h인 이진트리는 최소 h개의 노드, 최대 2^h-1개의 노드를 가진다

n개의 노드를 가지는 이진트리의 높이는 최대 n, 최소 log₂(n+1)

1.4 이진트리의 표현

1.4.1 배열 표현법

모든 이진트리를 포화 이진 트리로 가정하고, 각 노드에 번호를 붙여서 
번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

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

1.4.2 링크 표현법

포인터를 사용하여 부모노드가 자식노드를 가리키게 하는 방법

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

//노드는 구조체로, 링크는 포인터로 표현
typedef struct TreeNode
{
	int data;
    struct TreeNode *left, *right;
}

int main()
{
	TreeNode *n1, *n2, *n3;
    //메모리 할당
    n1 = (TreeNode)*malloc(sizeof(TreeNode));
    n2 = (TreeNode)*malloc(sizeof(TreeNode));
    n3 = (TreeNode)*malloc(sizeof(TreeNode));
    
    n1->data = 20;
    n1->left = n2;
    n1->right = n3;
    
    n2->data = 10;
    n2->left = NULL;
    n2->right = NULL;
    
    n3->data = 30;
    n3->left = NULL;
    n3->right = NULL;
    
    free(n1); free(n2); free(n3);
    
    return 0;

}

1.4 이진트리의 순회

순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것

전위순회(preorder traversal) : root-Left-Right
중위순회(inorder traversal) : Left-root-Right
후위순회(postorder traversal) : Left-Right-root

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

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

TreeNode N4 = {1, NULL, NULL};
TreeNode N5 = {16, NULL, NULL};
TreeNode N6 = {25, NULL, NULL};
TreeNode N3 = {20, &N5, &N6};
TreeNode N2 = {4, &N4, NULL};
TreeNode N1 = {15, &N2, &N3};

TreeNode *root = &N1;

void inorder(TreeNode *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("[%d] ", root->data);
        inorder(root->right);
    }
}

void preorder(TreeNode *root)
{
    if (root != NULL)
    {
        printf("[%d] ", root->data);
        inorder(root->left);
        inorder(root->right);
    }
}

void postorder(TreeNode *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        inorder(root->right);
        printf("[%d] ", root->data);
    }
}

int main()
{

    printf("inorder = ");
    inorder(root);
    printf("\n");

    printf("preorder = ");
    preorder(root);
    printf("\n");

    printf("postorder = ");
    postorder(root);
    printf("\n");

    return 0;
}

<실행 결과>
inorder = [1] [4] [15] [16] [20] [25] 
preorder = [15] [1] [4] [16] [20] [25]
postorder = [1] [4] [16] [20] [25] [15]

1.5 반복적인 순회

#include <stdio.h>
#include <stdlib.h>
#define N 100

typedef int element;

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

typedef struct StackType
{
    int top;
    TreeNode *stack[N]; 
} StackType;

void init(StackType *S)
{
    S->top = -1;

    for(int i = 0; i < N; i++)
    {
        S->stack[i] = NULL;
    }
}

int isEmpty(StackType *S)
{
    return S->top == -1;
}

int isFull(StackType *S)
{
    return S->top == N - 1;
}

void push(StackType *S, TreeNode *c)
{
    if (isFull(S))
        printf("Overflow!\n");
    else
    {
        S->top++;
        S->stack[S->top] = c; // 항상 구조체 필드는 포장지에 쌓여있어야 함.
    }
}

TreeNode* pop(StackType *S)
{
    if (!isEmpty(S))
    {
        return S->stack[S->top--];
    }   
    else
        return NULL;
}

void iterInOrder(TreeNode *root)
{
    StackType *S = (StackType *)malloc(sizeof(StackType));
    init(S);

    while(1)
    {
    	//반복문으로 root노드 부터 왼쪽에 있는 값을 스택에 저장
        for (; root != NULL; root = root->left)
            push(S, root);
        
        //가장 우선도가 높은 노드를 root로 설정
        root = pop(S);
		
        if (root == NULL)
            break;
        printf("[%d]", root->data);
        
		//root의 오른쪽 값을 root로 설정 
        root = root->right;
    }
    free(S);
}

int main()
{
	//노드 생성 및 간선 연결
    TreeNode N4 = {1, NULL, NULL};
    TreeNode N5 = {16, NULL, NULL};
    TreeNode N6 = {25, NULL, NULL};
    TreeNode N3 = {20, &N5, &N6};
    TreeNode N2 = {4, &N4, NULL};
    TreeNode N1 = {15, &N2, &N3};
	
    //root 노드 설정
    TreeNode *root = &N1;
	
    //반복 중위 연산
    iterInOrder(root);

    return 0;
}

<실행 결과>
[1][4][15][16][20][25]

1.6 레벨 순회

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

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

#define N 100

typedef int element;

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

typedef struct QueueType
{
    TreeNode *queue[N];
    int front, rear;
}QueueType;

void init(QueueType *Q)
{
    Q->front = Q->rear = 0;
}

int isEmpty(QueueType *Q)
{
    return Q->front == Q->rear;
}

int isFull(QueueType *Q)
{
    return Q->rear == N-1;
}

void enqueue(QueueType *Q, TreeNode *root)
{
    if (isFull(Q))
    {
        printf("Queue is full!\n");
        return; // 반환 값을 수정
    }
    Q->queue[Q->rear++] = root;
}

TreeNode *dequeue(QueueType *Q)
{
    if (isEmpty(Q))
    {
        printf("Queue is empty!\n");
        return NULL; // 반환 값을 수정
    }
    return Q->queue[Q->front++];
}


void levelorder(TreeNode *root)
{
    QueueType *Q = (QueueType *)malloc(sizeof(QueueType)); 
    //포인터 쓸 때, 꼭 할당하기
    init(Q);

    enqueue(Q, root);

    while(!isEmpty(Q))
    {
        root = dequeue(Q);
        printf("[%d] ", root->data);

        if(root->left != NULL)
            enqueue(Q, root->left);

        if(root->right != NULL)
            enqueue(Q, root->right);
    }
    free(Q);
}

int main()
{
    TreeNode N4 = {1, NULL, NULL};
    TreeNode N5 = {16, NULL, NULL};
    TreeNode N6 = {25, NULL, NULL};
    TreeNode N3 = {20, &N5, &N6};
    TreeNode N2 = {4, &N4, NULL};
    TreeNode N1 = {15, &N2, &N3};

    TreeNode *root = &N1;

    levelorder(root);

    return 0;
}

<실행 결과>
[15] [4] [20] [1] [16] [25]

1.7 수식 트리

비단말노드 : 연산자
단말노드 : 피연산자

후위연산을 이용한다

1.8 이진 트리 연산

1.8.1 노드 개수

int getcount(TreeNode *node)
{
    int count = 0;
    if(node != NULL)
    count = 1 + getcount(node->left) + getcount(node->right);

    return count;
}

1.8.2 높이

#define Max(a,b) a > b ? a : b

int getHeight(TreeNode *node)
{
    int height = 0;

    if(node != NULL)
    {
        height = 1+ Max(getHeight(node->left), getHeight(node->right));
        return height;    
    }
}

1.9 스레드 이진 트리

이진트리의 NULL 링크를 이용하여 순환 호출 없이도 노드를 순회
NULL링크의 중위 순회시에 후속 노드인 중위 후속자를 저장시켜 놓은 트리가 스레드 이진 트리

즉, 외부 스택이 아닌 포인터로 순회하는 트리

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

#define TRUE 1
#define FALSE 0

typedef struct TreeNode
{
    char data;
    struct TreeNode *left, *right;
    int isthread; 
    // 오른쪽 링크가 스레드이면 TRUE, 스레드는 단말 노드에만 적용
} TreeNode;

TreeNode *find(TreeNode *p)
{
    TreeNode *q = p->right;
    if (q == NULL || p->isthread == TRUE)
        return q;
    while (q->left != NULL)
        q = q->left;
    return q;
}

void inorder(TreeNode *t)
{
    TreeNode *q = t;
    while (q->left)
        q = q->left;
    do
    {
        printf("[%c] ", q->data);
        q = find(q);
    } while (q);
}

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 *root = &n7;

int main()
{
    n1.right = &n3;
    n2.right = &n7;
    n4.right = &n6; 

    inorder(root);
}

1.10 이진 탐색 트리

key(왼쪽) <= key(루트) <= key(오른쪽)
이진탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

1.10.1 탐색연산

비교 결과가 같으면 탐색 성공

비교 결과가, 주어진 키값이 루트 노드의 키값보다 작으면 
루트 노드의 왼쪽 자식을 기준으로 다시 시작

비교 결과가, 주어진 키값이 루트 노드의 키값보다 크면
루트 노드의 오른쪽 자식을 기준으로 다시 시작

// 순환적인 방법
TreeNode *search(TreeNode *root, int key)
{
    if (root == NULL)
        return NULL;
    if (key == root->key)
        return root;

    else if (key < root->key)
        return search(root->left, key);
    else
        return search(root->right, key);
}

// 반복적인 방법
TreeNode *search2(TreeNode *root, int key)
{
    while (1)
    {

        if (root == NULL)
            return NULL;
        if (key == root->key)
            return root;

        else if (key < root->key)
            root = root->left;
        else
            root = root->right;
    }
}

1.10.2 삽입연산

탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치

TreeNode *newnode(int key)
{
    TreeNode *temp = (TreeNode *)malloc(sizeof(TreeNode));
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

TreeNode *insert(TreeNode *root, int key)
{
    if (root == NULL)
        return root = newnode(key);

    if (key < root->key)
        root->left = insert(root->left, key);
    else if(key > root->key)
        root->right = insert(root->right, key);

    return root;
}

1.10.3 삭제연산

case 1. 삭제 노드가 단말 노드
case 2. 삭제 노드가 한 개의 서브 트리를 가짐
case 3. 삭제 노드가 두 개의 서브 트리를 가짐

case 3 : 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제 노드 위치로
가장 비슷한 값 : 왼쪽 서브 트리의 최대 || 오른쪽 서브 트리의 최소

// 오른쪽 서브 트리의 최소 구하기
TreeNode *min(TreeNode *node)
{
    TreeNode *current = node;

    while(current->left != NULL)
        current= current->left; //왼쪽으로 갈수록 최소
    return current;
}

TreeNode *delete(TreeNode *root, int key)
{
    if (root == NULL)
        return root; //존재하지 않는다.

    if (key < root->key)
        root->left = delete(root->left, key);

    else if (key > root->key)
        root->right = delete(root->right, key);

    else // key == root->key
    {
        //case.2
        if (root->left == NULL)
        {
            TreeNode *temp = root->right;
            return root = temp;
        }
        else if (root->right == NULL)
        {
            TreeNode *temp = root->left;
            return root = temp;
        }
        //case.3
        TreeNode *temp = min(root->right); //오른쪽 서브트리의 최소
        root->key = temp->key; // key 값 갈아끼우기
        root->right = delete(root->right, temp->key); 
        // 오른쪽 서브트리에서 해당값 삭제
    }

    return root;
}

1.10.3 성능분석

연산 시간의 복잡도는 트리의 높이(h)에 비례한다