DFS 이론

 

전위 순회(preorder)

트리의 전위 순회는 루트노트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 방식이다.

코드 역시 현재 노드를 출력한 후, 왼쪽, 오른쪽 순서대로 함수를 호출한다.

 

중위 순회(inorder)

트리의 전위 순회는 왼쪽 서브 트리 -> 루트노트 -> 오른쪽 서브 트리 순으로 순회하는 방식이다.

코드는 왼쪽 함수 호출, 현재 노드 출력, 오른쪽 함수 호출 순서로 진행된다.

 

후위 순회(postorder)

트리의 전위 순회는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트노트 순으로 순회하는 방식이다.

후위 순회 또한 왼쪽 함수 호출, 오른쪽 함수 호출, 현재 노드 출력 순서로 진행된다.

 

 

package main

import "fmt"

func dfs(v int) {
	if v > 7 {
		return
	} else {
		//fmt.Println(v) // 전위 순회
		dfs(v * 2)
		//fmt.Println(v) // 중위 순회
		dfs(v * 2 + 1)
		//fmt.Println(v) // 후위 순회
	}
}

func main() {
	dfs(1)
}

 

 

1 부터 7 까지 노드를 순위 별로 출력하는 코드입니다.

 

후위 순위의 같은 경우는 추후에 병합정렬에서 많이 쓰이니 알아 두시면 좋을거 같네요

이해가 잘안 되신다면 직접 코드를 치신다음 디버깅 툴을 사용하여 스택 이 쌓이는걸 직접 테스트 해보시면 좋을거 같습니다