트리

트리

트리는 그래프의 일종. 허나 사이클이 없다.

트리는 하나의 루트 노드를 가진다.

루트 노드는 0개 이상의 자식 노드를 가지고 있다.

자식 노드는 0개 이상의 자식 노드를 가지고 있다. 이는 반복된다.

--

이진 트리는 각 노드가 최대 둘의 자식을 가지는 트리이다.

이진 탐색 트리는 왼쪽 자식들 <= 부모 노드 < 오른쪽 자식들을 모든 노드에 만족하는 이진 트리이다.

허나, 중복된 값과 좌우의 문제는 갈릴 수 있음.

--

완전 이진 트리(complete binary tree)

마지막 단계를 제외한 모든 노드가 채워져 있으며, 마지막 단계도 왼쪽에서 오른쪽으로 채워져있는 이진 트리.

전 이진 트리(full binary tree)

모든 노드의 자식이 없거나, 둘인 이진 트리이다.

포화 이진 트리(perfect binary tree)

전 이진 트리이면서 완전 이진 트리인 경우.

모든 말단 노드는 같은 높이에 있으며, 마지막 단계에서 노드의 개수도 최대여야 한다.

실제 상황에서 흔한 케이스는 아니다.

--

이진 트리 순회

중위 순회(in-order)

좌-중-우 순회

전위 순회(pre-order)

중-좌-우 순회

후위 순회(post-order)

좌-우-중 순회

#include <cstdio>
struct node
{
    node *left;
    node *right;
    int data;
};
node *root, *leaf;
void init();
void in(node *r);
void post(node *r);
void pre(node *r);
int main()
{
    init();
    int command;
    while (1)
    {
        printf("1-pre / 2-in / 3-post / 4-exit\n : ");
        scanf("%d", &command);
        switch (command)
        {
        case 1: pre(root); break;
        case 2: in(root); break;
        case 3: post(root); break;
        case 4: return 1;
        }
        printf("\n");
    }
 
}
void init()
{
    root = new node;
    leaf = new node;
    root->left = new node;
    root->right = new node;
    root->left->left = new node;
    root->left->right = new node;
    root->right->left = new node;
    root->right->right = new node;
    root->left->left->left = leaf;
    root->left->left->right = leaf;
    root->left->right->left = leaf;
    root->left->right->right = leaf;
    root->right->left->left = leaf;
    root->right->left->right = leaf;
    root->right->right->left = leaf;
    root->right->right->right = leaf;
    root->data = 4;
    root->left->data = 2;
    root->right->data = 6;
    root->left->left->data = 1;
    root->left->right->data = 3;
    root->right->left->data = 5;
    root->right->right->data = 7;
    leaf->data = -1;
}
void in(node *r)
{
    if(r->left->data != -1)
        in(r->left);
    printf("%d   ", r->data);
    if(r->right->data != -1)
        in(r->right);
}
void post(node *r)
{
    if (r->left->data != -1)
        post(r->left);
    if (r->right->data != -1)
        post(r->right);
    printf("%d   ", r->data);
}
void pre(node *r)
{
    printf("%d   ", r->data);
    if (r->left->data != -1)
        pre(r->left);
    if (r->right->data != -1)
        pre(r->right);
}

-----

이진 힙

최소 힙과 최대 힙이 있다.

최소 힙은 가장 낮은 수가 루트이며 리프로 갈수록 수가 커진다.

최대 힙은 가장 높은 수가 루트이며 리프로 갈수록 수가 커진다.

최소 힙 코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector<int> heap;
    int num;
    char command;
    while (1)
    {
        printf("입력 - i / 삭제 - d\n : ");
        scanf("%c", &command);
        if (command == 'i')
        {
            printf("입력할 자연수 : ");
            scanf("%d", &num);
            heap.push_back(num);
            for (int i = heap.size() - 1; i > 0; i = (i+1)/2 - 1)
                if (heap[i] < heap[((i + 1) / 2) - 1])
                    swap(heap[i], heap[((i + 1) / 2) - 1]);
        }
        else if (command == 'd')
        {
            if (!heap.empty())
            {
                printf("%d\n", heap.front());
                swap(heap.front(), heap.back());
                heap.pop_back();
                for (int i = 0; i < heap.size();)
                {
                    if (i * 2 + 3 <= heap.size())
                    {
                        if (heap[i * 2 + 1] > heap[i * 2 + 2])
                        {
                            if (heap[i] > heap[i * 2 + 2])
                                swap(heap[i], heap[i * 2 + 2]);
                            i = i * 2 + 2;
                        }
                        else
                        {
                            if (heap[i] > heap[i * 2 + 1])
                                swap(heap[i], heap[i * 2 + 1]);
                            i = i * 2 + 1;
                        }
                    }
                    else if (i * 2 + 2 == heap.size())
                    {
                        if (heap[i] > heap[i * 2 + 1])
                            swap(heap[i], heap[i * 2 + 1]);
                        i = i * 2 + 1;
                    }
                    else
                        break;
                }
            }
        }
        while (getchar() != '\n');
    }
}