1. 개념

(1) BFS (너비 우선 탐색)

Breadth-First Search

같은 Level인 노드를 먼저 적어주는 탐색 방법

BFS는 큐를 이용해서 구현

Node 자기자신을 dequeue하면서 자식 Node을 enqueue하여 Queue가 빌 때까지 반복

자식들이 어떤 순서로 enqueue되느냐에 따라 결과 달라짐

---

(2) DFS (깊이 우선 탐색)

Depth-First Search

루트 노드에서 한 방향으로 branch 끝까지 탐색한 후, 자식 노드 있는 위치부터 다시 되돌아와서 탐색

DFS는 스택을 이용해서 구현

자식들이 push될 때 어떤 순서로 스택에 쌓이느냐에 따라 결과 달라질 수 있음

---

(3) 트리 순회

트리의 모든 노드들을 방문하는 과정을 트리 순회(Tree Traversal)라고 함

Traversal은 기본적으로 DFS이며, 콘솔 표시 방법에 따라 3가지 방식으로 구분됨

Pre-order를 주로 쓰고 대표적인 DFS라고 불림. In-order, Post-order은 상식처럼 알아두자

[1] Pre-order (노드 왼쪽)

[2] In-order (노드 아래)

[3] Post-order (노드 오른쪽)

---

2. 구현하기

import BinarySearchTree, Queue, Stack 

const bst = new BinarySearchTree();

bst.insert(4);
bst.insert(2);
bst.insert(6);
bst.insert(1);
bst.insert(3);
bst.insert(5);
bst.insert(7);

BFS 구현하기

function bfs(tree){
    const queue = new Queue();
    queue.enqueue(tree.root);
    while(queue.length > 0){ // length === 0 때까지
        const node = queue.dequeue();
        console.log(node.value)
        if(node.left){
            queue.enqueue(node.left);
        }
        if(node.right){
            queue.enqueue(node.right);
        }
    }
}

bfs(bst);
bst;

DFS 구현하기

function dfs(tree){
    const stack = new Stack();
    stack.push(tree.root);
    while(stack.length > 0){
        const node = stack.pop();
        console.log(node.value);
        if(node.right){ // right 먼저
            stack.push(node.right);
        }
        if(node.left){
            stack.push(node.left);
        }
    }
}

const bst = new BinarySearchTree();
dfs(bst);

Traversal 구현하기

(1) preOrder (= DFS) 실행결과

function preOrder(node){
    if(!node) return;
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
}

preOrder(bst.root);

---

(2) inOrder 실행결과

function inOrder(node){
    if(!node) return;
    inOrder(node.left);
    console.log(node.value);
    inOrder(node.right);
}

inOrder(bst.root);

---

(3) postOrder 실행결과

function postOrder(node){
    if(!node) return;
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.value);
}

postOrder(bst.root);