[Algorithm] 이진트리 깊이우선탐색(DFS)

❐ 이진트리순회

이진트리는 부모노드에서 자녀노드로 뻗어나가는 구조를 가진다. 그림에서 왼쪽에 위치한 자녀는 (부모노드)*2의 값을 가지고, 오른쪽에 위치한 자녀는 (부모 노드)*2+1의 값을 가지게 된다.

이진트리를 순회하는 여러가지 방법이 있다. 이 글에서는 3가지 방법을 소개하는데 부모의 순서에 따라 전위/중위/후위 순회로 구분된다. 

 

• 전위 순회는 부모, 왼쪽자녀, 오른쪽 자녀 순서로 출력된다.
• 중위 순회는 왼쪽자녀, 부모, 오른쪽 자녀 순서로 출력된다.
• 후위 순회는 왼쪽자녀, 오른쪽 자녀, 부모 순서로 출력된다.

 

위의 그림을 전위/중위/후위 순회한 결과는 이렇다.

 

• 전위 순회: 1-2-4-5-3-6-7
• 중위 순회: 4-2-5-1-6-3-7
• 후위 순회: 4-5-2-6-7-3-1

 

코드로 나타내보자.

console.log의 위치가 어디인지에 따라 전위/중위/후위 순회가 된다.

// 전위 순회
function solution(v) {
    let answer;
    function DFS(v) {
   // 종료 조건: 인자가 7이 넘어 갈 경우 종료
    	if(v>7) return;
        else {
        	console.log(v);
        	DFS(v*2); // 왼쪽 자녀 순회
        	DFS(v*2+1); // 오른쪽 자녀 순회
        }
    }
    DFS(1)
    return answer;
}

// 중위 순회
function solution(v) {
    let answer;
    function DFS(v) {
    	if(v>7) return;
        else {
        	DFS(v*2); // 왼쪽 자녀 순회
        	console.log(v);
        	DFS(v*2+1); // 오른쪽 자녀 순회
        }
    }
    DFS(1)
    return answer;
}

// 후위 순회
function solution(v) {
    let answer;
    function DFS(v) {
    	if(v>7) return;
        else {
        	DFS(v*2); // 왼쪽 자녀 순회
        	DFS(v*2+1); // 오른쪽 자녀 순회
        	console.log(v);
        }
    }
    DFS(1)
    return answer;
}