이진트리순회_레벨순회(level)/전위순회(preorder)/중위순회(inorder)/후위순회(postorder)

트리 자료구조란

- 무방향이면서 사이클이 없는 연결그래프(즉, 트리는 그래프의 일종)

- N개의 노드와 N-1개의 간선을 가짐

- 이진트리란, 트리 중 각 노드의 자식들이 2개 이하인 트리

- 이진트리를 순회하는 방식은 크게 레벨순회, 전위순회, 중위순회, 후위순회가 있음

레벨 순회(Level Order Traversal)

- 트리의 루트부터 리프까지 계층적으로 순회하는 방식

- 가장 높은 층을 먼저 순회하며 큐로 구현

- 그래프에서의 bfs와 동일하게 구현하나, 사이클이 없기 때문에 이전에 방문한 노드를 별도로 체크해줄 필요가 없음(부모 노드만 기록)

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int N;
vector<vector<int>> graph(10, vector<int>(0));
vector<int> parent(10, 0);

void setGraph() {

    scanf("%d", &N);
    for (int i=0; i<N-1; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
}

void level(int st) {

    queue<int> q;
    q.push(st);

    while (!q.empty()) {

        int cur = q.front();
        q.pop();
        cout<<cur<<" ";

        for (int i=0; i<graph[cur].size(); i++) { 
            int next = graph[cur][i];
            if (next == parent[cur]) continue; //다음 노드가 부모 노드이면 패스
            q.push(next);
            parent[next] = cur;
        }
    }
}

int main() {

    setGraph();
    level(1);
    return 0;
}

/*
input: 
7
1 2
1 3
2 4
2 5
3 6
3 7

output: 
1 2 3 4 5 6 7
*/

전위 순회( Preorder Traversal)

- 현재 정점을 탐색

- 현재 정점의 왼쪽에 있는 서브트리 탐색

- 현재 정점의 오른쪽에 있는 서브트리 탐색

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int N;
int lc[10];
int rc[10];

void setGraph() {

    scanf("%d", &N);
    for (int i=0; i<N; i++) {
        int p, c1, c2;
        scanf("%d %d %d", &p, &c1, &c2);
        if (c1 != -1) lc[p] = c1;
        if (c2 != -1) rc[p] = c2;
    }
}

void preorder(int node) {

    cout<<node<<" ";
    if (lc[node]) preorder(lc[node]);
    if (rc[node]) preorder(rc[node]);
}

int main() {

    setGraph();
    preorder(1);
    return 0;
}

/*
input: 
7
1 2 3
2 4 5
3 6 7
4 -1 -1
5 -1 -1
6 -1 -1
7 -1 -1

output:
1 2 4 5 3 6 7
*/

중위 순회(Inorder Traversal)

- 현재 노드의 왼쪽 서브트리 탐색

- 현재 노드 탐색

- 현재 노드의 오른쪽 서브트리 탐색

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int N;
int lc[10];
int rc[10];

void setGraph() {

    scanf("%d", &N);
    for (int i=0; i<N; i++) {
        int p, c1, c2;
        scanf("%d %d %d", &p, &c1, &c2);
        if (c1 != -1) lc[p] = c1;
        if (c2 != -1) rc[p] = c2;
    }
}

void inorder(int node) {

    if (lc[node]) inorder(lc[node]);
    cout<<node<<" ";
    if (rc[node]) inorder(rc[node]);
}

int main() {

    setGraph();
    inorder(1);
    return 0;
}

/*
input: 
7
1 2 3
2 4 5
3 6 7
4 -1 -1
5 -1 -1
6 -1 -1
7 -1 -1

output:
4 2 5 1 6 3 7
*/

후위 순회(Postorder Traversal)