이진 트리 순회
중위 순회(inorder traversal)
1) 더 이상 진행할 수 없을 때까지 왼쪽 방향으로 이동하여 내려간다.
2) 그 노드를 '방문'하고 오른쪽 자식 노드로 이동한 뒤 계속한다.
3) 이때 오른쪽으로 이동할 수 없을 때에는 한 노드 뒤로 되돌아간다.
void inorder(treePointer ptr) { /*중위 트리 순회*/ if (ptr) { inorder(ptr->leftChild); printf("%d", ptr->data); //왼쪽에서 리턴될때 프린트 inorder(ptr->rightChild); } }
inorder 처리 과정
반복 중위 순회(iterInorder)
void iterinorder(treePointer node)
{
int top = -1; /*스택 초기화*/
treePointer stack[MAX_STACK_SIZE];
for (;;) {
for (; node; node = node->leftChild)
push(node); /*스택에 삽입*/
node = pop();/*스택에서 삭제*/
if (!node)break; /*공백 스택*/
printf("%d", node->data);
node = node->rightChild;
}
}전위 순회(preorder traversal)
1) 노드를 먼저 방문하고 왼쪽으로 가서 계속한다.
2) 더 이상 계속할 수 없으면 오른쪽으로 이동하여 다시 시작하거나
3) 오른쪽으로 이동하여 순회를 계속할 수 있을 때까지 되돌아간다.
void preorder(treePointer ptr)
{ /*전위 트리 순회*/
if (ptr) {
printf("%d", ptr->data);
preorder(ptr->leftChild);
preorder(ptr->rightChild);
}
}preorder 처리 과정
후위 순회(postorder traversal)
1) 더 이상 내려 갈 수 없을 때 까지 왼쪽으로 내려간다.
2) 오른쪽으로 이동
void postorder(treePointer ptr)
{ /* 후위 트리 순회*/
if (ptr) {
postorder(ptr->leftChild);
postorder(ptr->rightChild);
printf("%d", ptr->data);
}
}
postorder 처리 과정
레벨 순서 순회(level order traversal)
반복적이거나 순환적으로 작성되든지 간에 중위,전위,후위 순회는 모두 스택을 필요로 한다.
그러나 레벨 순서 순회는 큐를 사용한다.
1) 루트를 먼저 방문한 다음 루트의 왼쪽 자식 방문
2) 루트의 오른쪽 자식 방문
3) 이러한 방법으로 각 새로운 레벨의 노드를 가장 왼쪽부터 가장 오른쪽까지 방문
void levelOrder(treePointer ptr)
{ /*레벨 순서 트리 순회*/
int front = rear = 0; //큐
treePointer queue[MAX_QUEUE - SIZE];
if (!ptr) return; /*공백 트리*/
addq(ptr);
for (;;) {
ptr = deleteq();
if (ptr) {
printf("%d", ptr->data);
if (ptr->leftChild) //왼쪽 자식 방문
addq(ptr->leftChild);
if (ptr->rightChild) //오른쪽 자식 방문
addq(ptr->rightChild);
}
else break;
}
}실습 예제 1
다음을 만족하는 Tree를 Linked Representation으로 구현하고 순회 결과를 출력하라.
1) 트리의 구조는 아래트리를 사용한다. 별도의 입력은 없다.
2) 교재 204페이지의 구조체를 이용하여 트리를 Linked Representation으로 구성한다.
3) 구성된 트리의 Preorder, Inorder, Postorder 순회를 하여 그 값을 출력한다.
4) 아래의 트리에 대해서도 동일하게 2)와 3)을 수행한다.
코드
/*
Description : Tree의 이진 트리 순회 -> inorder, preorder, postorder 순회
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct node *treePointer;
typedef struct node {
char data;
treePointer leftchild, rightchild;
}node;
/*왼쪽 가장 밑부터 넣어주기 후 부모로 이동*/
/* A
B C
D E F G
H I */
node A1 = { 'H',NULL,NULL };
node A2 = { 'I', NULL,NULL };
node A3 = { 'D',&A1,&A2 };
node A4 = { 'E',NULL,NULL };
node A5 = { 'B', &A3,&A4 };
node A6 = { 'F', NULL,NULL };
node A7 = { 'G' ,NULL,NULL };
node A8 = { 'C' ,&A6,&A7 };
node A9 = { 'A' ,&A5,&A8 };
node *root = &A9;
/* +
* E
* D
/ C
A B */
node B1 = { 'A',NULL,NULL };
node B2 = { 'B', NULL,NULL };
node B3 = { '/',&B1,&B2 };
node B4 = { 'C',NULL,NULL };
node B5 = { '*', &B3,&B4 };
node B6 = { 'D', NULL,NULL };
node B7 = { '*' ,&B5,&B6 };
node B8 = { 'E' ,NULL,NULL };
node B9 = { '+' ,&B7,&B8 };
node *root2 = &B9;
void inorder(treePointer);
void preorder(treePointer);
void postorder(treePointer);
int main()
{
printf("Preorder : ");
preorder(root);
printf("\n");
printf("Inorder : ");
inorder(root);
printf("\n");
printf("Postorder : ");
postorder(root);
printf("\n");
printf("Preorder : ");
preorder(root2);
printf("\n");
printf("Inorder : ");
inorder(root2);
printf("\n");
printf("Postorder : ");
postorder(root2);
printf("\n");
return 0;
}
void inorder(treePointer ptr)
{
if (ptr) {
inorder(ptr->leftchild);
printf("%c", ptr->data);
inorder(ptr->rightchild);
}
}
void preorder(treePointer ptr)
{
if (ptr) {
printf("%c", ptr->data);
preorder(ptr->leftchild);
preorder(ptr->rightchild);
}
}
void postorder(treePointer ptr)
{
if (ptr) {
postorder(ptr->leftchild);
postorder(ptr->rightchild);
printf("%c", ptr->data);
}
}출력 값
실습 예제 2
다음을 만족하는 Max Heap 프로그램을 구현하라.
1) Max Heap의 입력 데이터는 정수이며 파일(input.txt)로부터 입력받는다. 단, 정수의 갯수는 200개를 넘지 않는다고 가정한다.
2) 숫자를 차례대로 입력받아 배열을 이용하여 Max Heap을 구성한다.
즉, Array representation을 이용하여 Max Heap을 구현한다. (교재의 push()함수 참조)
3) 최종 구성된 Max Heap을 Level order와 Inorder로 각각 출력한다.
(Inorder 출력의 경우 교재의 iterInorder()함수 참조하여 재귀호출이 아닌 스택을 이용하여 구현)
4) Max Heap에서 하나를 제거하고 3)을 출력한다.
5) Max Heap에서 또 다른 하나를 제거하고 3)을 출력한다.
입력값
input1.txt
10 40 30 5 12 6 15 9 60
코드
/*
Description : 히프(HEAP) 이해하기 --> 최대 히프(MAX_HEAP)에서의 삽입과 삭제, 스택으로 중위 순회
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENTS 20
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
int Temp[MAX_ELEMENTS];
typedef struct {
int key;
}element;
element heap[MAX_ELEMENTS];
int stack[MAX_ELEMENTS];
void push(element);
element pop(element[]);
void open();
void print(int);
void iterinorder(); // 스택을 이용한 inorder
// void iterinorder_r(); /*재귀를 이용한 inorder*/
int count = 1; // heap 1부터 시작
int n = 0;
int main()
{
open();
printf("Level Order : "); print(count);
printf("\n");
printf("Inorder : "); iterinorder(); //iterinorder_r();
printf("\n");
pop(heap); count--;
printf("Level Order : "); print(count);
printf("\n");
printf("Inorder : "); iterinorder(); //iterinorder_r();
printf("\n");
pop(heap); count--;
printf("Level Order : "); print(count);
printf("\n");
printf("Inorder : "); iterinorder(); //iterinorder_r();
printf("\n");
return 0;
}
void open()
{
FILE *fp = fopen("input.txt", "r");
if (fp != NULL)
{
while ((fscanf(fp, "%2d", &Temp[count])) != EOF)
count++;
}
element item;
for (int i = 1; i < count; i++) {
item.key = Temp[i];
push(item);
}
}
void push(element item)
{
int i;
if (HEAP_FULL(n)) {
fprintf(stderr, "The heap is full\n");
exit(EXIT_FAILURE);
}
i = ++n;
while ((i != 1) && (item.key > heap[i / 2].key)) { //부모랑 비교후
heap[i] = heap[i / 2]; // 자식이 큰경우 부모랑 자식 바꿈
i /= 2; // 자식이였던 자리로 위치 이동
}
heap[i] = item; //비교 완료 후 자기 자리 이동
}
element pop(element heap[])
{
int parent, child;
element item, temp;
if (HEAP_EMPTY(n)) {
fprintf(stderr, "The heap is empty\n");
exit(EXIT_FAILURE);
}
item = heap[1];
temp = heap[(n)--];
parent = 1;
child = 2;
while (child <= n) {
if ((child < n) && heap[child].key < heap[child + 1].key) //현재부모보다 큰 자식 탐색
child++; //위로 올려줌 (root로 이동)
if (temp.key >= heap[child].key) break;
heap[parent] = heap[child]; //내려가면서 자기위치로
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
void print(int n)
{
int i;
for (i = 1; i < n; i++)
printf("%2d ", heap[i].key);
}
void iterinorder()
{
int i = 1;
int top = -1;
while (1) {
while (count > i) {
top++;
stack[top] = i;
i = i * 2;
}
if (top == -1)
return;
i = stack[top];
top--;
printf("%2d ", heap[i].key);
i = i * 2 + 1;
}
}출력 값
트리 관련 알고리즘