트리 순회

트리 순회

• 트리 탐색으로도 불림
• 트리의 각 노드를 방문하는 과정
• recurrence relation(점화식), 모든 노드를 한 번씩 방문해야 함 -> 완전탐색
• 순회 방법: BFS / DFS

너비 우선 탐색(BFS)

• 루트 노드를 기준으로 루트 노드에서 가까운 것을 탐색
• level 순서대로 (0 level, 1 level ...n level) 탐색
• bfs는 queue 사용
• 접근 해야 할 노드들을 queue에 저장 -> 탐색 시 popleft()
• visited = [] 선언 후, 방문한 노드들을 visitied에 방명록처럼 남김
• bfs 코드 템플릿(암기)

def bfs(root) :
	visited = []
    if root is None:
    	return ;
    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
    
bfs(root)

 

깊이 우선 탐색(DFS by recursion)

• DFS 구현 방법은 재귀/반복문 두가지가 있음.
• dfs 접근 코드
  
  

def dfs(cur_node):
	if cur_node is None:
    	return
    dfs(cur_node.left)
    dfs(cur_node.right)
    
dfs(cur_node)
//root(cur_node)만 나한테 줘. 그러면 root가 가리키는 tree에 속한 모든 노드를 접근할게

DFS 순회(전위/중위/후위)

• 접근 순서는 같지만 방문 순서는 다름(3가지)
• 전위 순회(자신부터 방문하고 자식노드 방문)
  

  def preorder(cur_node) :
      if cur_node is None:
      	return
      
      print(cur_node.value)
      preorder(cur_node.left)
      preorder(cur_node.right)
      
  preorder(root)

• 중위 순회(left node -> 자신 -> right node)
  

  def inorder(cur_node) :
      if cur_node is None:
      	return
      
      inorder(cur_node.left)
      print(cur_node.value)
      inorder(cur_node.right)
      
  inorder(root)​

• 후위 순회(자식노드 방문하고 자신 방문)
  

  def postorder(cur_node) :
      if cur_node is None:
      	return
      
      print(cur_node.value)
      postorder(cur_node.left)
      postorder(cur_node.right)
      
  postorder(root)

 

 

참고자료

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC