트리순회 - bfs

트리순회

트리순회란?

💡 트리탐색이라고도 불리우며 트리의 각 노드를 방문하는 과정을 말한다. 모든 노들를 한 번씩 방문 해야 하므로 완전 탐색이라고도 불린다. 순회 방법으로는 너비 우선 탐색의 BFS와 깊이 우선 탐색의 DFS가 있다.

BFS(너비 우선 탐색)

탐색 순서

루트노드로 부터 가까운 노드들 다 탐색하고 다음 그 아래 레벨의 노드들 탐색하는 말그대로 길이를 탐색하는 것. 위의 그림에서 볼때 2, 3번 노드를 먼저 탐색 후 4번 5번 6번 노드를 탐색한다

아래의 코드는 아주 기본적인 템플릿으로 안보고 짤 줄 알아야한다!!

from collections import deque

def levelOrder(root):
    visited = []
    if root is None:
        return 0
    q = deque()
    q.append(root)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

이 알고리즘의 이유는 모든 노드를 방문 하되 단 한번만 순회한다는 것이다

from collections import deque

def levelOrder(root):
    # 빈 리스트를 하나 만든다
    visited = []
    
    # 만약 루트가 비어있다면 => 트리가 없다면
    if root is None:
        # 0을 반환 => 근데 빈 리스트를 반환하는게 더 좋을 것 같다
        return 0
    
    # bfs를 구하려면 큐를 써야한다(왜 쓰는지만 이해하고 그냥 외우자)
    q = deque()
    # 루트 노드를 일단 큐에다가 넣는다
    q.append(root)
    # 큐안에 요소가 존재하면 반복문을 돈다
    # 여기까지가 초기 세팅이다
    while q:
        # 여기서부터 bfs 진짜 시작임
        # 너비우선 탐색 ㄱㄱ
        # 1. deque에서 가장 왼쪽에 있는 값을 빼서(dqeue해서) 그걸 cur_node 라고 하는데 루트에 '접근' 한 상태임
        # 1. 이 상태에선 q에는 아무것도 들어있지 않다(뺏으니까)
        # 2. b 노드가 앞에 있으니까 b 노드도 root 노드와 똑같이 돌아간다
        cur_node = q.popleft()
        # 1. 여기서 visitied라는 리스트에 접근한 노드의 value를 넣어준다
        # 1. 그럼 방명록을 남긴거니까 방문! 한게 된다
        visited.append(cur_node.value)

        # 1. 최근 방문한 노드(처음 기준으로 root) left child와 right child를 q에 저장해놓는다
        # 1. 나 방문할거니까 예약좀 해놓을게~~ 느낌
        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
        # 1. 다시 반복문으로 간다(반복문을 q안에 요소가 존재하면 계속 반복임, 현재 b, c 노드가 들어있을거임)
    return visited

이렇게 너비우선 탐색 def를 하나 만들고 bfs(root) 만 호출하면 자동으로 실행이 될거다

즉 기본을 알아야 응용이 잘되니까 꼭 외워놓자