[BOJ] 1991번 Tree 순회 방법 - 전위/중위/후위 순회 & Javascript 코드

자료 구조 중 이진트리를 순회하는 방법은 세가지 방법이 있다.

 

자세한 내용은 아래의 포스터를 확인해보면 된다.

2024.05.09 - [Algorithm] - [Algorithm] 이진 트리(Binary Tree)와 트리 순회(Tree Traversal)

[Algorithm] 이진 트리(Binary Tree)와 트리 순회(Tree Traversal)

 

• 전위 순회 (Pre-order)
• 중위 순회 (In-order)
• 후위 순회 (Post-order)

이러한 순회 방법은 트리 내의 모든 노드를 방문하는 기초적인 방법들이다. 

순회 방법은 트리의 형태와 원하는 결과에 따라 다르게 선택될 수 있다.

 

그렇다면 3가지 트리 순회에 대해 알아보자

전위 순회 (Pre-order)

Root - Left - Right

상단의 트리를 전위 순회로 순회한다면 다음과 같은 순서로 노드를 순회할 것이다.

• ABDCEFG

중위 순회 (In-order)

Left - Root - Right

• DBAECFG

후위 순회 (Post-order)

Left - Right - Root

• DBEGFCA

 

트리를 순회하는 방법은 주로 재귀적으로 구현된다.

재귀를 통해 트리의 노드를 방문하면서 순회를 수행할 수 있다.

또한, 스택(Stack)이나 큐(Queue)를 이용하여 반복적으로 순회할 수 도 있다.

 

백준 1991번 풀이 코드

const fs = require('fs');
let [N, ...input] = fs.readFileSync(__dirname + '/input.txt')
    .toString()
    .trim()
    .split('\n')
    .map(value => value.split(' '));
let n = Number(N[0]);

const tree = {};
for (let i = 0; i < input.length; i++) { 
    const [node, left, right] = input[i];
    tree[node] = [left, right];
}

//전위 순회(Pre-order)
let preOrderResult = "";
const recursivePreOrder = (node) => { 
    if (node == ".") return;
    const [left, right] = tree[node];
    //루트 노드를 방문
    preOrderResult += node;
    //왼쪽 서브 트리를 후위 순회
    recursivePreOrder(left);
    //오른쪽 서브 트리를 후위 순회
    recursivePreOrder(right);
}

//중위 순회(In-order)
let inOrderResult = "";
const recursiveInOrder = (node) => { 
    if (node == ".") return;
    const [left, right] = tree[node];
    recursiveInOrder(left);
    inOrderResult += node;
    recursiveInOrder(right);
}

//후위 순회(Post-order)
let postOrderResult = "";
const recursivePostOrder = (node) => { 
    if (node == ".") return;
    const [left, right] = tree[node];
    recursivePostOrder(left);
    recursivePostOrder(right);
    postOrderResult += node;
}

const main = () => { 
    recursivePreOrder('A');
    console.log(preOrderResult);
    recursiveInOrder('A');
    console.log(inOrderResult);
    recursivePostOrder('A');
    console.log(postOrderResult);
}
main();