이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
(1) 이진 트리의 순회에 대한 강의를 듣기 전 고민
이진트리의 모든 노드를 탐색하는 것을 순회라고 하는데
한번 방법을 고민해보자.
level이 8개라면 탐색할 수 있는 루트가
left를 0 right를 1이라하면 2^8개
route노드 탐색 후
left 탐색 그다음 left left 탐색....
left left... left탐색 후 left left... right 탐색
이런 식으로 하면
강의에서는 재귀를 이용하면 된다고 설명하는데
재귀를 이용해서는 어떻게 할지 고민해보자.
순회가 아니라 탐색하는 코드를 짠 것 같은데 일단 내가 짠 코드는 다음과 같다.
BTreeNode* search(BTreeNode* bt, BTData data)
{
if(bt->data == data) return bt;
else if(bt->left == NULL && bt->right == NULL) return NULL;
else if(search(bt->left)) return serch(bt->left);
else if(search(bt->right)) return search(bt->right);
else return NULL;
}내 코드대로 하면 못 찾으면 NULL이 return된다.
찾으면 그 데이터가 저장되어 있는 노드의 주소가 return 된다.
탐색의 목적이 그 데이터가 저장된 노드의 주소를 찾는 것이라는 가정하에 짠 함수이다.
내 코드의 작동원리를 다음 이진 트리에서 6을 찾는다고 가정했을 때를 예로 들어 이해해보자.
그러나 문제가 있다.
search를 if문에서 한번, return문에서 한번 더 해서 시간 낭비를 매우 많이 한다.
친구의 조언을 얻어서 수정해보았는데
BTreeNode* Search(BTreeNode* bt, int data)
{
BTreeNode* temp;
if (bt == NULL) return NULL;
if (bt->data == data) return bt;
if (temp = Search(bt->left, data)) return temp;
else return Search(bt->right, data);
}이렇게 하면 search를 두번 연산할 필요가 없기 때문이다.
이제 혼자 고민을 많이 해봤으니 다시 강의로 돌아가겠다.
(2) 순회의 세가지 방법
1) 중위 순회 -> 왼쪽에서 중앙으로, 중앙에서 오른쪽으로 순히하는 방법
2) 후위 순회 -> 왼쪽에서 오른쪽으로, 오른쪽에서 중앙으로 순회하는 방법
3) 전위 순회 -> 중앙에서 왼쪽으로, 왼쪽에서 오른쪽으로 순회하는 방법
Tip
L R C 를 배치하는 방법은
LCR LRC CLR CRL RLC RCL 의 여섯가지이나 R과 L은 방법론상 구분되지 않으므로
L과 R을 S 즉, Side로 통일하면
SCS SSC CSS 로 세개의 방법이 되고 이 세개의 방법이 각각
중위순회, 후위순회, 전위순회이다
센터 즉, 루트 노드를 접근하는 시점에 따라 중위순회, 후위순회,전위순회라 이름을 붙였다.
모든 노드를 중위순회로 돌면 모든 노트를 순회할 수 있는데
내 코드가 바로 중위 순회를 이용한 탐색이다.
강의에서는 이를
void InorderTraverse(&TreeNode* bt)
{
InorderTraverse(bt->left);
printf("%d \n", bt->data);
InorderTraverse(bt->right);
}로 구현했는데 이는 아직 탈출조건이 명시되지 않은 불완전한 구현이다.
이 때 출력되는 순서는 (탈출 조건이 있다 가정시)
N L O C D R E 가 될 것이다.
탈출조건까지 완성하면
void InorderTraverse(BTreeNode* bt)
{
if(bt == NULL) return; //void이므로 아무것도 return하지 X
InorderTraverse(bt->left);
printf("%d \n", bt->data);
InorderTraverse(bt->right);
}위의 코드로 InorderTraverse를 짠 후
다음의 메인함수를 실행해보자.
#include <stdio.h>
#include "BinaryTree.h"
int main(void)
{
BTreeNode * bt1 = MakeBTreeNode();
BTreeNode * bt2 = MakeBTreeNode();
BTreeNode * bt3 = MakeBTreeNode();
BTreeNode * bt4 = MakeBTreeNode();
SetData(bt1, 1);
SetData(bt2, 2);
SetData(bt3, 3);
SetData(bt4, 4);
MakeLeftSubTree(bt1, bt2);
MakeRightSubTree(bt1, bt3);
MakeLeftSubTree(bt2, bt4);
printf("%d \n",
GetData(GetLeftSubTree(bt1)));
printf("%d \n",
GetData(GetLeftSubTree(GetLeftSubTree(bt1))));
InorderTraverse(bt1);
return 0;
}그러면 순서대로 2 4 4 2 1 3 이 출력된다.
(3) 전위 순회와 후위 순회
전위 순회 코드
void InorderTraverse(BTreeNode* bt)
{
if (bt == NULL) return;
printf("%d \n", bt->data);
InorderTraverse(bt->left);
InorderTraverse(bt->right);
}실행결과
후위 순회 코드
void InorderTraverse(BTreeNode* bt)
{
if (bt == NULL) return;
InorderTraverse(bt->left);
InorderTraverse(bt->right);
printf("%d \n", bt->data);
}실행 결과
