DFS(전위, 중위 , 후위)

DFS(깊이 우선 탐색) by recursion

접근 방식

a → b → c → d → b → a → e → f → g → e → e 의 순서로 접근을 한다 깊이를 우선적으로 탐색하기 때문에 세로 방향을 먼저 탐색하고 만약에 형제 노드를 방문하고 싶다면 부모노드로 다시 올라와서 형제 노드로 접근해야한다

접근하는 코드

def traversal(root):
    if root is None:
        return
    traversal(root.left)
    traversal(root.right)

루트만 있으면 루트가 가리키는 트리에 속한 모든 노드를 접근한다

종류

1. 전위순회(preorder)
2. 중위순회(inorder)
3. 후위순회(postorder)

접근 방식은 위와 같다! 순서만 달라질뿐!

전위순회

전위순회의 순서는 A → B → A → C

def preorder(cur_node):
    if cur_node is None:
        return

    // 1. 방문
    print(cur_node.vlaue)
    // 2. 접근
    preorder(cur_node.left)
    preorder(cur_node.right)

preorder(root)

1. preorder에 root를 넣음
2. print에 의해서 cur_node(여기선 root)가 콘솔창에 찍힘
3. root 노드의 left에게 위임(접근과 동시에 재귀해서 이번엔 left로 넘어간다)
4. 현재 cur_node는 b임
5. print에 의해서 콘솔에 b의 value가 찍힘
6. b의 left와 right 하나씩 접근
7. 하지만 None이라서 그냥 패스
8. 다시 cur_node는 root 즉 A노드임
9. 이번엔 root 노드의 right child인 c로 넘어감
10. 다시 B에서 했던것 처럼 반복

💡 전위(pre)인 이유는 자기 자식한테 가기 전에 본인부터 출력을 하기 때문이다.

중위순회

중위 순회의 순서는 B → A → C → A

def preorder(cur_node):
    if cur_node is None:
        return

    preorder(cur_node.left)
    print(cur_node.vlaue) // left부터 접근한 후에 나를 방문함
    preorder(cur_node.right)

preorder(root)

 

후위순회

후위 순회의 순서는 B → C → A

자식 노드들을 전부 보고 나서 나를 방문함

def preorder(cur_node):
    if cur_node is None:
        return

    preorder(cur_node.left)
    preorder(cur_node.right)
    print(cur_node.vlaue)

preorder(root)

응용

조금 더 큰 트리 구조로 전위, 중위, 후위 순회로 하나씩 어떻게 순회하는지 보자

회색 글자는 돌아가는 것을 표현한 것

빨간 글자는 프린트 되는 부분(뽀인트)

전위 순회

A → B → D → G → D → H → D → B → E → B → A → C → F

중위 순회

G → D → H → D → B → E → B → A → C → F

후위순회

G → D → H → D → B → E → B → A → C → F → C → A