트리 순회

너비 우선 탐색 vs 깊이 우선 탐색

시간 복잡도는 같음. 다만, 공간 복잡도에서 효율 차이가 존재함.

깊이가 깊은 트리의 경우 =>너비 우선 탐색 사용 (너비가 넓으면 큐에 노드가 많이 추가됨)

너비가 넓은 트리의 경우 => 깊이 우선 탐색 사용

 

깊이 우선 탐색 종류

//            10
//        6        15
//     3     8        20

전위 순회 - [10, 6, 3, 8, 15, 20]을 반환하므로 10을 루트로 삼아서 다시 만들 때 좋음(데이터 이전, 복사 등)

후위 순회 - [3, 8, 6, 20, 15, 10]

중위 순회 - 반환되는 값이 오름차순을 이룸 [3, 6, 8, 10, 15, 20]

 

---

이진 트리를 예제로 함

너비 우선 탐색

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    BFS() {
        let node = this.root;
        let data = [];
        let queue = [];
        queue.push(node);

        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;
    }
}

깊이 우선 탐색 (전위 순회)

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    DFSPreOrder() {
        let data = [];
        let node = this.root
        function traverse(node) {
            data.push(node.value);
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
        }
        traverse(node);
        return data;
    }
}

//            10
//        6        15
//     3     8        20



let tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSPreOrder();

깊이 우선 탐색 (후위 순회)

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    DFSPostOrder() {
        let data = [];
        let node = this.root
        function traverse(node) {
            if (node.left) traverse(node.left);
            if (node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(node);
        return data;
    }
}

//            10
//        6        15
//     3     8        20



let tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSPostOrder();

깊이 우선 탐색 (중위 순회)

맨 왼쪽에서부터 x방향으로 순서대로 출력되는 결과를 얻을 수 있음

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    DFSInOrder() {
        let data = [];
        let node = this.root
        function traverse(node) {
            if (node.left) traverse(node.left);
            data.push(node.value);
            if (node.right) traverse(node.right);
        }
        traverse(node);
        return data;
    }
}

//            10
//        6        15
//     3     8        20

// 3 6 8 10 15 20

let tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSInOrder();