이진 트리 순회 방법 (연결 구조와 순차 구조 활용)

Tree Traversals (25) ==========================

모든 이진 트리 노드의 키는 서로 다른 양의 정수입니다. 후위 순회 및 중위 순회 시퀀스가 주어지면 해당 이진 트리의 수준 순회 시퀀스를 출력해야 합니다.

입력 사양:

각 입력 파일은 하나의 테스트 케이스를 포함합니다. 각 케이스에서 첫 번째 줄은 이진 트리의 노드 수 N (<=30)을 나타냅니다. 두 번째 줄은 후위 순회 시퀀스, 세 번째 줄은 중위 순회 시퀀스입니다. 줄의 모든 숫자는 공백으로 구분됩니다.

출력 사양:

각 테스트 케이스에 대해 해당 이진 트리의 수준 순회 시퀀스를 한 줄에 출력합니다. 줄의 모든 숫자는 정확히 하나의 공백으로 구분되며, 줄 끝에 추가 공백이 없어야 합니다.

샘플 입력: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 샘플 출력: 4 1 6 3 5 7 2

문제 요약: 후위 순회와 중위 순회 결과를 기반으로 이진 트리의 수준 순회 결과를 생성합니다.

핵심 접근법

후위 순회 마지막 요소를 루트로 설정
중위 순회에서 루트 위치를 확인하여 좌우 서브트리 구분
좌우 서브트리 크기를 기준으로 후위 순회 분할
재귀적으로 좌우 서브트리 생성
노드가 없는 경우 재귀 종료

구현 고려사항

이진 트리 저장 방식 선택

배열: 완전 이진 트리에 적합, 접근 속도 빠름

포인터: 임의 이진 트리에 적합, 메모리 유연성 우수

일반적으로 연결 구조(포인터로 노드 연결) 사용

struct node{
    int value;
    node* left;
    node* right;
}

struct BinaryNode {
    int value;         // 노드 값
    BinaryNode* left;  // 왼쪽 자식 포인터
    BinaryNode* right; // 오른쪽 자식 포인터
    BinaryNode(int x) : value(x), left(nullptr), right(nullptr) {} // 생성자
};

후위 순회에서 루트를 찾은 후 서브트리 분할 방법

후위 및 중위 순회로 이진 트리 구축

BinaryNode* createTree(int rootIndex, int inStart, int inEnd)

매개변수: (루트 인덱스, 중위 시작, 중위 끝)

서브트리 분할은 이 세 매개변수를 통해 수행

좌측 서브트리:

// 루트 인덱스를 중위 범위에서 사용

좌측 노드 수 = rootIndex - inStart;

좌측 루트 = rootIndex - (inEnd - rootIndex + 1)

root->left = createTree(rootIndex - (inEnd - rootIndex + 1), inStart, rootIndex - 1);

우측 서브트리:

root->right = createTree(rootIndex - 1, rootIndex + 1, inEnd);

서브트리 루트 결정 방법

각 서브트리의 루트는 해당 후위 순회 마지막 요소

재귀 종료 조건

서브트리 노드 수가 0일 때 재귀 종료

> if (inStart > inEnd) {
>     return nullptr; // 노드 없음
> }
> ```

서브트리 생성 후 부모 노드에 연결 시점

재귀 호출 완료 후 서브트리 루트를 부모 노드의 자식으로 할당

코드 구현:

#include
#include
#include <unordered_map>
#include
using namespace std;

vector post_seq(35), in_seq(35);
unordered_map in_map;
// 이진 트리 노드 정의
struct BinaryNode {
int value;
BinaryNode* left;
BinaryNode* right;
BinaryNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

// 후위 및 중위 순회로 이진 트리 생성
BinaryNode* createTree(int root_idx, int in_start, int in_end) {
// 재귀 종료 조건: 유효하지 않은 구간
if (in_start > in_end) {
return nullptr;
}
// 후위 순회 마지막 요소는 현재 루트
int node_val = post_seq[root_idx];
BinaryNode* current = new BinaryNode(node_val);

// 중위 순회에서 루트 위치 찾기
int root_pos = in_map[node_val];

current->left = createTree(root_idx - (in_end - root_pos + 1), in_start, root_pos - 1);

current->right = createTree(root_idx - 1, root_pos + 1, in_end);

return current;
}

// 수준 순회 수행
vector levelTraversal(BinaryNode* root) {
vector result;
if (!root) return result;

queue q;
q.push(root);

while (!q.empty()) {
_binaryNode* node = q.front();
q.pop();
result.push_back(node->value);


if (node->left) q.push(node->left);

if (node->right) q.push(node->right);
}

return result;
}

int main() {
int N;
cin >> N;

// 후위 순회 입력 처리
for (int i = 0; i < N; ++i) {
cin >> post_seq[i];
}

// 중위 순회 입력 및 맵 생성
for (int i = 0; i < N; ++i) {
cin >> in_seq[i];
in_map[in_seq[i]] = i;
}

// 트리 생성
BinaryNode* root = createTree(N-1, 0, N-1);

vector output = levelTraversal(root);

for (int i = 0; i < output.size(); ++i) {
if (i > 0) cout << " ";
cout << output[i];
}
cout << endl;

return 0;
}

최적화 포인트

초기 버전:

BinaryNode* createTree(vector<int>& post, int post_start, int post_end, vector<int>& in, int in_start, int in_end, unordered_map<int, int>& in_map)

최적화 버전:

BinaryNode* createTree(int root_idx, int in_start, int in_end)

후위 순회 시작/끝 지점을 매개변수로 전달하는 대신 루트 인덱스만 전달하여 간결성 향상
중위 순회에서 루트 위치 탐색 시 매번 순회 대신 사전에 맵으로 저장하여 시간 효율성 향상

다른 알고리즘 구현 -[류chu오](1020. Tree Traversals (25)-PAT 마스터 문제(후위 중위 → 수준 순회) – liuchuo)

아이디어: 후위 중위 → 전위 변환 코드와 유사한데, 루트 인덱스를 추적하는 변수를 추가하여 수준 순회 결과를 직접 저장

개념 설명:

수준 정보를 저장하는 map을 사용해 배열 구조처럼 활용
map의 키 자동 정렬 기능을 이용해 수준 순서 유지

첫 번째 해법과 비교

장점

코드 간결성 우수, 알고리즘 문제에 적합
map의 자동 정렬 기능으로 BFS 코드 생략

단점

메모리 효율성 낮음: 깊이가 큰 트리에서 인덱스 급증
확장성 제한: N≤30 범위에 한정

#include
#include
#include
using namespace std;
vector post_seq, in_seq;
map level_map;
void traverse(int root_idx, int in_start, int in_end, int level_idx) {
if(in_start > in_end) return ;
int i = in_start;
while(i < in_end && in_seq[i] != post_seq[root_idx]) i++;
level_map[level_idx] = post_seq[root_idx];
traverse(root_idx - 1 - in_end + i, in_start, i - 1, 2 * level_idx + 1);
traverse(root_idx - 1, i + 1, in_end, 2 * level_idx + 2);
}
int main() {
int n;
scanf("%d", &n);
post_seq.resize(n);
in_seq.resize(n);
for(int i = 0; i < n; i++) scanf("%d", &post_seq[i]);
for(int i = 0; i < n; i++) scanf("%d", &in_seq[i]);
traverse(n-1, 0, n-1, 0);
auto it = level_map.begin();
printf("%d", it->second);
while(++it != level_map.end()) printf(" %d", it->second);
return 0;
}

태그: 이진 트리 후위 순회 중위 순회 수준 순회 재귀 구조

5월 25일 16:03에 게시됨

괴물 클럽

이진 트리 순회 방법 (연결 구조와 순차 구조 활용)

인기 태그