2. 이진 트리의 순회

순회 알고리즘은 다음과 같다.

전위 순회는 루트를 먼저 방문하고,

그 다음에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 마지막으로 방문하는 것이다. 

중위 순회는 먼저 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순으로 방문한다. 

후위 순회는 왼쪽 서브 트리, 오른쪽 서브 트리, 루트 순으로 방문한다.

 

그림으로 보자.

 

㉠. 전위 순회 : VLR 

㉡. 중위 순회 : LVR

㉢. 전위 순회 : LRV

 

이진 트리에서 각 각의 서브 트리도 이진 트리이다.

따라서, 서브 트리에서도 전체 이진 트리와 똑같은 방법을 적용할 수 있다.

즉, 전위 순회라면 서브 트리에 들어 있는 노드들도 VLR의 순서대로 순회된다.

트리 순회 알고리즘은 앞에서 한 순환 기법을 이용한다.

 

아래의 그림의 이진 트리에서 보면 전체 트리나 서브 트리나 그 구조는 완전히 동일하다.

따라서, 전체 트리 순회에 사용된 알고리즘은 똑같이 서브 트리에 적용할 수 있는 것이다.

다만 문제의 크기는 작아진다.

따라서, 재귀에서 보았듯이 문제의 구조는 같고, 크기만 작아지는 경우라면

재귀를 적용할 수 있다.

따라서, 전체 순회에 사용된 알고리즘을 다시 서브 트리에 적용하는 것이 가능해진다.

[그림 ]

아래는 각 순회들의 알고리즘 수도 코드이다.

 

트리 전위 순회 알고리즘 의사코드

트리 중위 순회 알고리즘 의사코드

 

트리 후위 순회 알고리즘 의사코드

 

아래는 프로그램 소스인데, BinaryTree의 헤더 파일과 소스 파일에

각 순회 함수만 추가하면 된다.

 

메인 함수

 

프로그램 결과

 

그리고 앞에서, 동적할당에 대한 해제가 없다고 하였다.

이는 순회 알고리즘을 이용해서, 함수로 만들 수 있다.

즉, 순회 중에서 후위 순회를 이용하면 된다. 루트 노드는 맨 마지막에 제거 한다.

 

메인 함수에서 프로그램을 종료하기 전에 DeleteTree 함수를 호출한다.

 

결과는 아래와 같다. 모든 노드들이 제거 되는 것을 볼 수 있다.

 

소스파일

BinaryTree.c

0.00MB

BinaryTree.h

0.00MB

common.h

0.00MB

main.c

0.00MB