zzun.net zzun's blog since 2001

[info.]
2004 여름 / 네트워크 프로그래밍(경북대) / 고석주 교수님
using : C / Linux / TCP/IP / Multi-threads / thread-synchronization(mutex)


[Makefile]
all : zchat_serv zchat_clnt

zchat_serv : zchat_serv.c zchat.h
       gcc -o zchat_serv zchat_serv.c -D_REENTRANT -lpthread

zchat_clnt : zchat_clnt.c zchat.h
       gcc -o zchat_clnt zchat_clnt.c -D_REENTRANT -lpthread


[zchat.h]
/**

Z-Chat Header File

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <pthread.h>
#include <string.h>

#define BUFSIZE 100
#define IDSIZE 20
#define CLNT_LIMIT 10


[zchat_serv.c]
/**

Z-Chat SERVER

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include "zchat.h"

struct clnt_info
{
       int sock;
       char* id;
};

int clnt_count = 0;
struct clnt_info* clients[CLNT_LIMIT];
pthread_mutex_t mutx;

void error_handler( char* msg )
{
       fputs( msg, stderr );
       fputc( '\n', stderr );
       exit(1);
}

void sendtoall_ex( char* msg, int sender, int len )                // send to all except sender
{
       int i;
       char id_msg[BUFSIZE+IDSIZE+3];
       
       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++ )
               if ( clients[i]->sock == sender )
               {
                       sprintf( id_msg, "[%s] %s", clients[i]->id, msg );        // attach sender's id
                       len += strlen(clients[i]->id) + 3;
                       break;
               }
       for ( i=0; i<clnt_count; i++ )
               if ( clients[i]->sock != sender )
                       write( clients[i]->sock, id_msg, len );
       pthread_mutex_unlock( &mutx );
}

void sendtoone( char* msg, int sender, int len )        // usage : /id msg
{
       int i, target_sock, id_len;
       char id_msg[BUFSIZE+IDSIZE+15];
       char target_id[IDSIZE];

       id_len = strchr(msg, ' ') - msg - 1;
       strncpy( target_id, msg+1, id_len );
       target_id[id_len] = 0;
       msg = msg + id_len + 2;                // detach target id

       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++ )
       {
               if ( clients[i]->sock == sender )        // attach sender's id
               {
                       sprintf( id_msg, "[Secret from:%s] %s", clients[i]->id, msg );
                       len += strlen(clients[i]->id) + 15;
               }
               if ( !strcmp(target_id, clients[i]->id) )
                       target_sock = clients[i]->sock;
       }        
       pthread_mutex_unlock( &mutx );

       write( target_sock, id_msg, len );
}

void* clnt_msg_process(void* arg)
{
       int clnt_sock = (int) arg;
       char msg[BUFSIZE];
       int i, len;

       while ( (len=read(clnt_sock, msg, sizeof(msg))) != 0 )
       {
               if ( msg[0] == '/' )
                       sendtoone( msg, clnt_sock, len );        // whisper
               else
                       sendtoall_ex( msg, clnt_sock, len );
       }

       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++)
               if ( clnt_sock == clients[i]->sock )
               {
                       printf( "%s's connection closed.\n", clients[i]->id );
                       free( clients[i]->id );
                       free( clients[i] );
                       for ( ; i<clnt_count-1; i++)
                               clients[i] = clients[i+1];                        
                       break;
               }
       clnt_count--;
       pthread_mutex_unlock( &mutx );        

       close( clnt_sock );
       return 0;
}

int main( int argc, char** argv )
{
       int serv_sock, clnt_sock;
       struct sockaddr_in serv_addr;
       struct sockaddr_in clnt_addr;
       int clnt_addr_size;
       pthread_t thread;

       if ( argc != 2 )
       {
               printf( "Usage : %s <port>\n", argv[0] );
               exit(1);
       }

       if ( pthread_mutex_init(&mutx, NULL) )
               error_handler( "pthread_mutex_init() error" );

       serv_sock = socket( PF_INET, SOCK_STREAM, 0 );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = htonl( INADDR_ANY );
       serv_addr.sin_port = htons( atoi(argv[1]) );

       if ( bind(serv_sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) )
               error_handler( "bind() error" );

       if ( listen(serv_sock, CLNT_LIMIT) )
               error_handler( "listen() error" );

       while (1)
       {
               clnt_addr_size = sizeof(clnt_addr);
               clnt_sock = accept( serv_sock, (struct sockaddr*) &clnt_addr, &clnt_addr_size );

               pthread_mutex_lock( &mutx );
               clients[clnt_count] = (struct clnt_info*) malloc( sizeof(struct clnt_info) );
               clients[clnt_count]->id = (char*) malloc( IDSIZE );
               clients[clnt_count]->sock = clnt_sock;
               read( clnt_sock, clients[clnt_count++]->id, IDSIZE );        // recv clnt's id
               pthread_mutex_unlock( &mutx );

               pthread_create( &thread, NULL, clnt_msg_process, (void*)clnt_sock );
               printf( "new client connected : %s\n", clients[clnt_count-1]->id );
       }

       return 0;
}


[zchat_clnt.c]
/**

Z-Chat CLIENT

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include "zchat.h"

void error_handler( char* err_msg )
{
       fputs( err_msg, stderr );
       fputc( '\n', stderr );
       exit(1);
}

void* send_msg( void* arg )
{
       char msg[BUFSIZE];

       int sock = (int) arg;        
       while (1)
       {
               fgets( msg, BUFSIZE, stdin );
               if ( !strcmp(msg, "q\n") )
               {
                       close( sock );
                       exit(0);
               }
               write( sock, msg, strlen(msg) );
       }
}

void* recv_msg( void* arg )
{
       int sock = (int) arg;
       char recieved[BUFSIZE+IDSIZE+15];
       int len;

       while (1)
       {
               len = read( sock, recieved, BUFSIZE+IDSIZE+14 );
               if ( len == -1 )
                       return (void*)1;
               recieved[len] = 0;
               fputs( recieved, stdout );
       }
}

int main( int argc, char** argv )
{
       int sock;
       struct sockaddr_in serv_addr;
       pthread_t send_thrd, recv_thrd;
       void* thr_rtn_val;
       char id[IDSIZE];

       if ( argc != 4 )
       {
               printf( "Usage : %s <IP> <port> <ID>\n", argv[0] );
               exit(1);
       }

       sprintf( id, "%s", argv[3] );

       sock = socket( PF_INET, SOCK_STREAM, 0 );
       if ( sock == -1 )
               error_handler( "socket() error" );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = inet_addr( argv[1] );
       serv_addr.sin_port = htons( atoi(argv[2]) );

       if ( connect(sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) == -1 )
               error_handler( "connect() error" );

       write( sock, id, sizeof(id) );        // send my id

       pthread_create( &send_thrd, NULL, send_msg, (void*) sock );
       pthread_create( &recv_thrd, NULL, recv_msg, (void*) sock );

       pthread_join( send_thrd, &thr_rtn_val );
       pthread_join( recv_thrd, &thr_rtn_val );        // wait until threads die

       close( sock );
       return 0;
}

[info.]
2004 Summer / 네트워크 프로그래밍(경북대) / 고석주 교수님

[rspgame_serv.c]
/**

RSP game SERVER

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <time.h>
#include <signal.h>
#include <sys/wait.h>
#include <sys/socket.h>
#include <arpa/inet.h>

#define BUFSIZE 5

void err_handler( char* msg )
{
       fputs( msg, stderr );
       exit(1);
}

void z_handler( int sig )        // zombie child process handler
{
       int rtn;
       waitpid( -1, &rtn, WNOHANG );
}

int who_win( int a, int b )                // determine who win
{
       if ( a>2 || b>2 || a<0 || b<0 )
               return -2;
       else if ( a == b)
               return 0;
       else if ( a == (b+1)%3 )
               return 1;
       else
               return -1;
}

int main( int argc, char** argv )
{
       char buffer[BUFSIZE];
       int serv_sock, clnt_sock;
       struct sockaddr_in serv_addr;
       struct sockaddr_in clnt_addr;
       struct sigaction act;
       int str_len, clnt_addr_size, serv_card, result;
       pid_t pid;
       char* RSP[3];
       char* result_print[3];

       result_print[0] = "Win!\n";
       result_print[1] = "Draw! Regame!\n";
       result_print[2] = "Lose!\n";
       RSP[0] = "Rocks";
       RSP[1] = "Scissors";
       RSP[2] = "Papers";

       if ( argc != 2 )
       {
               printf( "Usage : %s <port>\n", argv[0] );
               exit(1);
       }

       act.sa_handler = z_handler;
       sigemptyset( &act.sa_mask );
       act.sa_flags = 0;                // for sigaction()

       if ( sigaction(SIGCHLD, &act, 0) )        // when child dies
               err_handler( "sigaction() error\n" );

       serv_sock = socket( PF_INET, SOCK_STREAM, 0 );
       if ( serv_sock == -1 )
               err_handler( "socket() error\n" );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = htonl( INADDR_ANY );
       serv_addr.sin_port = htons( atoi(argv[1]) );

       if ( bind(serv_sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) )
               err_handler( "bind() error\n" );
       if ( listen(serv_sock, 5) )
               err_handler( "listen() error\n" );
       
       while (1)
       {
               clnt_addr_size = sizeof( clnt_addr );
               clnt_sock = accept( serv_sock, (struct sockaddr*) &clnt_addr, &clnt_addr_size );
               if ( clnt_sock == -1 )
                       continue;

               pid = fork();

               switch ( pid )
               {
               case -1 :
                       printf("fork() error : client %s\n", inet_ntoa(clnt_addr.sin_addr) );
                       close( clnt_sock );
                       continue;

               case 0 :        // child
                       close( serv_sock );
                       
                       do
                       {
                               srand((unsigned) time(NULL));
                               serv_card = rand() % 3;
                               printf( "Randomly generated number : %d (%s)\n", serv_card, RSP[serv_card] );
                               read( clnt_sock, buffer, BUFSIZE );                // get client's card

                               result = who_win( serv_card, atoi(buffer) );
                               if ( result == -2 )
                                       err_handler( "client input error" );

                               buffer[0] = '1' + result;
                               buffer[1] = 0;
                               printf( "Game with %s : ", inet_ntoa(clnt_addr.sin_addr) );
                               printf( result_print[result+1] );        // print out the result
                               write( clnt_sock, buffer, 1 );
                       } while ( result == 0 );        // tied! try again

                       printf("connection to %s closed.\n", inet_ntoa(clnt_addr.sin_addr) );
                       close( clnt_sock );
                       exit(0);

               default :        // parent
                       printf("connected to %s\n", inet_ntoa(clnt_addr.sin_addr) );
                       close( clnt_sock );
                       continue;
               }
       }

       return 0;
}







[rspgame_clnt.c]
/**

RSP game CLIENT

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <string.h>
#include <sys/socket.h>
#include <arpa/inet.h>

#define BUFSIZE 10

void err_handler( char* msg )
{
       fputs( msg, stderr );
       exit(1);
}

int main( int argc, char** argv )
{
       int sock, str_len, clnt_card, result;
       struct sockaddr_in serv_addr;
       char buffer[BUFSIZE];
       char* result_print[3];
       char input_msg[] = "input your card (0:Rocks, 1:Scissors, 2:Papers) : ";

       result_print[0] = "You Lose!\n";
       result_print[1] = "Draw! Regame!\n";
       result_print[2] = "You Win!\n";

       if ( argc != 3 )
       {
               printf( "Usage : %s <IP> <port>\n", argv[0] );
               exit(1);
       }

       sock = socket( PF_INET, SOCK_STREAM, 0 );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = inet_addr( argv[1] );
       serv_addr.sin_port = htons( atoi(argv[2]) );

       if ( connect(sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) == -1 )
               err_handler( "connect() error\n" );

       printf( "connected.\n" );

       do
       {
               do
               {
                       write( 1, input_msg, strlen(input_msg) );        
                       str_len = read( 0, buffer, BUFSIZE );
                       clnt_card = atoi( buffer );
               } while ( clnt_card<0 || clnt_card>2 );                // input correctness check

               write( sock, buffer, str_len );
               read( sock, buffer, BUFSIZE-1 );
               result = atoi( buffer );
               if ( result<0 || result>2)
                       err_handler( "result error\n" );
               else
                       printf( result_print[result] );                
       } while ( result == 1);

       close( sock );
       printf( "connection closed.\n" );

       return 0;
}

http://online-judge.uva.es/p/v4/453.html

/**

Intersecting Circles

zzun
http://zzun.net

**/

#include <fstream.h>
#include <math.h>
#include <stdio.h>

float pow2( float a )
{
       return pow( a, 2 );
}

int main()
{
       ifstream fin;
       float a[2], b[2], r[2], x[2], y[2], temp;

       fin.open( "test.in" );

       fin >> a[0] >> b[0] >> r[0] >> a[1] >> b[1] >> r[1];

       while ( ! fin.eof() )
       {
               float d = sqrt( pow2(a[0]-a[1]) + pow2(b[0]-b[1]) );        // distance

               if ( a[0]==a[1] && b[0]==b[1] && r[0]==r[1] )
                       printf( "THE CIRCLES ARE THE SAME\n" );

               else if ( d>r[0]+r[1] || d<fabs(r[0]-r[1]) )
                       printf( "NO INTERSECTION\n" );

               else if ( d == r[0]+r[1] )        // circumscription
               {
                       x[0] = ( r[0]*a[1] + r[1]*a[0] ) / ( r[0] + r[1] );
                       y[0] = ( r[0]*b[1] + r[1]*b[0] ) / ( r[0] + r[1] );
                       printf( "(%.3f,%.3f)\n", x[0], y[0] );
               }

               else if ( d == fabs(r[0]-r[1]) )        // inscription
               {
                       x[0] = ( r[0]*a[1] - r[1]*a[0] ) / ( r[0] - r[1] );
                       y[0] = ( r[0]*b[1] - r[1]*b[0] ) / ( r[0] - r[1] );
                       printf( "(%.3f,%.3f)\n", x[0], y[0] );
               }

               else if ( a[0] == a[1] )        // same a, diff b
               {
                       y[0] = ( (b[0]+b[1]) - (r[0]+r[1])*(r[0]-r[1])/(b[0]-b[1]) ) / 2;
                       temp = sqrt( (r[0]-y[0]+b[0])*(r[0]+y[0]-b[0]) );
                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", a[0]-temp, y[0], a[0]+temp, y[0] );
               }

               else if ( b[0] == b[1] )        // same b, diff a
               {
                       x[0] = ( (a[0]+a[1]) - (r[0]+r[1])*(r[0]-r[1])/(a[0]-a[1]) ) / 2;
                       temp = sqrt( (r[0]-x[0]+a[0])*(r[0]+x[0]-a[0]) );
                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", x[0], b[0]-temp, x[0], b[0]+temp );
               }

               else        // normal case
               {
                       float ef[3], A, B, C;

                       B = 2 * (b[1]-b[0]);
                       A = 2 * (a[1]-a[0]) / B;
                       C = ( (a[0]+a[1])*(a[0]-a[1]) + (b[0]+b[1])*(b[0]-b[1]) - (r[0]+r[1])*(r[0]-r[1]) ) / B;

                       ef[0] = 1 + pow2(A);
                       ef[1] = 2*b[0]*A - 2*a[0] + 2*A*C;
                       ef[2] = pow2(C) + 2*b[0]*C + pow2(a[0]) + pow2(b[0]) - pow2(r[0]);

                       temp = sqrt( pow2(ef[1]) - 4*ef[0]*ef[2] );        // b^2 - 4ac
                       x[0] = (temp*(-1) - ef[1]) / (2*ef[0]);
                       x[1] = (temp - ef[1]) / (2*ef[0]);

                       for (int i=0; i<2; i++)
                               y[i] = (-1)*C - A*x[i];

                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", x[0], y[0], x[1], y[1] );
               }

               fin >> a[0] >> b[0] >> r[0] >> a[1] >> b[1] >> r[1];
       }

       fin.close();

       return 0;
}


[test.in]
0.0 0.0 1.0
3.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
1.0 0.0 1.0
5.6 6.6 3.2
3.2 4.8 3.5
5.0 5.0 5.0
0.0 0.0 5.0
0.0 0.0 1.0
3.0 0.0 2.0
0.0 0.0 3.0
2.0 0.0 1.0
3.5 8.6 6.3
3.5 0.3 4.2
0.0 0.0 5.0
1.0 0.0 2.0



> time ./n04_circle
NO INTERSECTION
THE CIRCLES ARE THE SAME
(0.500,-0.866)(0.500,0.866)
(2.880,8.285)(6.456,3.517)
(0.000,5.000)(5.000,0.000)
(1.000,0.000)
(3.000,0.000)
(0.389,3.122)(6.611,3.122)
NO INTERSECTION
0.000u 0.000s 0:00.00 0.0%      0+0k 0+0io 164pf+0w

2003 Fall / 화일처리 / 이석호 교수님

/**

AVL Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>

struct node                        // AVL tree node
{
       int data;                                        // data type is integer
       struct node * left;                        // left subtree
       struct node * right;                // right subtree
       int height;                                        // height of the tree
};

struct node * root = NULL;                // root node, initially NULL

void print_tree_level_order(struct node* tree, int length)                // print tree in level order
{
       struct node** queue;                        // queue for printing
       struct node* current;                        // current printing node
       int front = 0;                                        // front pointer of queue
       int back = 0;                                        // back pointer of queue
       queue = (struct node**)malloc(sizeof(void *)*length);                // queue initailization

       queue[0] = tree;                                                // enqueue root node
       while (queue[front] != NULL)                        // until queue is empty
       {
               current = queue[front];
               printf("%d-", current->data);                // print current node
               if (current->left != NULL)                        // if left node is exist, then enqueue it
               {
                       back = (back+1) % length;
                       queue[back] = current->left;
               }
               if (current->right != NULL)                        // if right node is exist, then enquee it
               {
                       back = (back+1) % length;
                       queue[back] = current->right;
               }
               queue[front] = NULL;                                // dequeue printed element
               front = (front+1) % length;                        // move front pointer to the next
       }

       if (length==0)
               printf("Empty Tree!\n");
       else
               printf("\n");

       free(queue);
}

int max(int x, int y)
{
       return x > y ? x : y;
}

int height_of(struct node* tree)
{
       return tree == NULL ? -1 : tree->height;        // if the tree is NULL, its height is -1
}

void reset_height(struct node* tree)                        // after rotation, reset tree's height
{
       if (tree != NULL)
               tree->height = max(height_of(tree->left), height_of(tree->right)) + 1;
}

struct node* rotate_left(struct node* t)                // rotate left for balancing
{
       struct node* new_node = t->left;
       t->left = new_node->right;
       new_node->right = t;

       reset_height(t);
       reset_height(new_node);                                                // reset nodes' height

       return new_node;
}

struct node* rotate_right(struct node* t)                // right
{
       struct node* new_node = t->right;
       t->right = new_node->left;
       new_node->left = t;

       reset_height(t);
       reset_height(new_node);

       return new_node;
}

struct node* double_rotate_left(struct node* t)           // in some cases, need to rotate twice
{
       t->left = rotate_right(t->left);
       return rotate_left(t);
}

struct node* double_rotate_right(struct node* t)        // symmetric
{
       t->right = rotate_left(t->right);
       return rotate_right(t);
}

struct node* insert(int insert_data, struct node* tree)                // node insert
{
       if (tree == NULL)                                                           // if null, make new node
       {
               tree = (struct node *)malloc(sizeof(struct node));
               tree->data = insert_data;
               tree->left = NULL;
               tree->right = NULL;
               tree->height = 0;
       }
       else if (insert_data < tree->data)                             // insert data in left subtree
       {
               tree->left = insert(insert_data, tree->left);
               if (height_of(tree->left) - height_of(tree->right) == 2)
               {
                       if (insert_data < tree->left->data)
                               tree = rotate_left(tree);
                       else
                               tree = double_rotate_left(tree);
               }
       }
       else if (insert_data > tree->data)
       {
               tree->right = insert(insert_data, tree->right);
               if (height_of(tree->right) - height_of(tree->left) == 2)
               {
                       if (insert_data > tree->right->data)
                               tree = rotate_right(tree);
                       else
                               tree = double_rotate_right(tree);
               }
       }
       else
               printf("Insert Error : item duplicated!\n");          // when the item already exists

       reset_height(tree);                                             // reset tree's height

       return tree;
}

struct node* delete_min(struct node* tree)        // delete minimum-valued node
{
       struct node* temp = tree;

       if (tree == NULL)
               printf("Delete Minimum Error : null tree!\n");
       else if (tree->left != NULL)
       {
               tree->left = delete_min(tree->left);                    // traverse to left and left again
               if (height_of(tree->right) - height_of(tree->left) == 2)
               {
                       if (height_of(tree->right->left) > height_of(tree->right->right))
                               tree = double_rotate_right(tree);
                       else
                               tree = rotate_right(tree);
               }
       }
       else
       {
               tree = tree->right;                           // attach right subtree(or NULL) to parent
               free(temp);                                         // and deletee the old parent
       }

       reset_height(tree);

       return tree;
}

struct node* deletee(int delete_data, struct node* tree)         // delete node
{
       struct node* temp = tree;

       if (tree == NULL)
               printf("Delete Error : item not found!\n");
       else if (delete_data < tree->data)              // delete data in left subtree
       {
               tree->left = deletee(delete_data, tree->left);
               if (height_of(tree->right) - height_of(tree->left) == 2)
               {
                       if (height_of(tree->right->left) > height_of(tree->right->right))
                               tree = double_rotate_right(tree);
                       else
                               tree = rotate_right(tree);
               }
       }
       else if (delete_data > tree->data)
       {
               tree->right = deletee(delete_data, tree->right);
               if (height_of(tree->left) - height_of(tree->right) == 2)
               {
                       if (height_of(tree->left->right) > height_of(tree->left->left))
                               tree = double_rotate_left(tree);
                       else
                               tree = rotate_left(tree);
               }
       }
       else if (tree->left != NULL && tree->right != NULL)
       {
               temp = temp->right;
               while (temp->left != NULL)
                       temp = temp->left;       // find the minimum data of right subtree
               tree->data = temp->data;        // and set it to the parent
               tree->right = delete_min(tree->right);       // and deletee it in right subtree
       }
       else
       {
               tree = (tree->left != NULL) ? tree->left : tree->right;
               free(temp);                                   // free the old parent
       }

       reset_height(tree);

       return tree;
}

int main()
{
       FILE* fp;
       char buffer[11];
       int count = 0;                                                            // # of elements

       fp = fopen("index.txt", "r");
       while (fgets(buffer, 10, fp) != NULL)           // read one line from index.txt
       {
               printf("insert %d : ", atoi(buffer));
               root = insert(atoi(buffer), root);                                // insert it
               count++;
               print_tree_level_order(root, count);                 // and print tree in level order
       }
       fclose(fp);

       fp = fopen("index.txt", "r");                           // close and reopen
       while (fgets(buffer, 10, fp) != NULL)
       {
               printf("delete %d : ", atoi(buffer));
               root = deletee(atoi(buffer), root);                      // delete a node
               count--;
               print_tree_level_order(root, count);                  // and print
       }
       fclose(fp);

       return 0;
}

2003 Fall / 화일처리 / 이석호 교수님

/**

Binary Search Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>

struct znode                        // binary search tree node
{
       int data;                        // data type is integer
       struct znode * left;                        // left subtree
       struct znode * right;                        // right subtree
};

struct znode * root = NULL;                        // root node, initially NULL

void print_tree_inorder(struct znode* tree)       // print tree in inorder (left -> parent -> right)
{
       if (tree == NULL)
               printf("Tree is empty!\n");
       else
       {
               if (tree->left != NULL)
                       print_tree_inorder(tree->left);
               printf("%d ", tree->data);
               if (tree->right != NULL)
                       print_tree_inorder(tree->right);
       }
}

struct znode* insert(int insert_data, struct znode* tree)                // node insert
{
       if (tree == NULL)                  // if null, make new node
       {
               tree = (struct znode *)malloc(sizeof(struct znode));
               tree->data = insert_data;
               tree->left = NULL;
               tree->right = NULL;
       }
       else if (insert_data < tree->data)                // insert data in left subtree
               tree->left = insert(insert_data, tree->left);
       else if (insert_data > tree->data)
               tree->right = insert(insert_data, tree->right);         // insert data in right subtree
       else
               printf("Insert Error : item duplicated!\n");        // when the item already exists

       return tree;
}

struct znode* zremove_min(struct znode* tree)          // delete minimum-valued node
{
       struct znode* temp = tree;

       if (tree == NULL)
               printf("remove Minimum Error : null tree!\n");
       else if (tree->left != NULL)
               tree->left = zremove_min(tree->left);              // traverse to left and left again
       else
       {
               tree = tree->right;                   // attach right subtree(or NULL) to parent
               free(temp);                               // and remove the old parent
       }

       return tree;
}

struct znode* zremove(int remove_data, struct znode* tree)           // delete node
{
       struct znode* temp = tree;

       if (tree == NULL)
               printf("remove Error : item not found!\n");
       else if (remove_data < tree->data)            // delete data in left subtree
               tree->left = zremove(remove_data, tree->left);
       else if (remove_data > tree->data)
               tree->right = zremove(remove_data, tree->right);   // delete data in right subtree
       else if (tree->left != NULL && tree->right != NULL)
                                // if this has both left and rihgt subtree
       {
               temp = temp->right;
               while (temp->left != NULL)
                       temp = temp->left;             // find the minimum data of right subtree
               tree->data = temp->data;                      // and set it to the parent
               tree->right = zremove_min(tree->right);     // and remove it in right subtree
       }
       else
       {
               tree = (tree->left != NULL) ? tree->left : tree->right;
                         // attach one of two children to parent (tree or NULL)
               free(temp);                                // free the old parent
       }

       return tree;
}

int main()
{
       FILE* fp;
       char buffer[11];

       fp = fopen("index.txt", "r");
       while (fgets(buffer, 10, fp) != NULL)                  // read one line from index.txt
       {
               printf("\ninsert %d : ", atoi(buffer));
               root = insert(atoi(buffer), root);                  // insert it
               print_tree_inorder(root);                              // and print the current tree shape
       }
       fclose(fp);

       fp = fopen("index.txt", "r");                             // close and reopen
       while (fgets(buffer, 10, fp) != NULL)
       {
               printf("\ndelete %d : ", atoi(buffer));
               root = zremove(atoi(buffer), root);               // delete a node
               print_tree_inorder(root);                              // and print
       }
       fclose(fp);

       return 0;
}

/**

Binary Search Tree

zzun
hello82@unitel.co.kr
http://zzun.net

**/