[알고리즘 스터디] 자료구조_2

1.트리, 그래프

비선형 구조
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다.

트리

• 트리의 구성 요소

  • Root Node : 트리 구조에서 최상위에 존재하는 노드 (A)
  • Node : 트리의 구성요소에 해당하는 요소 (A,B,C,D,E,F,G)
  • Edge : 노드와 노드를 연결하는 선
  • Terminal Node(Leaf Node) : 트리의 맨 밑에 있는 자식을 가지지 않는 노드
  • Sub-Tree : 전체 트리에 속하는 작은 트리
  • Level : 트리에서 각 층별로 숫자를 매김 (root node = level 0)
  • Height : 트리의 최고 레벨

• 트리의 종류

  • 이진트리 (binary tree)

    어떤 한 노드가 2개 이하의 자식만을 가지는 트리

  • 포화이진트리 (perfect binary tree)

    leaf를 제외한 모든 노드가 2개의 자식을 가지는 트리

    • 높이가 d인 포화이진트리의 노드 수
      2^(d+1)-1

  • 완전이진트리 (complete binary tree)

    포화이진트리에서 leaf를 오른쪽부터 제거하여 얻는 트리
    위에서부터 순서대로 꽉 채워진 모양이다

    • 높이가 h인 완전이진트리의 노드 수는 2^h 이상 2^(h+1)이하이다.

• 구현

  • 노드의 구조

• 주로 연결리스트 혹은 배열로 구현한다.

• 필요한 함수
  • Create: 새로운 트리를 만들기
  • Destroy: 사용되던 트리를 파기하기
  • Insert: 트리에 새로운 노드를 삽입하기
  • Delete: 트리의 특정 노드를 삭제하기
  • Search: 주어진 키를 가진 노드 레코드를 검색하기
  • IsEmpty: 빈 트리인지를 확인하기
  • CopyTree: 주어진 트리를 복사하기
  • Traverse: 트리 내부 노드를 하나씩 순회하기

이진탐색트리의 구현

• 원소 크기에 따라 노드 위치를 정의한 이진트리

#include <stdio.h>
#include <stdlib.h>
//부모노드 인덱스 i/2
//왼쪽자식 인덱스 2i
//오른쪽 자식 인덱스 2i+1

typedef struct TreeNode { //구조체  
    int key;
    struct TreeNode *left,*right;
}TreeNode; 

//전위 순회
preorder(TreeNode *root) {
    if(root){
        printf("%d ",root->key);
        preorder(root->left);
        preorder(root->right);
    }

}
//중위 순회
inorder(TreeNode *root) {
    if(root){
        inorder(root->left);
        printf("%d ",root->key);
        inorder(root->right);
    }
} 
//후위 순회
postorder (TreeNode *root) {
    if(root){
        postorder(root->left);
        postorder(root->right);
        printf("%d ",root->key);
    }
} 
//탐색  
TreeNode *search(TreeNode *node,int key) {
    while(node!=NULL){
        if(key==node->key) return node;
        else if(key<node->key)
            node=node->left;
        else 
            node=node->right;
    }
    return NULL; // 탐색 실패한 경우  
}
//노드 삽입  
void insert_node(TreeNode **root, int key) {
   TreeNode *parent, *t;
   TreeNode *new;

   t = *root;
   parent = NULL;
   while (t != NULL) {
      if (key == t->key)
         return;
      parent = t;
      if (key < t->key)
         t = t->left;
      else
         t = t->right;
   }
   new = (TreeNode *)malloc(sizeof(TreeNode));
   if (new == NULL)
      return;
   new->key = key;
   new->left = new->right = NULL;
   if (parent != NULL)
      if (key < parent->key)
         parent->left = new;
      else
         parent->right = new;
   else
      *root = new;
}
//노드 삭제  
void delete_node(TreeNode **root,int key) {
    TreeNode *parent,*child,*suc,*suc_parent,*t;

    parent = NULL;
    t=*root;
    while(t != NULL && t->key != key) {
        parent = t;
        t=(key<parent->key) ? parent->left : parent->right ;
    }
    if (t==NULL) {
        printf("탐색 실패\n");
        return;
    }
    //단말 노드인 경우 
    if((t->left==NULL)&&(t->right==NULL))
        if(parent != NULL)
            if(parent->left==t)
                parent->left=NULL;
            else
                parent->right=NULL;
        else
            *root=NULL;

    //하나의 자식만 가지는 경우 
    else if((t->left==NULL)||(t->right==NULL)) {
        child = (t->left != NULL) ? t->left : t->right;
        if(parent != NULL)
            if(parent->left==t)
                parent->left=child;
            else
                parent->right=child;
        else
            *root=child;
    }
    //두 개의 자식을 가지는 경우 
    else {
        //오른쪽 서브 트리에서 맨 왼쪽 노드가 후계자 
        suc_parent=t;
        suc=t->right;
        while(suc->left != NULL) {
            suc_parent = suc;
            suc=suc->left;
        } 
        //후계자의 부모와 자식을 연결
        if(suc_parent->left==suc)
            suc_parent->left=suc->right;
        else
            suc_parent->right=suc->right;
        //후속자가 가진 키 값을 현재 노드에 복사
        t->key=suc->key;
        t=suc; 
    } 
    free(t);            
}

int main(void) {
    TreeNode *root=NULL;
    insert_node(&root,30);
    inorder(root);
    printf("\n");
    insert_node(&root,20);
    insert_node(&root,40);
    inorder(root);
    printf("\n");
    insert_node(&root,15); 
    insert_node(&root,25);
    insert_node(&root,35); 
    insert_node(&root,45);
    inorder(root);
    printf("\n");
    delete_node(&root,30);
    inorder(root);
    printf("\n");  

    return 0;
}