트리

양규빈·2024년 2월 27일

목록 보기

5/6

트리란?

계층적인 구조를 나타내는 자료 구조로, 노드(node)들이 간선(edge)으로 연결되어 있는 형태를 말합니다.

트리는 하나의 루트(root) 노드로부터 시작하여 여러 개의 자식(child) 노드를 가질 수 있으며, 각 자식 노드 또한 자신의 자식 노드를 가질 수 있습니다.
각 노드는 부모-자식 관계로 서로 연결되어 있으며, 루트 노드는 부모가 없는 최상위 노드입니다.

트리의 특징은 아래와 같습니다.

일반적으로 루트 노드는 1개만 존재한다.

루트 노드를 제외한 나머지 객체들에 대해서는 1개의 부모노드와 0개 이상 다수의 자식 노드 객체들이 존재한다.

객체들은 부분적으로 순서화할 수 있지만, 모든 객체들이 반드시 일렬로 순서화 되는 것은 아니다.

부모 객체이면서 자식 객체가 되는 경우는 없다.

트리 특징

노드 차수(Node Degree)는 트리의 노드가 가지는 자식의 개수를 말합니다. 이진 트리에서는 각 노드의 차수가 최대 2입니다. 다른 종류의 트리에서는 차수에 제한이 없을 수 있습니다.
트리 차수(Tree Degree)는 트리 내에서 가장 큰 노드 차수를 말합니다. 만약 트리가 이진 트리라면 트리 차수는 2가 됩니다.
노드 레벨(Node Level)은 트리에서 특정 노드의 깊이(Depth)를 나타냅니다. 루트 노드의 레벨은 일반적으로 0으로 시작하며, 아래로 내려갈수록 1씩 증가합니다. 예를 들어, 루트 노드의 레벨은 0이며, 그 아래의 자식 노드들의 레벨은 1, 그 아래의 자식 노드들의 레벨은 2, 이와 같이 증가합니다.
트리 깊이(Tree Depth)는 트리에서 가장 깊은 레벨을 말합니다. 즉, 트리 내에서 가장 깊은 노드의 레벨 값입니다. 트리 깊이는 트리의 높이(Height)와도 동일한 의미를 갖습니다.

이진 트리란?

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식을 가지는 트리 구조를 말합니다.

루트 노드(Root Node): 트리의 시작점이며, 다른 모든 노드는 루트 노드에서 시작하는 경로에 속합니다.

부모 노드(Parent Node)와 자식 노드(Child Node): 부모 노드는 자식 노드를 가리키는 엣지로 연결되어 있습니다. 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.

이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 한 종류로, 왼쪽 서브트리의 모든 노드가 현재 노드보다 작고 오른쪽 서브트리의 모든 노드가 현재 노드보다 큰 값을 가집니다. 이진 탐색 트리는 탐색, 삽입, 삭제 연산을 빠르게 수행할 수 있습니다.

포화 이진 트리(Full Binary Tree)

: 모든 내부 노드가 두 개의 자식을 가지는 이진 트리를 말합니다.
이러한 트리는 모든 레벨이 꽉 차 있어서 높이가 최소이며, 각 레벨의 노드 수는 2의 거듭제곱 형태로 증가합니다.

완전 이진 트리(Complete Binary Tree)

:마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들이 왼쪽부터 순서대로 채워져 있는 이진 트리를 말합니다

부모 노드 구하기

노드 인덱스가 0이 아닐 때 (즉, 루트 노드가 아닐 때):

부모 노드의 인덱스 = (i - 1) / 2

루트 노드일 때 = 부모 노드가 없으므로 정의되지 않음

자식 노드 구하기

왼쪽 자식 노드의 인덱스 = 2 * i

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

트리의 순회

전위 순회

루트 노드를 먼저 방문하고, 왼쪽 서브트리를 전위 순회한 후에 오른쪽 서브트리를 전위 순회합니다.

노드 방문 순서: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

중위 순회

왼쪽 서브트리를 중위 순회한 후에 루트 노드를 방문하고, 오른쪽 서브트리를 중위 순회합니다.

노드 방문 순서: 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

후위 순회

왼쪽 서브트리를 후위 순회한 후에 오른쪽 서브트리를 후위 순회하고, 마지막으로 루트 노드를 방문합니다.

노드 방문 순서: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

코드 구현

문제 링크

트리를 입력 받아서, 순회를 구현하는 문제입니다.
전위 순회와 중위 순회, 후위 순회는 각각 재귀함수를 이용해서 구현합니다.

preOrder는 전위 순회로서, 먼저 현재 방문 노드를 출력하고 재귀함수를 호출해, 다음 노드로 이동합니다.
midOrder는 중위 순회로서, 노드 방문 후, 현재 노드 출력. 그리고 다음 노드를 방문합니다.
postOrder는 후위 순회로서, 노드들을 재귀함수로 먼저 호출한 후에, 현재 방문 노드를 출력합니다.

#include <iostream>
#include <vector>

using namespace std;
void preOrder(int node, int tree[][2]);
void midOrder(int node, int tree[][2]);
void postOrder(int node, int tree[][2]);

int main()
{
    int nodes;
    int tree[26][2];
    vector<bool> visited;
    
    cin >> nodes;
    
    visited.resize(nodes);
    fill(visited.begin(), visited.end(), false);
    
    for(int i=0; i< nodes; i++)
    {
        char my;
        char leftChild;
        char rightChild;
        cin >> my >> leftChild >> rightChild;
        
        int node = my -'A';
        
        if(leftChild == '.')
            tree[node][0] = -1;
        else
            tree[node][0] = leftChild - 'A';
        
        if(rightChild == '.')
            tree[node][1] = -1;
        else
            tree[node][1] = rightChild - 'A';
    }
    
    preOrder(0, tree);
    cout<<"\n";
    midOrder(0, tree);
    cout<<"\n";
    postOrder(0, tree);
    cout<<"\n";
}

void preOrder(int node, int tree[][2])
{
    if(node == -1)
        return;
    
    cout << (char)(node + 'A');
    preOrder(tree[node][0], tree);
    preOrder(tree[node][1], tree);
}

void midOrder(int node, int tree[][2])
{
    if(node == -1)
        return;
    
    midOrder(tree[node][0], tree);
    cout << (char)(node + 'A');
    midOrder(tree[node][1], tree);
}

void postOrder(int node, int tree[][2])
{
    if(node == -1)
        return;
    
    postOrder(tree[node][0], tree);
    postOrder(tree[node][1], tree);
    cout << (char)(node + 'A');
}