10-2 이진 트리 순회의 개념

1. 이진 트리 순회의 개념

① 개념

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

2. 이진 트리 순회

① 이진 트리 순회

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

② 전위 순회

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

③ 중위 순회

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

④ 후위 순회

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

3. 이진 트리 순회의 응용

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

  - 컴퓨터 폴더 구조가 이진 트리 구조인 경우, 각 폴더 순회하면서 용량 계산하면

     내 컴퓨터의 전체 용량 계산 가능함.

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

 

② 스레드 이진 트리

  - 재귀 호출 없이 순회할 수 있도록 수정한 이진 트리(하위 내려갈수록 재귀 호출이 비효율적이므로)

  - 스레드 : 스레드 이진 트리에서 자식 노드가 없는 경우,

                  링크 필드를 널포인터 대신 순회 순서상의 다른 노드 가리키도록 설정

  - 순회를 위해서 후속자 정보만 필요한 경우, 오른쪽 링크 필드만 스레드로 사용하는 스레드 이진 트리 사용할 수 있다.