트리 순회

문제

언어

  • JavaScript

트리의 순회

  • 트리의 모든 노드를 방문하는 순서입니다.
  • 트리도 그래프이기 때무넹 DFS, BFS 모두 가능합니다.
  • DFS 는 노드, 왼쪽 자식, 오른쪽 자식이 있을 때, 노드를 언제 방문할지에 따라서 프리오더(preorder), 인오더(inorder), 포스트오더(postorder) 이렇게 총 3 가지 방문 순서가 있습니다.

프리오더 (Pre-Order)

  1. 노드 방문
  2. 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더
  3. 오른쪽 자식 노드를 루트로 하는 서브 트리를 프리오더

인오더 (In-Order)

  1. 왼쪽 자식 노드를 루트로 하는 서브 트리를 인오더
  2. 노드 방문
  3. 오른쪽 자식 노드를 루트로 하는 서브 트리를 인오더

포스트오더 (Post-Order)

  1. 왼쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더
  2. 오른쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더
  3. 노드 방문

문제 풀이 step 1

  • 본 문제는 트리의 순회 방법에 대해서 묻는 문제로 Pre-Order, In-Order, Post-Order 를 이해하고 적용하는 문제입니다.
  • 각 트리의 순회 방법에 따라서 구현해주시면 됩니다.
  • 트리의 표현 방법 중에서 구조체나 클래스를 이용해서 표현하는 방법을 사용했습니다.
    • Node 클래스를 만들고, 각 노드를 배열에 저장했습니다.
  • 그리고 각 노드를 charCode 를 이용해서 숫자로 변환해서 조금 더 접근하기 쉽게 구현했습니다.
  • 자세한 내용은 주석으로 설명하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// Node 클래스 생성 (left link, right link 로 구성)
class Node {
	constructor(left, right) {
		this.left = left;
		this.right = right;
	}
}

// 전위 순회 함수로 node 를 먼저 방문
const preOrder = (nodes, index) => {
	if (index < 0) return "";

	let str = "";
	str += String.fromCharCode("A".charCodeAt(0) + index);
	str += preOrder(nodes, nodes[index].left);
	str += preOrder(nodes, nodes[index].right);

	return str;
};

// 중위 순회 함수로 node 를 중간에 방문
const inOrder = (nodes, index) => {
	if (index < 0) return "";

	let str = "";
	str += inOrder(nodes, nodes[index].left);
	str += String.fromCharCode("A".charCodeAt(0) + index);
	str += inOrder(nodes, nodes[index].right);

	return str;
};

// 후위 순회 함수로 node 를 마지막에 방문
const postOrder = (nodes, index) => {
	if (index < 0) return "";

	let str = "";
	str += postOrder(nodes, nodes[index].left);
	str += postOrder(nodes, nodes[index].right);
	str += String.fromCharCode("A".charCodeAt(0) + index);

	return str;
};

const solution = (input) => {
	const n = parseInt(input[0]);

	const nodes = [];
	for (let i = 1; i < n + 1; i++) {
		// 이후에 더 접근하기 쉽게 알파벳을 숫자로 변환
		const [root, left, right] = input[i]
			.split(" ")
			.map((v) => v.charCodeAt(0) - "A".charCodeAt(0));

		nodes[root] = new Node(left, right);
	}

	return (
		preOrder(nodes, 0) + "\n" + inOrder(nodes, 0) + "\n" + postOrder(nodes, 0)
	);
};

console.log(solution(input));