본문으로 바로가기
homeimage
  1. Home
  2. 컴퓨터/프로그래밍
  3. C언어 이진트리 제거 함수 tdestroy()

C언어 이진트리 제거 함수 tdestroy()

· 댓글개 · 바다야크

C tdestroy() 이진 트리 제거 함수

tdestroy()는 이진 트리 데이터를 제거 합니다.

  • 헤더: #define _GNU_SOURCE
    #include <search.h>
  • 형태: void tdestroy(void *root, void (*free_node)(void *nodep))
  • 인수: void *rootp 이진 트리 포인터
    void (*free_node)(void *nodep) 노드를 삭제하는 함수 포인터
  • 반환: -

tdestroy()는 glibc의 확장 기능으로 제공하는 함수이므로 _GNU_SOURCE 정의가 필요합니다. 프로그램 소스 상단에 아래의 문구를 삽입하세요.

#define _GNU_SOURCE         // 반드시 삽입
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <search.h>

선형 리스트와 이진트리

정렬된 테이블은 bsearch() 함수로 아주 빠르게 검색할 수 있으나 정렬되어 있지 않으면 제대로 검색할 수 없습니다. 그래서 새로운 자료를 등록할 때마다 계속 정렬해 주어야 하는데, 데이터가 많아지면 많아질수록 부담이 됩니다. 이 문제를 선형 리스트로 빠르게 처리할 수 있습니다.

선형 리스트는 자료를 가지고 있는 노드마다 이전과 다음 노드를 가리키는 포인터를 가지고 있어서 노드 하나만 알면 앞과 뒤의 포인터로 이전과 다음 노드의 자료를 구할 수 있습니다.

여기에 새로운 자료를 추가할 때, 각 노드의 크기와 비교하여 포인터 정보만 갱신해 줍니다.

즉, 각 노드의 데이터를 이동할 필요 없이 포인터 정보만 갱신해 주면 정렬이 이루어집니다.

선형 리스트가 자료를 추가하거나 정렬하기는 문제가 없습니다만, 이진 검색하기에는 부족한 구조입니다. 정렬의 중간 노드를 알기 위해서는 전체 노트 개수를 확인하고 노드를 추적해 가야 합니다.

이진트리는 선형 리스트에 더 발전된 구조로 자료를 입력할 때부터 정렬과 함께 이진 검색이 용이하도록 데이터의 크기에 따라 트리식으로 정렬하는 구조입니다.

이진트리의 노드는 2개의 자식 노드만 가질 수 있으며, 왼쪽과 오른쪽 자식 노드는 크기에 따라 좌우로 나뉘게 됩니다. 만일 45를 찾는다면 선형 리스트처럼 포인터 정보를 이용하여 검색하게 됩니다.

이와 같은 구조로 이진트리에서는 빠르게 정렬과 검색할 수 있습니다.

이진트리 관련 함수

C언어 tdestroy() 함수 예제

#define _GNU_SOURCE
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <search.h>

void print_tree( const void *node, VISIT order, int level)
{
   char *str;

   str   = *(char **)node;

   if ( ( postorder == order)  ||
        ( leaf      == order) )
      printf( "%d %s\n", level, str);
}
int compare( const void *cmp1, const void *cmp2)
{
   return strcmp( (char *)cmp1, (char *)cmp2);
}
void free_node(void *nodep){
   printf( "free: %s\n", ( char *)nodep);
   free( nodep);
}
int main( void)
{
   void  *btree = NULL;
   char  **ptr;
   char  *str;
   char  *item;

   item  = malloc( 100);   strcpy( item, "jwmx");     tsearch( item, &btree, compare);
   item  = malloc( 100);   strcpy( item, "badayak");  tsearch( item, &btree, compare);
   item  = malloc( 100);   strcpy( item, "com");      tsearch( item, &btree, compare);

   printf( "call twalk() -------------------\n");

   twalk( btree, print_tree);

   printf( "search node --------------------\n");

   ptr   = tfind( "jwmx", &btree, compare);
   if ( ptr){
      str   = *ptr;
      printf( "%s is found.\n", str);
   }
   ptr   = tfind( "badayak", &btree, compare);
   if ( ptr){
      str   = *ptr;
      printf( "%s is found.\n", str);
   }

   printf( "call tdestroy() ----------------\n");

   tdestroy( btree, free_node);

   return 0;
}

C언어 tdestroy() 예제 실행 결과

]$ ./a.out
call twalk() -------------------
1 badayak 
0 com 
1 jwmx 
search node -------------------- 
jwmx is found. 
badayak is found. 
call tdestroy() ----------------
]$
SNS 공유하기
💬 댓글 개
최근글
이모티콘창 닫기
울음
안녕
감사해요
당황
피폐

이모티콘을 클릭하면 댓글창에 입력됩니다.