본문 바로가기

자료구조/트리(Tree)

[자료구조] 트리(Tree) - 코딩밥상

트리의 개념

트리는 이름 그대로 나무를 닮은 자료구조입니다. 뿌리가 있고 뿌리에는 가지가 뻗어 나오며 가지 끝에는 잎이 달립니다.

이러한 구조는 우리들의 일상생활 뿐만 아니라 컴퓨터 과학에서도 활용도가 매우 높습니다. 운영체제의 파일 시스템과 문서를 다룰 때 사용하는 DOM등이 트리 구조로 이루어져 있습니다. 또한 검색 엔진이나 데이터베이스도 트리 자료구조에 기반해서 구현됩니다.


트리 구조의 용어 정리

 

-구성요소

트리는 뿌리(Root),가지(Branch),잎(Leaf) 세 가지 요소로 이루어져 있습니다. 모두 또같은 노드이지만 트리에서 어디에 위치하는가에 따라 불리는 이름이 달라질 뿐입니다. 가장 위에 있는 노드가 뿌리, 뿌리와 잎 사이에 있는 모든 노드가 가지 그리고 끝에 매달린 노드를 잎이라고 부릅니다. 잎 노드는 끝에 있다고 해서 단말(Terminal)노드라고 부르기도 합니다.

-구성요소 간 관계

연결된 트리 구조에서 상단 노드와 하단 노드의 관계를 부모(Parent)노드와 자식(Children)노드로 정의합니다. 그리고 같은 노드를 부모 노드로 갖는 노드들을 서로 형제(Sibling)노드라고 정의합니다. 이외의 기본적인 용어 정리를 하자면

  • 경로(Path) : 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서
  • 깊이(Depth) : 뿌리 노드에서 해당 노드까지 이르는 경로의 길이
  • 레벨(Level) : 깊이가 같은 노드의 집합
  • 높이(Height) : 가장 깊은 곳에  있는 잎 노드까지의 깊이
  • 차수(Degree) : 해당 노드의 자식 노드의 개수, 트리의 차수는 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수

트리 구현하기

단, 해당 트리는 왼쪽 노드는 자식노드, 오른쪽 노드는 형제 노드 입니다.

-노드 선언

typedef char ElementType;

typedef struct tagLCRSNode{
    struct tagLCRSNode* LeftChild;
    struct tagLCRSNode* RightSibling;
    
    ElementType Data;
} LCRSNode;

-노드 생성/소멸 연산

LCRSNode* LCRS_CreateNode(ElementType NewData){
    LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
    NewNode->LeftChild = NULL;
    NewNode->RightSibling = NULL;
    NewNode->Data = NewData;
    
    return NewNode;
}

void LCRS_DestroyNode(LCRSNode* Node){
    free(Node);
}

Heap 공간에 노드 할당과 해제

-자식 노드 연결

void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child){
    if(Parent->LeftChild == NULL){
        Parent->LeftChild = Child;
    }
    else{
        LCRSNode* TempNode = Parent->LeftChild;
        while(TempNode->RightSibling != NULL){
            TempNode = TempNode->RightSibling;
        }
        
        TempNode->RightSibling = Child;
    }
}

부모노드의 Child노드가 비어있다면, 그대로 연결

비어있지 않다면 최우측 형제노드에 연결

-트리 출력

void LCRS_PrintTree(LCRSNode* Node, int Depth){
    cout<<Node->Data;
    
    if(Node->LeftChild != NULL){
        LCRS_PrintTree(Node->LeftChild, Depth+1);
    }
    if(Node->RightSibling != NULL){
        LCRS_PrintTree(Node->RightSibling, Depth);
    }
}