[Python Algorithm] 완전탐색(DFS) - 이진트리 순회

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

 

 

 

 

이진트리의 전위순회와 후위순회 연습하기 (재귀를 통해 DFS 배우기)

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

 

 

전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1

 

 

import sys

def DFS(n):
	if n>7:
    	return
    else:
    	print(n, end=" ")	# **
        #	(1)
    	DFS(n*2)	# 왼쪽 자식 노드
        #	(2)
        DFS(n*2+1)	# 오른쪽 자식 노드
        #	(3)
    



DFS(1)

 

 

⭐️ Point ! ⭐️

• 전위순회는 자주 쓰임. 쓰임 빈도: 전위 > 후위 > 중위
  
  
• print(n, end=" ") 의 위치에 따라
  - 전위순회 : 출력문이 왼쪽,오른쪽 자식 노드 방문 전 (1)에 두면, 부모부터 부-> 왼-> 오
  - 중위순회 : (2)에 두면 왼쪽 자식 노드 방문하여 출력 후, 부모 출력, 오른쪽 자식 노드 출력,  왼-> 부-> 오
  - 후위순회 : (3)에 두면 부,왼은 그냥 방문 후, 오부터 출력하여 , 오 -> 왼 -> 부
  
  

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이