HISTORY

#include <stdio.h>
#define MAX_ELEMENT 200

typedef struct {
 int key;
} element;

typedef struct {
 element heap[MAX_ELEMENT];
 int heap_size;
} HeapType;

init(HeapType *h)           //초기화
{
 h->heap_size = 0;
}

void insert_max_heap(HeapType *h, element item)          //삽입
{
 int i;
 i = ++(h->heap_size);

 while((i != 1) && (item.key >h->heap[i/2].key)) {
  h->heap[i] = h->heap[i/2];
  i/=2;
 }
 h->heap[i] = item;
}

element delete_max_heap(HeapType *h)        //삭제
{
 int parent, child;
 element item, temp;

 item = h->heap[1];
 temp = h->heap[(h->heap_size)--];
 parent = 1;
 child = 2;

 while(child <= h->heap_size) {
  if((child < h->heap_size) && (h->heap[child].key) < h->heap[child+1].key) child++;
  if(temp.key >= h->heap[child].key) break;

  h->heap[parent] = h->heap[child];
  parent = child;
  child *= 2;
 }
 h->heap[parent] = temp;
 return item;
}

void main(void)
{
 element e1 = {10}, e2 = {5}, e3 = {30};
 element e4, e5, e6;

 HeapType heap;

 init(&heap);

 insert_max_heap(&heap, e1);
 insert_max_heap(&heap, e2);
 insert_max_heap(&heap, e3);

 e4 = delete_max_heap(&heap);
 printf("<%d> ", e4.key);
 e5 = delete_max_heap(&heap);
 printf("<%d> ", e5.key);
 e6 = delete_max_heap(&heap);
 printf("<%d>\n", e6.key);
}

//이진 탐색 트리를 이용한 영어 사전 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

#define MAX_WORD_SIZE 100
#define MAX_MEANING_SIZE 200

//데이터형식 <- key
typedef struct {
 char word[MAX_WORD_SIZE];
 char meaning[MAX_MEANING_SIZE];
} element;
//노드의구조
typedef struct TreeNode {
 element key;
 struct TreeNode *left, *right;
} TreeNode;

//  키값 비교

//  e1  >  e2    => -1 반환

//  e1 == e2   => 0  반환

//  e1  <  e2    => 1  반환

int compare(element e1, element e2)
{
 return strcmp(e1.word, e2.word);
}
//출력
void display(TreeNode *p)
{                                                             //p가 null일때의 처리없음
 if(p!=NULL) {
  printf("(");
  display(p->left);              //왼쪽 서브 트리로 재귀
  printf("%s", p->key.word);
  display(p->right);            //오른쪽 서브트리로 재귀
  printf(")");
 }
}
//탐색
TreeNode *search(TreeNode *root, element key)
{
 TreeNode *p = root;
 while(p!=NULL) {
  switch(compare(key, p->key)) {
  case -1:
   p = p->left;
   break;
  case 0:
   return p;
  case 1:
   p=p->right;
   break;
  }
 }
 return p;
}
//삽입
void insert_node(TreeNode **root, element key)
{
 TreeNode *p, *t;
 TreeNode *n;

 t=*root;
 p=NULL;
//탐색수행
 while(t!=NULL) {
  if(compare(key, t->key)==0) return;
  p=t;
  if(compare(key, t->key)<0) t=t->left;
  else t=t->right;
 }
//item이 없으므로 삽입가능
 n=(TreeNode *)malloc(sizeof(TreeNode));
 if(n==NULL) return;
//데이터 복사
 n->key = key;
 n->left = n->right = NULL;
//부모노드와 링크 연결
 if(p!=NULL)
  if(compare(key, p->key)<0)
   p->left = n;
  else p->right = n;
 else *root = n;
}
//삭제
void delete_node(TreeNode **root, element key)
{
 TreeNode *p, *child, *succ, *succ_p, *t;

 p=NULL;
 t=*root;

 while(t != NULL && compare(key, t->key)!=0) {
  p=t;
  t=(compare(key, t->key)<0) ? t->left : t->right;
 }

 if(t==NULL) {
  printf("key is not in the tree");
  return;
 }
//단말노드
 if((t->left == NULL) && (t->right == NULL)) {
  if(p!=NULL) {
   if(p->left == t) p->left =NULL;
   else p->right = NULL;
  }
  else *root = NULL;  //부모노드가 없으면 노드
 }
//하나의 자식노드
 else if((t->left == NULL) || (t->right == NULL)) {
  child = (t->left != NULL) ? t->left : t->right;

  if(p != NULL) {
   if(p->left == t) p->left = child; //부모노드를 자식노드와 연결
   else p->right = child;
  }
  else *root = child;
 }
//두개의 자식노드
 else { 
  succ_p = t;
  succ = t->right;  //오른쪽 서브트리에서 후속자를 찾는다

  while(succ->left !=NULL) {
   succ_p = succ;
   succ = succ->left;   //후속자를 찾아서 왼쪽으로 계속 이동
  }
//후속자의 부모와 자식을 연결
  if(succ_p->left == succ) succ_p->left = succ->right;
  else succ_p->right = succ->right;
//후속자를 현재 노드로 이동
  t->key = succ->key;
  t=succ;
 }
 free(t);
}
//목차
void help()
{
 printf("***************\n");
 printf("i : 입력 \n");
 printf("d : 삭제 \n");
 printf("s : 탐색 \n");
 printf("p : 출력 \n");
 printf("q : 종료 \n");
 printf("***************\n");
}
//메인
void main()
{
 char command;
 element e;
 TreeNode *root = NULL;
 TreeNode *tmp;

 do {
  help();
  command = getchar();
  fflush(stdin);   //버퍼에 남은 \n을 제거
                              //stdin : Standard Input ( 기본 입력 스트림 )

  switch(command) {
  case 'i':
   printf("단어: ");
   gets(e.word);
   printf("의미: ");
   gets(e.meaning);
   insert_node(&root, e);
   break;
  case 'd':
   printf("단어: ");
   gets(e.word);
   delete_node(&root, e);
   break;
  case 'p':
   display(root);
   printf("\n");
   break;
  case 's':
   printf("단어: ");
   gets(e.word);
   tmp=search(root, e);
   if(tmp!=NULL) printf("의미: %s\n", tmp->key.meaning);
   break;
  }
 }while(command != 'q');
}

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
 int data;
 struct TreeNode *left, *right;
} TreeNode;

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, NULL, NULL};
TreeNode n3 = {'*', &n1, &n2};
TreeNode n4 = {16, NULL, NULL};
TreeNode n5 = {25, NULL, NULL};
TreeNode n6 = {'+', &n4, &n5};
TreeNode n7 = {'+', &n3, &n6};
TreeNode *exp = &n7;

int evaluate(TreeNode *root)
{
 if(root == NULL)
  return 0;
 if(root->left == NULL && root->right == NULL)
  return root->data;
 else {
  int op1 = evaluate(root->left);
  int op2 = evaluate(root->right);

  switch(root->data) {
  case '+' :
   return op1+op2;
   case '-' :
   return op1-op2;
   case '*' :
   return op1*op2;
   case '/' :
   return op1/op2;
  }
 }
 return 0;
}

void main()
{
 printf("%d\n", evaluate(exp));
}

1) 전위 순회 - 루트 > 왼쪽 서브트리 > 오른쪽 서브트리를 차례로 방문.

                      - 1. 노드가 NULL이면 더이상 순환 호출을 하지 않는다.

                      - 2. 노드의 데이터를 출력한다.

                      - 3. 노드의 왼쪽 서브트리를 순환 호출하여 방문한다.

                      - 4. 노드의 오른쪽 서브트리를 순환 호출하여 방문한다.

preorder(TreeNode *root) {
 if(root) {
  printf("%d ", root->data);
  preorder(root->left);
  preorder(root->right);
 }
}

2) 중위 순회 - 왼쪽 서브트리 > 루트 > 오른쪽 서브트리

inorder(TreeNode *root) {
 if(root) {
  inorder(root->left);
  printf("%d ", root->data);
  inorder(root->right);
 }
}

3) 후위 순회 - 왼쪽 서브트리의 모든 노드 > 오른쪽 서브트리의 모든 노드 > 루트노드

postorder(TreeNode *root) {
 if(root) {
  postorder(root->left);
  postorder(root->right);
  printf("%d ", root->data);
 }
}

*링크법으로 생성된 이진트리 - 순회

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
 int data;
 struct TreeNode *left, *right;
} TreeNode;

TreeNode n1 = { 1, NULL, NULL };        //노드의 정적 생성(malloc를 사용하지 않는것)
TreeNode n2 = { 4, &n1, NULL };         //노드를 간편하게 만들수 있으나 노드개수가 한정되어 있다.
TreeNode n3 = { 16, NULL, NULL };      //실제로는 잘 사용되지 않는다고 한다.
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode *root = &n6;

inorder(TreeNode *root)             //전위순회

{
 if(root) {
  inorder(root->left);
  printf("%d ", root->data);
  inorder(root->right);
 }
}

preorder(TreeNode *root)          //중위순회

{
 if(root) {
  printf("%d ", root->data);
  preorder(root->left);
  preorder(root->right);
 }
}

postorder(TreeNode *root)           //후위순회

{
 if(root) {
  postorder(root->left);
  postorder(root->right);
  printf("%d ", root->data);
 }
}

void main()
{
 inorder(root);
 printf("\n");
 preorder(root);
 printf("\n");
 postorder(root);
 printf("\n");
}

4) 레벨순회

- 각 노드를 레벨 순으로 검사한다.

- 동일한 레벨일 때는 좌->우로 방문한다.

- 큐를 사용하는 순회법이다.

*트리 레벨 순회 알고리즘

level_order(root)

{

  initialize queue;                                             //큐 초기화

    enqueue(queue, root);                              //루트 노드를 큐에 삽입

    while is_empty(queue) != TRUE do          //큐가 공백이 될때까지 계속 다음을 반복한다.

      x <- dequeue(queue);                             //큐 맨처음에 있는 노드 x를 꺼내온다.

      if(x != NULL)                                                //x가 NULL이 아니면

        then print  x->data;                                 //x의 데이터값을 출력하고

                 enqueue(queue, x->left);             //x의 왼쪽 자식을 큐에 삽입

                 enqueue(queue, x->right);           //x의 오른쪽 자식을 큐에 삽입

}