Language 자료구조 Part9. "트리" - 트리의 순회 - 이진 트리의 순회.

자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
 
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
 
 
Part9 트리 - 트리의 순회 - 이진 트리의 순회.
--------------------------------------
 
트리의 순회.
 
순회 : 여러 곳을 돌아다님.
 
트리에서 자료를 사용하려면, 또는 검색하려면 순회 라는 것을 해야 한다.
 
순회란 트리의 모든 노드를 한번씩 훑어보는 것 (방문 이란 말을 자주 쓴다.) 인데,
 
기초적인 서브트리에서 트리의 순회하는 방법은 3! = 3 x 2 x 1 = 6 가지가 있다.

1. 위 - 왼쪽 - 오른쪽 / 2. 위 - 오른쪽 - 왼쪽
3. 왼쪽 - 위 - 오른쪽 / 4. 왼쪽 - 오른쪽 - 위
5. 오른쪽 - 위 - 왼쪽 / 6. 오른쪽 - 왼쪽 - 위
 
이 중에서, 반드시 왼쪽을 오른쪽보다 먼저 순회한다면,
1, 3, 4 의 3가지 방법만 남게 되는데, 이를 각각 전위순회, 중위순회, 후위순회 라고 한다.
(루트의 방문 위치에 따라 이름을 붙인다.)
 
(왜 왼쪽을 오른쪽보다 먼저 순회하는 방법만 이름을 붙이고 자주 사용하는지는 잘 모르겠습니다.
혹시 알고 계시다면 연락주세요~ ^^)
 
전위 순회(PreOrder)는 루트를 먼저 방문하고 좌우를 각각 방문하며
중위 순회(InOrder)는 왼쪽을 방문하고 루트를 중간에 방문하며 마지막에 오른쪽을 방문하는 방식이며.
후위 순회(PostOrder)는 왼쪽을 방문, 오른쪽을 방문하고 마지막에 루트를 방문하는 방식이다.
//=*먼저 이 3가지 순회를 알아본 뒤, 또다른 순회인 층별순회(LevelOrder)를 알아보자.=//

 
하지만, 자식이 부모여서, 즉, B 나 C 가 또다른 자식을 가지고 있다면
 
그 자식을 먼저 순회해야 하기 때문에 트리의 순회는 보통 재귀함수를 사용한다
(전위순회를 예로, 왼쪽 자식을 순회하고 다시 자기자신으로 돌아온 뒤,
 오른쪽 자식을 순회해야 하므로 순회했던 순서의 반대로 자기 자신에(Root)게 다시 돌아와야 한다는 것
 때문에 재귀적인 호출이 필요하다.)
 
소스는 아래와 같다.
//시작--------------------이 줄은 소스에 포함되지 않습니다.

·미리보기 | 소스복사·

1. #include<stdio.h>   
2. #include<stdlib.h>   
3. struct Node   
4. {   
5.      int data;   
6.      Node *left;   
7.      Node *right;   
8. };   
9. Node *Root;   
10.     
11. void InitTree(int data)   
12. {   
13.      Root=(Node *)malloc(sizeof(Node));   
14.      Root->data=data;   
15. }   
16.     
17. Node *AddChild(Node *Parent,int data,BOOL bLeft)   
18. {   
19.      Node *New;   
20.     
21.      New=(Node *)malloc(sizeof(Node));   
22.      New->data=data;   
23.      New->left=NULL;   
24.      New->right=NULL;   
25.      if (bLeft) {   
26.           Parent->left=New;   
27.      } else {   
28.           Parent->right=New;   
29.      }   
30.      return New;   
31. }   
32.     
33. void PreOrder(Node *R)   
34. {   
35.      printf("%d ",R->data);   
36.      if (R->left) PreOrder(R->left);   
37.      if (R->right) PreOrder(R->right);   
38. }   
39.     
40. void InOrder(Node *R)   
41. {   
42.      if (R->left) InOrder(R->left);   
43.      printf("%d ",R->data);   
44.      if (R->right) InOrder(R->right);   
45. }   
46.     
47. void PostOrder(Node *R)   
48. {   
49.      if (R->left) PostOrder(R->left);   
50.      if (R->right) PostOrder(R->right);   
51.      printf("%d ",R->data);   
52. }   
53.     
54. void FreeTree(Node *R)   
55. {   
56.      if (R->left) FreeTree(R->left);   
57.      if (R->right) FreeTree(R->right);   
58.      free(R);   
59. }   
60.     
61. void main()   
62. {   
63.      Node *Left,*Right;   
64.     
65.      InitTree(1);   
66.      Left=AddChild(Root,2,TRUE);   
67.      Right=AddChild(Root,3,FALSE);   
68.      AddChild(Left,4,TRUE);   
69.      AddChild(Left,5,FALSE);   
70.      AddChild(Right,6,TRUE);   
71.     
72.      PreOrder(Root);puts("");   
73.      InOrder(Root);puts("");   
74.      PostOrder(Root);puts("");   
75.     
76.      FreeTree(Root);   
77. }  

//끝--------------------이 줄은 소스에 포함되지 않습니다.
자, 소스를 분석해 보면,
 
먼저, 노드의 구조체를 선언했고, Root 노드는 먼저 선언 해 준다.
 
1. void InitTree(int data)
 큐와 스택과 마찬가지로 init 는 트리를 초기화 한다.
 선언한 루트에 메모리를 부여하며 data를 넣는다.
 
2. *AddChild(Node *Parent,int data,BOOL bLeft)
 이 함수는 연결리스트와 상당히 비슷한데,
 마지막 인수인 bLeft에 따라 왼쪽, 또는 오른쪽에 자식을 만들어서 부모와 연결한다.
 마찬가지로 노드의 값을 data로 지정한다.
 
메인 함수에선 맨 처음 루트의 값을 1로 지정했으며, 그 뒤로 자식노드를 만들어 내는 함수를 호출한다.
 
실행 후 트리의 구조는 그림과 같다.

이렇게 만들어진 트리를 세 가지 방법으로 순회하면서 데이터를 출력하는데
대표적으로 루트를 먼저 방문하는 PreOrder 함수를 보자.
 
루트를 우선적으로 처리해야 하므로 자신의 데이터를 printf 함수로 먼저 출력했다.
 
여기서 printf 함수 호출은 순회중에 하고자 하는 작업에 해당하는데
하려는 짓이 검색이라면 data를 비교하고, 삭제라면 노드 제거 함수를 호출하면 될 것이다.
 
그리고 루트의 왼쪽, 오른쪽 각각을 출력하되 각 차일드들이 또 다른 서브 트리일 수도 있으므로 이 서브 트리에 대해서도 PreOrder 함수를 호출하여 차일드의 루트부터 모든 차일드를 출력하도록 해야 한다.
 
그래서 자신을 다시 호출하는 재귀 호출 구조를 가지고 있다.
 
위 그림에서 1을 출력할 때 왼쪽 차일드 2가 또 다른 서브 트리이므로 2에 대해서도 PreOrder 함수를 호출하였다.
 
PreOrder(2) 호출은 자신을 먼저 출력하고 또 4, 5번 자식에 대해 전위 순회를 하되 4, 5는 모두 차수가 0인 잎 노드이므로 더 이상 재귀를 하지 않고 자신만 출력한 후 리턴할 것이다.
 
2번 서브 트리의 출력이 끝나면 다음번 호출인 PreOrder(3)이 호출되어 오른쪽 서브 트리가 출력된다.
 
각 서브 트리에 대해 루트와 차일드를 모두 거치므로 트리의 모든 노드를 순회하게 된다.
 
중위 순회하는 InOrder, 후위 순회하는 PostOrder 함수도 루트를 처리하는 순서만 다를 뿐 재귀 구조는 동일하다.
 
재귀 호출을 사용하지 않으려면 자식 노드로 내려 가기 전에 스택에 돌아올 번지를 푸시하면서 순회하는 방법을 사용할 수도 있다.
 
그러나 트리는 자료 구조 자체가 재귀적이기 때문에 재귀 호출을 사용하는 것이 가장 자연스럽다.
 
main에서는 세 방법으로 순회한 결과를 출력하는데 순서가 틀릴 뿐이지 결국 모든 노드를 한 번씩 방문한다.

 
1 2 4 5 3 6 //전위
4 2 5 1 6 3 //중위
4 5 2 6 3 1 //후위
 
 생성한 트리를 해제하는 FreeTree 함수는 각 노드를 해제하되 자식 노드를 먼저 해제한 후 루트를 해제해야 하므로 후위 순회법을 사용한다.
 
루트를 먼저 해제하면 자식 노드를 알 수 없게 되므로 후위 순회가 적합하다.
 
----------
층별순회 (LevelOrder).
 
층별순회는 가장 쉬운 순회방법 중 하나인데,
 
말 그대로 윗층부터 순서대로 출력해 내는 것이다.
(레벨이 낮은 노드부터 차례로 방문한다)
 
전위, 중위, 후위 순회는 일단 주어진 서브 트리를 먼저 완전히 방문한 후 다음 서브 트리를 찾지만 레벨별 순회는 서브 트리를 기준으로 하지 않고 레벨을 기준으로 하므로 재귀 호출을 사용하지 않는다.
 
대신 노드를 만날 때마다 자신을 출력한 후 자신의 자식들을 차례대로 큐에 밀어 넣어 직계 자식들이 우선적으로 처리되도록 한다.
 
층별 순회를 하기위해선, 큐 기법을 사용할 줄 알아야 한다.
 
층별순회는 Root 부터, 자신을 큐에 넣고, 자신을 빼낼 때 자신의 자식을 넣는다.
그 후 큐 방식인 맨 처음의 노드를 빼내면서 그 노드의 자식이 있다면 자식을 큐에 넣는다.
 
이 방법을 반복하게 된다.

(그림이 잘 보이지 않으니 클릭해서 보세요~ ^^)
직감이 올 것이다.
 
왜 맨 앞의 데이타를 빼내냐고 묻는다면, 큐 이니까.
FIFO방식을 따라 순서대로 진행하면, 위의 순서대로 1 2 3 4 5 6 , 즉 레벨별로 순회가 완료 된다.
 
소스는 다음과 같다.
//시작---------------------이 줄은 소스에 포함되지 않습니다.

·미리보기 | 소스복사·

1. #include<stdio.h>   
2. #include<stdlib.h>   
3. struct Node   
4. {   
5.      int data;   
6.      Node *left;   
7.      Node *right;   
8. };   
9. Node *Root;   
10.     
11. Node **Queue;   
12. int QSize;   
13. int head,tail;   
14.     
15. void InitQueue(int size)   
16. {   
17.      QSize=size;   
18.      Queue=(Node **)malloc(QSize*sizeof(Node *));   
19.      head=tail=0;   
20. }   
21.     
22. void FreeQueue()   
23. {   
24.      free(Queue);   
25. }   
26.     
27. BOOL Insert(Node *data)   
28. {   
29.      if ((tail+1) % QSize == head) {   
30.           return FALSE;   
31.      }   
32.      Queue[tail]=data;   
33.      tail=(tail+1) % QSize;   
34.      return TRUE;   
35. }   
36.     
37. Node *Delete()   
38. {   
39.      Node *data;   
40.     
41.      if (head==tail) {   
42.           return NULL;   
43.      }   
44.      data=Queue[head];   
45.      head=(head+1) % QSize;   
46.      return data;   
47. }   
48.     
49. void InitTree(int data)   
50. {   
51.      Root=(Node *)malloc(sizeof(Node));   
52.      Root->data=data;   
53. }   
54.     
55. Node *AddChild(Node *Parent,int data,BOOL bLeft)   
56. {   
57.      Node *New;   
58.     
59.      New=(Node *)malloc(sizeof(Node));   
60.      New->data=data;   
61.      New->left=NULL;   
62.      New->right=NULL;   
63.      if (bLeft) {   
64.           Parent->left=New;   
65.      } else {   
66.           Parent->right=New;   
67.      }   
68.      return New;   
69. }   
70.     
71. void FreeTree(Node *R)   
72. {   
73.      if (R->left) FreeTree(R->left);   
74.      if (R->right) FreeTree(R->right);   
75.      free(R);   
76. }   
77.     
78. void LevelOrder(Node *R)   
79. {   
80.      Node *tNode;   
81.     
82.      Insert(R);   
83.      while (head != tail) {   
84.           tNode=Delete();   
85.           printf("%d ",tNode->data);   
86.           if (tNode->left) Insert(tNode->left);   
87.           if (tNode->right) Insert(tNode->right);   
88.      }   
89. }   
90.     
91. void main()   
92. {   
93.      Node *Left,*Right;   
94.     
95.      InitQueue(128);   
96.      InitTree(1);   
97.      Left=AddChild(Root,2,TRUE);   
98.      Right=AddChild(Root,3,FALSE);   
99.      AddChild(Left,4,TRUE);   
100.      AddChild(Left,5,FALSE);   
101.      AddChild(Right,6,TRUE);   
102.     
103.      LevelOrder(Root);puts("");   
104.     
105.      FreeTree(Root);   
106.      FreeQueue();   
107. }  

//끝---------------------이 줄은 소스에 포함되지 않습니다.
큐를 써야 하기 때문에
큐에서 따온 initQueue, insert(put), delete(get) 등 큐에서 쓰던 함수도 있다.
 
 
이상으로 트리의 기본적인 용어와 많이 사용되는 이진 트리의 모양, 생성하는 방법, 그리고 순회하는 방법에 대해 알아보았다.
 
다소 이론적인 내용만 다루었고 실무에 바로 적용할 수 있을만한 내용은 없는 셈인데 트리는 워낙 형태가 변화 무쌍해서 적용되는 알고리즘에 따라 구현 방법이 다양하므로 여기서 응용을 다루기는 어렵다.
 
-WinAPI의 글을 초보자가 쉽게 공부할 수 있도록 재작성 한 글 입니다.
 
ps. 다음은 수식트리에 대해 공부해 봅시다~
---------------
-순회 이해하기.-
ex) 다음 트리를 4가지 방법으로 순회했을때 결과는?

정답:
전위순회: A B D F C E
중위순회: B D F A E C
후위순회: F D B E C A
레벨순회: A B C D E F
----------------
선린 인터넷 고등학교 20420 전호근