트리의 모든 노드들을 방문하는 과정을 트리 순회라고 한다.
선형 자료구조(연결 리슽, 스택, 큐, ..)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 한다.
트리를 순회할 수 있는 방법은 전위 순회, 중위 순회, 후위 순회 이렇게 세 가지가 있다.
이러한 순회는 보통 재귀로 쉽게 구현할 수 있다.
트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.
깊이 우선 순회(DFT, Depth-First Traversal)이라고도 한다.
트리를 복사하거나, 전위 표기법을 구하는데 주로 사용된다.
트리를 복사할 때 전위 순회를 사용하는 이유는 트리를 생성할 때 자식 노드보다 부모 노드가 먼저 생성되어야 하기 때문이다.
위 트리의 전위 순회 결과 : A->B->D->E->C->F->G
중위 순회는 왼쪽 오른쪽 대칭 순서로 순회를 하기 때문에 대칭 순회(Symmetric Traversal)라고도 한다.
중위 순회는 이진 탐색 트리(BST, Binary Search Tree)에서 오름차순 또는 내림차순으로 값을 가져올 때 사용한다.
내림차순으로 값을 가져오기 위해서는 역순(오른쪽-> root-> 왼쪽)으로 중위 순회를 하면 된다.
위 트리의 중위 순회 결과 : D->B->E->A->F->C->G
후위 순회는 주로 트리를 삭제하는 데 사용된다.
부모 노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야 하기 때문이다.
위 트리의 후위 순회 결과 : D->E->B->F->G->C->A
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const node = new Node(value);
// 루트가 설정되어 있지 않다면 루트를 node로 만들어 준다.
// node는 treeNode()에서 뼈대를 받아온다.
if (!this.root) {
this.root = node;
return this;
}
else {
// 비교를 위해 current 변수를 설정해 준다.
let current = this.root;
// current가 true 라면 while문을 돌면서 value와 지금 현재 value인 current value를 비교한다.
while (true) {
// 중복된 값은 어떤 결과를 리턴하지 않는다.
if (value === current.value) return;
// value가 기준 value(current value)보다 작다면 왼쪽에 넣어준다.
if (value < current.value) {
if (!current.left) {
current.left = node;
break; // return this;
}
else {
// 이제 current value(기준)는 왼쪽의 data로 잡힌다.
current = current.left;
}
}
// value가 기준 value(current value)보다 크다면 오른쪽에 넣어준다.
else if (value > current.value) {
if (!current.right) {
current.right = node;
break; // return this;
}
else {
// 이제 current value(기준)는 오른쪽 value로 잡힌다.
current = current.right;
}
}
}
}
}
find(value) {
if (!this.root) return;
let current = this.root;
let found = false;
while (current && !found) {
if (value < current.value) {
current = current.left;
}
else if (value > current.value) {
current = current.right;
}
else {
found = true;
}
}
if (!found) return;
return current;
}
// Breadth-first Search(너비 우선 탐색)
bfs() {
let node = this.root;
let queue = [node];
let data = [];
while (queue.length) {
node = queue.shift();
data.push(node.value);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
return data;
}
// Depth-first Search(깊이 우선 탐색)
// 1. Pre-Order traversal(전위 순회)
preOrder() {
let data = [];
function traverse(node) {
data.push(node.value);
if (node.left) {
traverse(node.left);
}
if (node.right) {
traverse(node.right);
}
}
traverse(this.root);
return data;
}
// 2. In-Order traversal(중위 순회)
inOrder() {
let data = [];
function traverse(node) {
if (node.left) {
traverse(node.left);
data.push(node.data);
}
if (node.right) {
traverse(node.right);
}
}
traverse(this.root)
return data;
}
// 3. Post-Order traversal(후위 순회)
postOrder() {
let data = [];
function traverse(node) {
if (node.left) {
traverse(node.left);
}
if (node.right) {
traverse(node.right);
data.push(node);
}
}
traverse(this.root)
return data;
}
}
let nums = new bst();
nums.insert(10);
nums.insert(5);
nums.insert(11);
nums.insert(3);
nums.insert(6);
console.log(nums.bfs()); // 10, 5, 11, 3, 6
console.log(nums.preOrder()); // 10, 5, 3, 6, 11
console.log(nums.inOrder()); // 3, 5, 6, 10, 11
console.log(nums.postOrder()); // 3, 6, 5, 11, 10