[Python-CodingTest] 6-2. 이진트리 순회 (DFS: 깊이우선탐색)

이진트리 순회

문제 정리

처리 과정

전위순회

1. 노드의 값이 7보다 크면 재귀 종료
2. DFS 함수 본연의 일
3. 왼쪽 자식노드(DFS(v*2)) 방문
4. 오른쪽 자식노드(DFS(v*2+1)) 방문

출력

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

풀이

def DFS(v): # 파라미터: 노드값
    if v>7:
        return
    else:
        # 전위순회
        print(v, end=' ') # DFS 함수 본연의 일
        DFS(v*2) # 왼쪽 자식노드
        DFS(v*2+1) # 오른쪽 자식노드

        # 중위 순회
        # DFS(v*2) 
        # print(v, end=' ') 
        # DFS(v*2+1) 

        # 후위 순회 
        # DFS(v*2)
        # DFS(v*2+1) 
        # print(v, end=' ') 

if __name__=="__main__": 
    DFS(1)

정리

• 전위순회

  1. 함수 본연의 일 (예시에서는 print())
     
  2. 왼쪽 자식노드 방문
     
  3. 오른쪽 자식노드 방문

• 중위순회

  1. 왼쪽 자식노드 방문
     
  2. 함수 본연의 일 (예시에서는 print())
     
  3. 오른쪽 자식노드 방문

• 후위순회

  1. 왼쪽 자식노드 방문
     
  2. 오른쪽 자식노드 방문
     
  3. 함수 본연의 일 (예시에서는 print())

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기