트리 순회 (TREE TRAVERSAL)

• 일반적인 트리 모두에서 사용가능하다

두가지 방법

Breadth-first Search(너비 우선)

다음 레벨로 넘어가기전에 같은 레벨에 있는 모든 노드들을 거쳐가는것!(자식 노드들을 보기전에 형제 노드들을 먼저 본다.)

Steps (편의상 queue를 직접 class로 구현하지않고 배열을 사용한다, dequeue는 shift)

1. 큐를 생성하고, 노드의 값을 저장할 리스트 변수(방문한 순서)를 생성한다.
2. 큐에 루트노드를 넣는다.
3. 큐에 아무 값이 없을때까지 루프를 돈다.
4. 만약 큐에 무언가 들어있다면 dequeue를 사용하여 가장 앞의 값을 빼고 리스트 변수에 push해준다.
5. 4번에서 dequeue한 노드의 왼쪽에 값이 있는지 확인하고 값이 있으면 큐에 넣는다.
6. 4번에서 dequeue한 노드의 오른쪽에 값이 있는지 확인하고 값이 있으면 큐에 넣는다.
7. 3~4를 반복해준다.
8. return 리스트

구현

BFS(){
        if(!this.root) return false
        let visited = [], queue = [], node = this.root
        queue.push(node)
        while(queue.length){
            node = queue.shift()
            visited.push(node.val)
            // queue에 push해주어 수평 레벨에 대한 노드를 넣어준다.
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
        return visited
    }

Depth-first Search(깊이 우선)

형제 노드로 넘어가기전에 수직으로 트리의 끝까지 내려간다.

DFS - PreOrder(전위순회)

root => left => right
1. 방문한 노드를 저장할 visited 변수와 현재 노드를 가르키는 current변수를 생성한다.
2. current을 인자로 받는 헬퍼 함수를 생성한다(traverse(node))
3. visited에 인자로 받은 node를 넣어준다.
4. node.left가 있다면 node.left값으로 헬퍼함수를 실행해준다.
5. node.right가 있다면 node.right값으로 헬퍼함수를 실행해준다.
6. return visited

DFSPreOrder(){
        let visited = [], current = this.root
        function traverse(node){
                visited.push(node.val)
                if(node.left) traverse(node.left)
                if(node.right) traverse(node.right)
        }
        traverse(this.root)
        return visited
}

DFS - PostOrder(후위순회)

left => right => root

DFSPostOrder(){
        let visited=[], current = this.root
        function traverse(node){
            if(node.left) traverse(node.left)
            if(node.right) traverse(node.right)
            visited.push(node.val)
        }
        traverse(current)
        return visited
    }

DFS - InOrder(중위순회)

left => root => right

DFSInOrder(){
        let visited=[], current = this.root
        function traverse(node){
            if(node.left) traverse(node.left)
            visited.push(node.val)
            if(node.right) traverse(node.right)
        }
        traverse(current)
        return visited
    }

사용되는 상황

시간 복잡도는 같기 때문에 트리의 구조에 따라 무엇을 사용할지 정한다.

• 깊이보다 너비가 넓은 트리의 경우 : DFS (더 적은 공간을 차지한다, BFS를 사용할경우 queue에 많은 노드들을 저장해야함)

전위,후위,정위

• 정위 : 모든 노드들을 오름차순으로 구할수있다. (이진 탐색 트리일경우)