17 트리 순회

17.1 트리 순회

  트리 순회는 말 그대로 어떤 트리에서든지 사용할 수 있는 개념이다. 예를 들어 이진 탐색 트리든지, 그냥 이진 트리든지 그 외의 어떤 트리들에도 다 사용이 가능한 순회 방법이다. 즉 트리의 특성을 가지고 있다면 트리 순회를 할 수 있다. 트리를 순회하는 방법에는 많은 방법이 존재하고 대표적으로 너비 우선 탐색(Breadth First Search)과 깊이 우선 탐색(Deapth First Search)가 있다. 어떤 탐색 방법이든 모든 노드들을 순회하는 것은 동일하다. 

 

17.2 너비 우선 탐색

  너비 우선 탐색(Breadth First Search)은 트리의 같은 레벨에 있는 모든 노드를 거쳐가며 순회를 하는 방식이다.

/*
트리)

           10
         /    \ 
        6      15
       / \     / \
      3	  8  12   20

너비 우선 탐색) 같은 레벨의 노드들을 거쳐가면서 탐색

	------>10
   --->6----------->15
  3----->8----->12----->20
  
*/

  너비 우선 탐색을 구현하려면 큐 자료 구조를 이용해야 한다.(선입선출) 직접 큐 클래스를 만들어서 활용하는 것보다 배열을 활용해서 큐를 만드는 것이 구현하기 더 편리하다.

 

◎수도코드

1) 먼저 변수 두 개를 만든다.

2) 큐를 만들어서 요소들을 추적하고, 데이터를 담는 배열을 만들어서 마지막에 반환해 준다.

즉, 마지막에 데이터를 담은 배열을 반환하고, 큐는 마지막에는 비어 있는 배열 상태가 된다.(큐 배열은 그냥 도와주는 역할임)

3) 처음에는 루트 노드를 큐 배열에 넣고, 큐 배열에 데이터가 있다면 계속 루프를 돌린다.

4) 그리고 큐에서 디큐를 한다. 배열을 사용해서 만드는 경우에는 shift() 메서드를 사용해서 큐 배열의 맨 앞에 있는 데이터를 제거 한다.

5) 그리고 제거한 노드의 값을 데이터를 담는 배열에 추가해 준다.

6) 그리고 제거된 노드의 왼쪽/오른쪽에 노드가 있는지 확인하고 노드가 있다면 해당 노드를 큐 배열에 담는다.

7) 모든 루프가 끝난 다음에는 모든 노드의 값들을 저장한 변수를 출력해 준다.

 

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

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            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 undefined;
        return current;
    }

    BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node); 

        while(queue.length){ //빈 배열을 무조건 true가 나와서 length를 이용
           node = queue.shift(); // shift 원본 배열 직접 변경(큐 배열에서 제거됨)
           data.push(node.value); // push 원본 배열 직접 변경(데이타 배열에 추가됨)
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;    
    }
}

17.3 깊이 우선 탐색

  깊이 우선 탐색은 너비 우선 탐색 처럼 형제노드를 다 거쳐가면서 탐색하는 것이 아니라, 수직으로 트리의 끝까지 내려가면서 검색하는 것이다. 깊이 우선 탐색은 순회시 순회된 데이터를 저장하는 배열에 언제 순회된 데이터를 저장할지에 따라 전위 순회, 후위 순회, 중위 순회로 나뉠 수 있다.

 

◎수도코드

1) 순회시 확인을 한 노드들의 값을 저장하는 배열을 만든다.

2) 맨 마지막에는 값을 저장한 배열을 반환한다.

3) 현재 확인하고 있는 노드를 가리키는 포인터 역할을 할 변수를 만들어 준다. 그리고 트리의 루트노드를 할당한다.

4) 이제 헬퍼 함수인 중첩 함수를 만든다. 

5) 이제 노드들을 방문해서 노드들의 값을 저장하는 배열에 값을 추가해 준다.

6) 그리고 확인한 노드가 왼쪽/오른쪽 프로퍼티에 노드를 가지고 있다면 재귀 방식으로 헬퍼 함수를 다시 호출합니다.

 

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

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            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 undefined;
        return current;
    }

    DFSPreOrder(){ //전위
        var data = [];
        function traverse(node){
            data.push(node.value); // <--해당 코드의 위치에 따라 dfs의 유형이 달라진다.
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
    DFSPostOrder(){ //후위
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value); // <--해당 코드의 위치에 따라 dfs의 유형이 달라진다.
        }
        traverse(this.root);
        return data;
    }
    DFSInOrder(){ //중위
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.value); // <--해당 코드의 위치에 따라 dfs의 유형이 달라진다.
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
}

  그렇다면 너비 우선 탐색, 깊이 우선 탐색은 언제 사용하면 좋을까? 우선 트리의 너비가 넓은 경우에는 깊이 우선 탐색 방법이 더 유리하다. 왜냐하면 너비 우선 탐색은 큐에 저장해서 그것을 활용하는 방식으로 이뤄지기 때문에 넓이가 넓어 질수록 많은 데이터를 큐에 저장해야 하므로 공간 복잡도가 올라가기 때문이다. 반대로 트리의 깊이가 깊은 경우에는 너비 우선 탐색 방법이 유리하다. 깊이 우선 탐색은 헬퍼 함수가 재귀 호출되는데 깊이가 깊어지면 그 만큼 콜 스택이 계속해서 쌓이기 때문이다.