이진 트리의 순회 (전위, 중위, 후위 순회), 스레드 이진 트리

728x90

반응형

SMALL

전위 순회	D(현재 노드 방문 처리) → L(현재 노드의 왼쪽 서브 트리로 이동) → R(현재 노드의 오른쪽 서브 트리로 이동) 순서이다. 먼저 root 부터 방문 시작하여 현재 노드를 가장 먼저 수행하고 왼쪽 서브 트리 쪽 방문 후, 오른쪽 서브 트리 방문 순회하는 과정이다.
중위 순회	L(현재 노드의 왼쪽 서브 트리로 이동) → D(현재 노드 방문 처리)  → R(현재 노드의 오른쪽 서브 트리로 이동) 순서이다. 현재 노드를 방문하여 작업 D를 작업 L과 작업 R의 중간에 수행한다.
후위 순회	L(현재 노드의 왼쪽 서브 트리로 이동) → R(현재 노드의 오른쪽 서브 트리로 이동)  → D(현재 노드 방문 처리) 순서이다. 현재 노드를 방문하는 D 작업을 가장 나중에 수행한다.

---

이진 트리 순회(traversal)의 개념

모든 원소를 빠트리거나 중복하지 않고 처리하는 연산

○ 이진 트리가 순환적으로 정의되어 구성되어있으므로, 순회작업도 서브 트리에 대해서 순환적으로 반복하여 완성함

○ 왼쪽 서브 트리에 대한 순회를 오른쪽 서브 트리 보다 먼저 수행함

 

 

이진 트리의 순회를 위한 세부 작업

○ 작업 D : 현재 노드를 방문하여 처리한다.

○ 작업 L : 현재 노드의 왼쪽 서브 트리로 이동한다.

○ 작업 R : 현재 노드의 오른쪽 서브 트리로 이동한다.

 

순회의 종류

○ 전위 순회

○ 중위 순회

○ 후위 순회

---

전위 순회(Preorder Traversal)

D → L → R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행

 

이진 트리의 전위 순회 작업 순서

1. 작업 D : 현재 노드 n을 처리한다.

2. 작업 L : 현재 노드 n의 왼쪽 서브 트리로 이동한다.

3. 작업 R : 현재 노드 n의 오른쪽 서브 트리로 이동한다. 

 

---

전위 순회 예

수식 A*B-C/D를 이진 트리로 구성 

수식에 대한 이진 트리를 전위 순회하면, 전위 표기식을 구할 수 있음

---

중위 순회(Inoder Traversal)

L → D → R 순서로, 현재 노드를 방문하는 작업 D를 작업 L과 작업 R의 중간에 수행

 

이진 트리의 중위 순회 작업 순서

1. 작업 L : 현재 노드 n의 왼쪽 서브 트리로 이동한다.

2. 작업 D : 현재 노드 n을 처리한다.

3. 작업 R : 현재  노드 n의 오른쪽 서브 트리로 이동한다.

---

중위 순회 예

 

수식 A*B-C/D를 이진 트리로 구성

수식 이진 트리를 중위 순회하면, 수식에 대한 중위 표기식을 구할 수 있음

---

후위 순회 (Postorder Traversal)

L → R → D 순서로 현재 노드를 방문하는 D 작업을 가장 나중에  수행

 

이진 트리의 후위 순회 작업 순서

1. 작업 L : 현재 노드 n의 왼쪽 서브 트리로 이동한다.

2. 작업 R : 현재 노드 n의 오른쪽 서브 트리로 이동한다.

3. 작업 D : 현재 노드 n을 처리한다. 

---

후위 순회의 예

 

수식 A*B-C/D를 이진 트리로 구성

수식 이진 트리를 후위 순회하면, 수식에 대한 후위 표기식을 구할 수 있음

---

이진 트리 순회의 응용 프로그램

컴퓨터의 폴더 구조가 이진 트리 구조인 경우 각 폴더를 순회하면서 용량을 계산하면 내 컴퓨터의 전체 용량이 계산 가능함

○ 폴더 전체 용량은 폴더에 저장된 파일 용량과 하위 폴더의 용량을 합한 값

○ 상위 폴더 용량을 계산하려면 먼저 하위 폴더 용량을 계산해야 하므로 후위 순회를 사용

 

F4[프로그램] 전체 용량

= [프로그램]용량2MB  +  하위 폴더 용량(F8[C 프로그램]용량200MB  + F9[Java프로그램]용량100MB)

= 2MB+(200MB+100MB)

= 302MB

 

F2[C:￦] 전체 용량

= [C:￦]용량0MB  + 하위 폴더 용량(F4[프로그램]전체용량302MB  + F5[자료]용량15MB

= 0MB+(302MB+15MB)

= 317MB

 

....

---

스레드 이진 트리(Thread Binary Tree)

재귀호출 없이 순회할 수 있도록 수정한 이진 트리

재귀호출 방식은 알고리즘이나 함수 구현은 간단하지만, 수행 성능 측면에서는 시스템 스택을 사용하면서 호출과 복귀를 관리해야 하고 이진 트리의 하위 레벨로 내려갈수록 재귀호출 깊이가 깊어지므로 비효율적임

 

스레드 이진 트리에서 자식 노드가 없는 경우 링크 필드를 널 포인터 대신 순회 순서상의 다른 노드를 가리키도록 설정

이런 링크 필드를 스레드라고 한다. 

 

이진 트리 노드 구조에 isThread 필드를 추가하여 정의

isTread 필드는 링크 필드가 자식 노드에 대한 포인터인지 아니면 자식 노드 대신 스레드가 저장되어 있는지 구별하기 위한 태그 필드 

 

A*B-C/D 수식의 이진 트리에서 중위 순회를 한다면

왼쪽 스레드에는 선행자를 설정하고 오른쪽 스레드에는 후속자를 설정.

중위 순회 경로가 A → * → B → - → C → / → D 이므로 B의 선행자는 * 이고 B의 후속자는 -이다.

이런식으로 단말 노드에 NULL로 표현하지 않고 선행노드,후행노드가 누구인지 값을 표현한다.

순회를 위해서 후속자 정보만 필요한 경우에는

오른쪽 링크 필드만 스레드로 사용하는 스레드 이진 트리를 사용할 수 있음

---