[C언어]46일차 - 트리 (이것이 c언어 자료구조 알고리즘이다)

 

학습 개념

1.트리의 개념 이해하기

2.트리를 표현하는 여러가지 방식 이해하기

 

3.이진트리의 개념과 구현 이해하기

4.수식 트리의 개념과 구현 이해하기

5.분리집합의 개념과 구현 이해하기

 

 

트리의 개념

트리 구조는 컴퓨터 과학에서도 활용도가 매우 높다. 

 

운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM도 트리 구조로 이루어져 있다.

또한 검색 엔진이나 데이터베이스도 트리 자료구조에 기반해서 구현된다.

 

*검색 엔진이나 데이터베이스에 사용되는 트리 자료구조를 탐색 트리라고 한다.

 

 

트리의 구성요소

트리는 뿌리, 가지, 잎 세가지 요소로 이루어져 있습니다.

 

 

뿌리는 트리 자료구조의 가장 위에 있는 노드를 가리킨다.

가지는 뿌리와 잎 사이에 있는 모든 노드를 일컫는다.

가지 끝에 매달린 노드를 잎이라고 부른다.(단말 노드라고 하기도 한다.)

 

아래 그림에서 노드 B, C, D를 보면 B에서 C와 D가 뻗어 나와 있다.

 

B:  C, D의 부모이다.

 

C, D : B의 자식

 

C,D는 한 부모 밑에서 태어난 형제라고 한다.

 

 

한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서를 일컬어 경로라고 부른다.

 

B노드에서 F노드를 찾아 간다고 하면

B노드에서 출발하여 D노드를 방문하고 D에서 출발하여 F에 도착한다.

 

이때 B, D, F를 B에서 F까지의 경로라고 한다.

 

B, D, F 경로의 길이는 2가 된다.

 

 

노드의 깊이는 뿌리 노드에서 해당 노드까지 이르는 경로의 길이를 뜻한다.

 

레벨은 깊이가 같은 노드의 집합을 일컫는 말이다.

레벨 2라고 하면 C, D, H, J 노드 전체를 가리킨다.

 

 

노드의 차수는 그 노드의 자식 노드 개수를 뜻한다.

 

트리의 차수는 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수를 말한다.

 

 

트리의 표현방법

 

1.중첩된 괄호 표현법 - 같은 레벨의 노드들을 괄호로 함께 묶어 표현하는 방법

이 방법은 읽기는 다소 어렵지만 트리를 하나의 공식처럼 표현 할 수 있다는 장점이 있다.

 

 

 

2.중첩된 집합으로 트리를 표현하기 - 트리가 하위 트리의 집합이라는 사실을 잘 표현 할 수 있다는 장점이 있다.

 

 

 

3.들여쓰기 트리 - 자료의 계층적인 특징을 잘 나타낸다.

 

 

 

 

노드의 표현 방법

노드표현 방법은 부모와 자식, 형제 노드를 서로 연결 짓는 방법이라고 할 수 있다.

표현 방법에는 두가지가 있다. 하나는 N-링크 표현방법이고, 하나는 왼쪽 자식 - 오른쪽 형제 표현법이다.

 

 

N-링크 표현방법

 

N-링크는 노드의 차수가 N이라면 노드가 N개의 링크를 갖고 있는데, 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법이다.

 

N-링크로 트리를 표현하면 아래와 같은 모습이 된다.

 

이 노드 표현법은 차수(자식 노드의 수)가 노드마다 달라지는 트리에는 적용하기 힘들다는 단점이 있다.

 

예) 폴더 트리 같은 경우 폴더의 차수가 0일 수도 있고, 수백, 수천이 될 수도 있다.

 

 

왼쪽자식 - 오른쪽 형제 표현법

 

이 표현법은 왼쪽 자식과 오른쪽 형제에 대한 포인터만을 갖도록 노드를 구성하는 방법이다.

 

이 표현법을 사용하면 N개의 차수를 가진 노드의 표현이 오로지 2개의 포인터 (왼쪽 자식 포인터와 오른쪽 형제 포인터)만으로 가능하게 된다.

 

 

 

트리 구조와 관계 확인

• a가 루트 노드라는 점, 맞습니다.
• a의 자식은 b, c, d 세 노드로, b와 c와 d는 모두 a의 자식이면서 서로 형제(시블링) 노드입니다.
• b의 자식은 e 하나이며, e는 형제가 없습니다.
• d의 자식은 f와 g이며, f와 g는 서로 형제입니다.
• e, f, g는 더 이상 자식이 없으므로 잎(leaf) 노드라는 표현도 맞습니다.

추가 설명

이 그림은 트리의 "왼쪽-자식 오른쪽-형제(left-child right-sibling)" 방식으로 표현된 트리입니다. 즉, 각 노드는 자신의 첫 번째 자식과 오른쪽 형제만 기억합니다. 이렇게 하면 임의의 다차수 트리를 이진트리처럼 구현할 수 있습니다

 

 

이 표현법을 사용하는 트리에서 어느 한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 된다.

해당 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻은 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 얻고, 그 다음 오른쪽 형제 노드의 주소를 계속해서 얻어나가면 결국에는 모든 자식 노드를 얻을 수 있다.

 

 

트리의 기본 연산 - 노드를 생성하고 부모와 자식 노드를 연결하는 코드

 

노드 선언

 

 

노드 생성 

 

이 함수는 malloc() 함수를 이용하여 LCRSNode 구조체의 크기만큼 자유 저장소에 메모리를 할당하고 매개 변수 NewData를 Data에 저장한 후 노드의 메모리 주소를 반환한다.

 

 

 

노드 소멸

 

 

자식 노드 연결

 

LCRS_AddChildNode() 함수는 부모 노드와 이 부모 노드에 연결할 자식 노드를 매개 변수로 받는다.

 

이 함수는 먼저 부모 노드인 Parent에게 자식 노드가 있는지 검사한다.

 

Parent에 몇 개의 자식 노드가 있는지 단번에 알아낼 수 있는 방법은 없지만, 일단 LeftChild가 NULL인 것을 확인하면 자식이 하나도 없다는 사실 정도는 알 수 있다.

 

만약 Parent에게 자식 노드가 하나도 없다면 Parent의 LeftChild 포인터에 자식 노드 주소를 바로 저장하면 된다.

 

 

 

Parent의 LeftChild가 NULL이 아닌 경우 자식 노드를 하나 이상 갖고 있다는 의미이다.

 

이럴 때는 자식 노드의 RightSibling 포인터를 이용해서 가장 오른쪽에 있는 자식 노드 (RightSibling이 NULL인 노드)를 찾아내고, 이렇게 찾아낸 가장 오른쪽 자식 노드의 RightSibling에 Child를 대입한다. 

 

이렇게 하면 Parent는 새로운 자식을 하나 더 얻게 된다.

 

 

 

트리 출력

제일 앞에 나오는 for 루프가 매개 변수로 입력된 depth(깊이) -1 만큼 공백을 3칸씩 출력한다.

 

공백 마지막에는 해당 노드가 누군가의 자식 노드임을 나타내는 +-- 를 덧붙인 후 노드의 데이터를 출력한다.

 

이렇게 하면 깊이가 0인 뿌리 노드는 제일 앞쪽에 출력되고 잎 노드는 제일 뒤쪽 (깊은곳)에 출력된다.

 

 

 

전체 코드

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

#define ElementType char


//MARK: 노드 구조체
typedef struct tagLCRSNode
{
    struct tagLCRSNode* LeftChild;
    struct tagLCRSNode* RightSibling;
    ElementType Data;
} LCRSNode;



//MARK: 노드 생성
LCRSNode* createNode(ElementType NewData){
        
    //malloc 함수를 이용해서 LCRSNode 구조체 크기 만큼 자유 저장소에 메모리를 할당한다.
    LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
    NewNode->LeftChild = NULL;
    NewNode->RightSibling = NULL;
    NewNode->Data = NewData;
    return NewNode;
};


//MARK: 노드 소멸
void destroyNode(LCRSNode* Node){
    free(Node);
}

//MARK: 트리 소멸
void destroyTree(LCRSNode* Root){
    
    if (Root->RightSibling != NULL) {
        destroyTree(Root->RightSibling);
    }
    
    if (Root->LeftChild != NULL) {
        destroyTree(Root->LeftChild);
    }
    
    Root->LeftChild = NULL;
    Root->RightSibling = NULL;
    
    destroyNode(Root);
    
}


//MARK: 노드 연결
void addChildNode(LCRSNode* Parent, LCRSNode* Child){
    
    //LeftChild가 Null이면 자식이 없다는 뜻
    if (Parent->LeftChild == NULL) {
        Parent->LeftChild = Child;
        
        
    }else{
        //자식 노드를 하나 이상 갖고 있다는 의미
        //RightSibling 포인터를 이용해서
        //가장 오른쪽에 있는 자식 노드(RightSibling이 NULL인 노드)를 찾아내고,
        //이렇게 찾아낸 가장 오른쪽 노드의 RightSibling에 Child를 대입한다.
        
        LCRSNode* temp = Parent->LeftChild;
        
        while (temp->RightSibling != NULL) {
            temp = temp->RightSibling;
        }
        
        //temp: 가장 오른쪽에 있는 노드
        temp->RightSibling = Child;
    }
}

//MARK: 트리출력
void printTree(LCRSNode* Node, int Depth){
   
    //들여쓰기
    //깊이가 0인 뿌리 노드는 제일 앞쪽에 출력되고 , 잎 노드는 제일 뒤쪽에 출력된다.
    int i = 0;
    for (i = 0; i < Depth - 1; i++) {
        printf("   ");
    }
    
    if (Depth > 0) {
        printf("+--");
    }
    
    printf("%c\n" , Node->Data);
    
    if (Node->LeftChild != NULL) {
        printTree(Node->LeftChild, Depth+1);
    }
    
    if (Node->RightSibling != NULL) {
        printTree(Node->RightSibling, Depth);
    }
}



//MARK: main
int main(int argc, const char * argv[]) {
       
    LCRSNode* Root = createNode('A');
    LCRSNode* B = createNode('B');
    LCRSNode* C = createNode('C');
    LCRSNode* D = createNode('D');
    LCRSNode* E = createNode('E');
    LCRSNode* F = createNode('F');
    LCRSNode* G = createNode('G');
    LCRSNode* H = createNode('H');
    LCRSNode* I = createNode('I');
    LCRSNode* J = createNode('J');
    LCRSNode* K = createNode('K');

    //트리에 노드 추가
    
    addChildNode(Root, B);
        addChildNode(B, C);
        addChildNode(B, D);
            addChildNode(D, E);
            addChildNode(D, F);
    
    
    addChildNode(Root, G);
        addChildNode(G, H);
    
    
    addChildNode(Root, I);
        addChildNode(I, J);
            addChildNode(J, K);
    
    printTree(Root, 0);
    
    return 0;
}

 

 

A
+--B
   +--C
   +--D
      +--E
      +--F
+--G
   +--H
+--I
   +--J
      +--K