전위순회, 중위순회, 후위순회 개념 알아보기

✏️ 목표

트리의 구조를 알아보고 전휘순회, 중위순회, 후위순회 방식의 과정과 원리를 알아볼 것이다.

 

 

 

❓ 트리

📍 트리 구조와 DFS

출처: MyCloud (tistory.com)

- root node: 가장 상위에 있는 노드 

- 트리의 기본 단위: 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 이렇게 세 개가 한 묶음이다.

                               왼쪽 자식 노드와 오른쪽 자식 노드는 서로 형제(sibling) 관계이다.

ex) 2가 부모 노드라 하면 4는 2의 왼쪽 자식 노드, 5는 2의 오른쪽 자식 노드

- level: 루트 노드는 1 level, 아래로 내려갈수록 level이 증가한다.

 

DFS(깊이 우선 탐색)에서는 일반적으로 root node부터 시작하여 왼쪽부터 내려가면서 탐색한다.

그리고 가장 말단 node에 닿아 더 이상 내려가지 못하면 back을 하여 탐색하지 않은 node를 찾아가는 방식으로 이루어진다. 따라서 '재귀'를 사용하여 구현한다.

 

BFS(너비 우선 탐색)에서는 트리의 level 순으로 탐색하므로 '큐'를 이용하여 구현한다.

 

 

 

❓ 재귀를 이용한 트리 순회 방식 (DFS)

아래의 그림을 통해 구현해 보겠다.

 

📍 전위 순회 (preorder traverse)

함수 본연의 일을 가장 먼저 한 뒤 자기 자신을 호출하는 방식이다. 

항상 왼쪽 아래로 먼저 탐색하고 반환되는 값은 기본 단위 기준으로 부모 노드의 값 --> 왼쪽 자식 노드의 값 --> 오른쪽 자식의 노드의 값 순이다.

순회 방법 중에서 가장 흔하게 볼 수 있는 방법이다.

 

 

💻 전위 순회 python으로 구현하기

출력 결과가 아래와 같아야 한다.

 

# 전위 순회
1 2 4 5 3 6 7

 

1️⃣ 우선 어떤 과정으로 부모 노드의 값에서 자식 노드의 값을 얻을 수 있는지 보아야 한다.

root node값인 1에서 왼쪽 자식 노드의 값이 2이고, 2의 왼쪽 자식 노드 값이 4인 것을 볼 수 있다.

이를 통해 왼쪽으로 뻗는 가지는 부모 노드의 2배의 값을 가지게 된다는 것을 알 수 있다.

또, root node값인 1에서 오른쪽 자식 노드의 값이 3이고, 3의 오른쪽 자식 노드 값이 7인 것을 볼 수 있다.

이를 통해 오른쪽으로 뻗는 가지는 부모 노드의 2배 + 1의 값을 가지게 된다는 것을 알 수 있다.

 

2️⃣ 시작 조건과 종료 조건을 설정한다.

시작은 root node에서부터이므로 함수에 첫 번째로 들어가는 인자는 1이어야 한다.

재귀 함수의 종료 조건은 인자로 들어갈 값이 8 이상일 때이다. 이때마다 재귀를 종료하고 화면에 해당 값을 출력한다.

 

3️⃣ 코드 작성

항상 왼쪽으로 먼저 가지를 뻗어야 하고 끝에 다다렀을 때 값을 반환하고 오른쪽 자식을 탐색해야 한다.

 

def preorder(n):
	if n > 7:
    	return
    else:
    	print(n, end=' ')     # 함수 본연의 일을 처음에!
        preorder(n * 2)     # 왼쪽 
        preorder(n * 2 + 1)     # 오른쪽
        
preorder(1)

 

 

📍 후위 순회

왼쪽 자식과 오른쪽 자식 노드를 모두 탐색한 뒤 함수 본연의 일을 수행한다.

즉, 출력 순서는 왼쪽 자식 노드의 값 --> 오른쪽 자식 노드의 값 --> 부모 노드의 값 순이다.

후위 순회는 왼쪽과 오른쪽을 쪼개어 병합하면서 정렬하는 '병합 정렬'에 쓰인다. 항상 위와 같은 순서로 처리되기 때문이다.

 

 

💻 후위 순회 python으로 구현하기

출력 결과가 아래와 같아야 한다.

 

4 5 2 6 7 3 1

 

def postorder(n):
	if n > 7:
    	return;
    else:
    	postorder(n * 2)     # 왼쪽 (항상 왼쪽 먼저)
        postorder(n * 2 + 1)     # 오른쪽
        print(n, end=' ')     # 함수 본연의 일을 마지막에!
     
postorder(1)

 

 

📍 중위 순회

왼쪽 자식을 탐색한 뒤 함수 본연의 일을 수행하고 나서 오른쪽 자식을 탐색한다.

즉, 출력 순서는 왼쪽 자식 노드의 값 --> 오른쪽 자식 노드의 값 --> 부모 노드의 값 순이다.

 

 

💻 중위 순회 python으로 구현하기

 

def inorder(n):
	if n > 7:
    	return
    else:
    	inorder(n * 2)     # 왼쪽
        print(n, end=' ')     # 함수 본연의 일을 중간에!
        inorder(n * 2 + 1)     # 오른쪽
        
inorder(1)

 

 

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의