서리 개인 개발 블로그

트리

- 비선형 자료구조의 일종이다.

- 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다.

  ※ 사용 예로 컴퓨터의 디렉터리 구조를 들 수 있다.

용어 정리

1. 노드(Node) : 트리의 구성요소에 해당하는 요소.

2. 간선(Edge) : 노드와 노드를 연결하는 연결선.

3. 루트 노드(Root node) : 트리 구조에서 최상위에 존재하는 노드.

4. 단말 노드(Leaf node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드.

5. 내부 노드(Internal node) : 단말 노드를 제외한 모든 노드.

6. 형제 노드(Sibling node) : 같은 부모를 가지는 노드.

이진 트리(Binary tree)

- 노드의 자식 수가 2 이하인 트리

포화 이진 트리(Full binary tree)

- 단말 노드를 제외한 모든 노드가 2개의 자식을 가진 트리

이진 탐색 트리(Binary search tree)

- 이진 탐색 트리는 이진 탐색과 이진 트리를 결합한 자료구조이다.

- 이진 탐색 트리는 다음과 같은 속성을 갖기 때문에 효율적인 탐색이 가능하다.

  1. 중복된 값을 혀용하지 않는다. (하지만 일부에서는 중복된 값을 혀용하는 경우도 있다.)

  2. 왼쪽 서브트리의 키들은 부모 노드의 키보다 작다.

  3. 오른쪽 서브트리의 키들은 부모 노드의 키보다 크다.

  4. 양쪽 서브트리는 그 자체로 이진 탐색 트리이다.

- 위와 같은 특징 때문에 탐색 연산은 O(log₂n)의 시간복잡도를 가진다.

트리 순회(Tree traversal)

- 트리의 순회는 전위 순회, 중위 순회, 후위 순회 세 가지가 있다.

  ※ 순회에서 중요한 부분은 자식 노드를 좌, 우 순서로 출력된다고 생각하면 된다.

- 전위 순회(PreOrder) : Root 노드부터 시작된다.

- 중위 순회(InOrder) : Root 노드가 중간에 위치한다.

- 후위 순회(PostOrder) : Root 노드가 마지막에 위치한다.

전위 순회

- Root 노드가 제일 먼저 순회가 시작되고 자식 노드의 좌, 우 순서로 순회가 이루어진다

- 즉, 탐색 순서는 A → B → D → E → C → F → G가 된다.

중위 순회

- 왼쪽 자식노드, Root 노드, 오른쪽 자식노드 순으로 순회가 이루어진다.

- 즉, 순회 순서는 D → B → E → A → F → C → G가 된다.

후위 순회

- 왼쪽 자식노드, 오른쪽 자식노드, Root 노드 순으로 순회가 이루어진다.

- 즉, 순회 순서는 D → E → B → F → G → C → A가 된다.

  ※ 어렵게 생각할 필요없이 자식 노드는 무조건 오른쪽 왼쪽 순으로 순회가 되고, 전위냐 중위냐 후위냐에 따라 Root 노드가 자식 노드들의 앞, 중간, 뒤에 위치한다고 생각하면 편하다.

큐

- 선형 자료구조의 일종이다.

- 먼저 들어간 것이 먼저 나오는 선입선출(FIFO : First In First Out)형식의 자료구조이다.

  ※ 사용 예로 번호표 시스템을 들 수 있다.

  ※ 들어간 순서대로 나오므로 위 그림 기준으로 오른쪽에 데이터가 입력이 되고, 왼쪽 데이터부터 출력이 이루어진다.

큐를 작성할 코드에 활용할 구조체는 다음과 같다.

typedef struct Queue
{
    int data;
    struct Queue* NEXT;
}Queue;

Enqueue(입력)

void Enqueue(Queue** front, Queue** rear, int data)
{
    Queue* newNode = (Queue*)malloc(sizeof(Queue));
    newNode->data = data;
    newNode->NEXT = NULL;
    
    if(*front == NULL)
    {
        *front = newNode;
        *rear = newNode;
    }
    else
    {
        (*rear)->NEXT = newNode;
        *rear = newNode;
    }
}

  ※ Stack과는 다르게 연결리스트의 첫 노드와 마지막 노드를 참조할 변수를 인수로 받아 값을 넣어준다.

  ※ 결과적으로 Queue의 데이터가 1개일때는 front와 rear가 같은 노드를 참조하게되고, 2개 이상이 되면 rear는 마지막 노드를 참조하게 된다.

Dequeue(출력)

void Dequeue(Queue** front, Queue** rear)
{
    if(*front == NULL) return;
    
    printf("%d ", (*front)->data);
    
    Queue* deleteNode = *front;
    *front = (*front)->NEXT;
    if(*front == NULL)
        *rear = NULL;
    
    free(deleteNode);
}

  ※ 데이터를 출력하고 front가 참조하고 있는 노드를 할당 해제해준다.

  ※ front가 NULL이면 Queue에 더이상 데이터가 없는것이므로 rear의 참조도 NULL로 밀어준다.

위 과정을 그림으로 보면 다음과 같다.

  ※ 첫 노드는 front, 제일 마지막 노드는 rear가된다.

  ※ Enqueue : 새 데이터를 입력하면 Enqueue함수에서 노드를 동적할당하고 rear에 새로 할당한 노드를 참조해준다.

  ※ Dequeue : front가 참조하고 있는 데이터를 출력하고 front의 참조를 다음 노드로 변경해준다.

풀 소스코드는 다음과 같다.

#include <stdio.h>
#define MAX 10

typedef struct Queue
{
    int data;
    struct Queue* NEXT;
}Queue;

void Enqueue(Queue** front, Queue** rear, int data)
{
    Queue* newNode = (Queue*)malloc(sizeof(Queue));
    newNode->data = data;
    newNode->NEXT = NULL;
    
    if(*front == NULL)
    {
        *front = newNode;
        *rear = newNode;
    }
    else
    {
        (*rear)->NEXT = newNode;
        *rear = newNode;
    }
}

void Dequeue(Queue** front, Queue** rear)
{
    if(*front == NULL) return;
    
    printf("%d ", (*front)->data);
    
    Queue* deleteNode = *front;
    *front = (*front)->NEXT;
    if(*front == NULL)
        *rear = NULL;
    
    free(deleteNode);
}

void main()
{
    Queue* front = NULL, * rear = NULL;
    for(int i = 0; i < MAX; i++)
        Enqueue(&front, &rear, i);
        
    //현재 상태 : 0(front), 1, 2, 3, 4, 5, 6, 7, 8, 9(rear)
    
    for(int i = 0; i < MAX; i++)
        Dequeue(&front, &rear);
        
    //결과 : 0 1 2 3 4 5 6 7 8 9
}

스택

- 선형 자료구조의 일종이다.

- 들어간 것이 먼저 나오는 후입선출(LIFO : Last In First Out)형식의 자료구조이다.

  ※ 사용 예로 브라우저의 뒤로가기 기능을 들 수 있다.

  ※ 위의 그림 기준으로 입력의 순서는 A → D → C, 출력은 C → D → A 순으로 이루어진다.

그럼 본격적으로 코드를 작성하기 전 활용할 구조체는 다음과 같다.

typedef struct Stack
{
    int data;
    struct Stack* NEXT;
}Stack;

Push (입력)

Stack* Push(Stack* node, int data)
{
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->NEXT = node;
	
    return newNode;
}

  ※ 새로 할당한 노드의 자기참조 변수는 앞에 만들어진 노드(인수로 받은 노드)를 대입하면 된다.

Pop(출력)

Stack* Pop(Stack* node)
{
    if (node == NULL) return NULL;
	
    Stack* deleteNode = node;
    node = node->NEXT;
    free(deleteNode);
	
    return node;
}

  ※ 현재(Top)의 노드를 할당해제하고 인수로 받은 노드의 다음 노드를 반환한다.

위 과정을 그림으로 풀면 다음과 같다.

  ※ 제일 마지막에 Push된 데이터가 스택의 Top이 된다.

  ※ Push :  현재 Top(Stack3)을 인수로 넘겨주면 Push함수에서 노드를 동적할당하고 Stack->NEXT에 인수로 받은 Stack3을 대입해주고 반환해주면, Top은 새로 할당한 노드로 변경이 되고 기존 노드(Stack3)은 새로 할당한 노드의 참조 변수(NEXT)에 대입해주면 된다.

  ※ Pop : 현재 Top을 인수로 넘겨주면 되고, Pop함수에서 인수로 받은 Top 노드를 할당 해제 해주고, Top노드의 참조 변수(NEXT)를 반환해주면 된다.

풀 소스코드는 다음과 같다.

#include <stdio.h>
#define MAX 10

typedef struct Stack
{
    int data;
    struct Stack* NEXT;
}Stack;

Stack* Push(Stack* node, int data)
{
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->NEXT = node;
	
    return newNode;
}

Stack* Pop(Stack* node)
{
    if (node == NULL)
    {
        printf("데이터가 없습니다.\n");
        return NULL;
    }
	
    printf("%d ", node->n);
    Stack* deleteNode = node;
    node = node->NEXT;
    free(deleteNode);
	
    return node;
}

void main()
{
    Stack* top = NULL;
    for(int i = 0; i < MAX; i++)
        top = Push(top, data);
    
    //현재 상태 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9(top)
    
    for(int i = 0; i < MAX; i++)
    	top = Pop(top);
        
    //결과 : 9 8 7 6 5 4 3 2 1 0
}

연결리스트

- 추상적 자료형인 리스트를 구현한 자료구조로 노드(데이터 덩어리)를 저장할 때 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 자료구조이다.

  ※ 그렇기때문에 구조체 멤머변수 중 자신과 동일한 구조체의 주소를 저장할 수 있는 변수를 만들어 참조해야한다. (이 때, 주소를 저장하는 멤버 변수를 자기참조 구조체라고 함.)

- 장점 : 배열과 다르게 데이터를 동적으로 추가, 삭제가 가능하다.

- 단점 : 배열처럼 정렬되어있지 않고, 흩어져있기 때문에 배열의 인덱스로 접근하는것 처럼 특정 노드에 빠른 접근은 불가능하다.

  ※ 일일이 탐색하는 과정을 거쳐서 데이터를 찾아야 한다.

Linked List를 위한 구조체

typedef struct Node
{
    int data
    struct Node* Next;
}Node;

위의 구조체를 바탕으로 우리가 구현할 연결리스트의 그림을 그려보자면 다음과 같이 표현할 수 있다.

추가

- 가장 마지막 노드를 찾아 그 뒤에 데이터를 추가한다.

1. 재귀함수를 통해 마지막 노드까지 찾아간다.

2. 새로운 데이터를 동적할당을 한 뒤, 마지막 노드에 연결해준다.

Node* AddData(Node* node, int data)
{
    if (node == NULL)
    {
    	Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->NEXT = NULL;

        return newNode;
    }

    node->NEXT = AddData(node->NEXT, data);
    return node;
}

탐색

- 이부분 역시 재귀함수로 데이터를 비교해서 같은 노드를 반환하면 된다.

Node* Search(Node* node, int data)
{
    if (node == NULL)
        return NULL;
	
    if (node->data == data)
        return node;

    return Search(node->NEXT, data);
}

삭제

1. 재귀함수로 데이터가 같은 노드를 찾는다.

2. 같은 노드를 찾으면 찾은 노드에 연결된 리스트를 임시 변수에 저장해둔다.

3. 찾은 노드의 동적할당을 해제한다.

4. 2번에 저장해둔 다음 리스트를 반환한다.

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (node->data == data)
    {
        Node* nextNode = node->NEXT;
        free(node);
		
        return nextNode;
    }
	
    node->NEXT = Delete(node->NEXT, data);
    return node;
}

여기까지만 구현해 두면, 어느 특정 위치에 데이터를 끼워넣든 삭제하든 나머지는 응용하기 나름이다.

마지막으로 풀 소스 코드를 올려본다.

#include <stdio.h>
#define MAX 10

typedef struct Node
{
    int data;
    struct Node* NEXT;
}Node;

Node* AddData(Node* node, int data)
{
    if (node == NULL)
    {
    	Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->NEXT = NULL;

        return newNode;
    }

    node->NEXT = AddData(node->NEXT, data);
    return node;
}

void ShowAllData(Node* node)
{
    if (node == NULL) return;

    printf("%d ", node->data);
    ShowAllData(node->NEXT);
}

Node* Search(Node* node, int data)
{
    if (node == NULL)
        return NULL;
	
    if (node->data == data)
        return node;

    return Search(node->NEXT, data);
}

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (node->data == data)
    {
        Node* nextNode = node->NEXT;
        free(node);
		
        return nextNode;
    }
	
    node->NEXT = Delete(node->NEXT, data);
    return node;
}

void main()
{
    Node* head = NULL;
    //데이터 추가
    for(int i = 0; i < MAX; i++)
        head = AddData(head, i);
    ShowAllData(head);
    
    //결과 : 0 1 2 3 4 5 6 7 8 9
    
    //탐샋
    Node* someNode = Search(head, 5);
    if(someNode != NULL)
        printf("%d\n", someNode->data);
        
    //결과 : 5
    
    //삭제
    head = Delete(head, 8);
    ShowAllData(head);
    //결과 : 0 1 2 3 4 5 6 7 9
}