이진 트리 기초

이진 트리

각 노드의 자식 노드의 개수가 2 이하로 구성된 트리

 

완전 이진 트리

마지막 레벨은 왼쪽부터 채워지

마지막 레벨을 제외하고 완전하게 노드들이 채워짐.

 

이진 트리의 표현은 배열!!

그래프 표현 방식은 일반적으로 쓰지 않음.

 

루트 노드의 index는 1부터 시작해야한다!!

그래서 크기 초기화를 할 때,

2 ^ h + 1로 초기화를 한다.

 

루트 노드 -> index = 1

부모 노드 -> index = index / 2

왼쪽 자식 노드 -> index = index * 2

오른쪽 자식 노드 -> index = index * 2 + 1

 

트리 순회하기

preorder 

현재 -> 왼쪽 -> 오른쪽

inorder

왼쪽 -> 현재 -> 오른쪽

postorder

왼쪽 -> 오른쪽 -> 현재

 

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

int tree[26][2];

Left, Right를 표현하는 이차원 배열

 

 

#include <iostream>
 
using namespace std;
 
int tree[26][2];
 
void preorder(int now)
{
    if (now == -1)
        return;
 
    cout << (char)(now + 'A');
    preorder(tree[now][0]);
    preorder(tree[now][1]);
}
 
void inorder(int now)
{
    if (now == -1)
        return;
 
    inorder(tree[now][0]);
    cout << (char)(now + 'A');
    inorder(tree[now][1]);
}
 
void postorder(int now)
{
    if (now == -1)
        return;
 
    postorder(tree[now][0]);
    postorder(tree[now][1]);
    cout << (char)(now + 'A');
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        char node_char, left, right;
        cin >> node_char >> left >> right;
        int node = node_char - 'A';
 
        if (left == '.')
            tree[node][0] = -1;
        else
            tree[node][0] = left - 'A';
 
        if (right == '.')
            tree[node][1] = -1;
        else
            tree[node][1] = right - 'A';
    }
 
    preorder(0);
    cout << '\n';
    inorder(0);
    cout << '\n';
    postorder(0);
    cout << '\n';
 
}