[BOJ알고리즘, C++]#9934_완전 이진 트리, 트리 순회, 순회 -> 트리 구성 유형

 

#1. 문제

 

9934번: 완전 이진 트리

 

---

 

#2. 풀이

 

1. 완전 이진트리

[자료구조]#5_트리

 

완전 이진트리는 이진트리의 한 종류로, 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있으며, 마지막 레벨의 경우 왼쪽부터, 오른쪽 순서로 노드가 채워지는 특징이 있습니다. 

 

2. 트리의 중위 순회

[자료구조]#5_트리

struct Node {
    int data;
    Node* left;
    Node* right;
};

void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);   // 왼쪽 서브 트리 순회 재귀
    cout << root->data << " ";      // 현재 노드 값 출력
    inorderTraversal(root->right);  // 오른쪽 서브 트리 순회 재귀
}

트리의 중위 순회는 트리를 순회하는 방법 중 하나로, 왼쪽 자식 노드, 현재 노드, 그리고 오른쪽 자식 노드 순서로 트리를 순회하는 방법입니다. 트리의 중위 순회를 구현하기 위해 먼저, 왼쪽 자식 노드에 대해 중위 순회를 재귀적으로 수행, 현재 노드 출력 혹은 저장, 그리고 오른쪽 자식 노드에 대해 중위 순회를 재귀적으로 수행합니다. 

 

3. 주어진 중위 순회를 전위 순회!

 

중위 순회 : 1 - [6] - 4 - [3] - 5 - [2] - 7

1. 루트 노드 : 3
2. 왼쪽 자식 노드 : 6
3. 오른쪽 자식 노드 : 2

 

1. 먼저, 중위 순회의 루트 노드는 가운데 위치합니다. 그리고, 루트 노드의 왼쪽 자식 노드는 또 루트 노드를 기준으로 왼쪽에 위치한 부분 배열의 가운데에 위치하며, 오른쪽 자식 노드는 반대로 오른쪽 부분 배열의 가운데에 위치합니다. 
2. 주어진 중위 순회를 통해 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 전위 순회하며 DFS를 재귀적으로 수행하고, 레벨 별 노드들을 왼쪽 -> 오른쪽 순서로 저장합니다.

 

---

 

#3. 코드

 

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

#define MAX 1025

int K, InOrder[MAX];
vector<int> tree[MAX];

void MakeTree(int level, int start, int end)
{
    if (start > end)
        return;

    int mid = (start + end) / 2;
    int root = InOrder[mid];

    tree[level].push_back(root);

    // #1. 왼쪽 서브트리
    MakeTree(level + 1, start, mid - 1);
    // #2. 오른쪽 서브트리
    MakeTree(level + 1, mid + 1, end);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> K;

    int n = (1 << K) - 1;
    for (int i = 0; i < n; ++i)
    {
        cin >> InOrder[i];
    }

    // 재귀 호출, 중위 순회를 통해 완전 이진 트리 구성
    MakeTree(0, 0, n - 1);

    for (int i = 0; i < K; ++i)
    {
        for (int j = 0; j < tree[i].size(); ++j)
        {
            cout << tree[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

 

---