이중 포인터를 이용한 tree(트리) 구조

#include <stdio.h>

#include <malloc.h>

#define FAIL 0

#define SUCC 1

typedef struct node

{

struct node *left;

struct node *right;

int data;

}NODE;

NODE* createNode( int);

void insertNode( NODE **, int);

int deleteNode( NODE **, int);

int main( void)

{

int arry[] = { 50, 70, 30, 90, 60, 20, 110, 80, 65, 55, 68, 63, 58, 53};

int c = 0;

NODE *root = NULL;

for( c = 0 ; c < sizeof(arry) / 4 ; c ++)

{

insertNode( &root, arry[c]);

}

deleteNode( &root, 50);

return 0;

}

int deleteNode( NODE **r, int data)

{

NODE *temp = NULL;

if( *r == NULL) // 지우려는 데이터가 없을 경우

{

printf("Can't find a data!\n");

return FAIL; // 노드 삭제 실패

}

else if( (**r).data > data)  // 찾고자 하는 데이터가 작을 경우

{

if( SUCC == deleteNode( &(**r).right, data)) // 오른쪽으로 탐색

{

(**r).right = NULL; // 오른쪽 하위 노드가 지워졌으므로, NULL을 대입

}

}

else if( (**r).data < data)// 찾고자 하는 데이터가 클 경우

{

if( SUCC == deleteNode( &(**r).left, data)) // 왼쪽으로 탐색

{

(**r).left = NULL; // 왼쪽 하위 노드가 지워졌으므로, NULL을 대입

}

}

else // 데이터를 찾은 경우

{

if( (**r).left == NULL && (**r).right == NULL) // 하위 노드가 없을 경우

{

*r = NULL; // 현재 노드의 위치를 NULL로 만든다 * root 노드 삭제 시 root 포인터가 NULL이 아닌 해제된(엉뚱한) 공간을 가르킴

free(*r); // 현재 노드 삭제

return SUCC; // 하위 노드가 없는 노드 삭제 완료

}

else if( (**r).left != NULL && (**r).right != NULL) // 하위 노드가 2개 있을 경우

{

temp = (**r).left; // 노드 탐색을 위한 변수 초기화

while( (*temp).right != NULL) // 마지막 노드 탐색

{

temp = (*temp).right; // 계속 다음 노드로 진행

}

(**r).data = (*temp).data; // 삭제할 노드와 대체될 노드의 데이터를 변경

deleteNode( &((**r).left), (*temp).data); // 원래 위치 삭제

}

else // 하위 노드가 1개 있을 경우

{

temp = *r; // 삭제될 노드 백업

if( (**r).left != NULL) // 왼쪽 노드가 있을 경우

{

*r = (**r).left; // 현재 노드 위치에 왼쪽 하위 노드를 대체한다.

}

else // 오른쪽 노드가 있을 경우

{

*r = (**r).right; // 현재 노드 위치에 오른쪽 하위 노드를 대체한다.

}

free(temp); // 삭제하려는 노드 제거

}

}

return 0;

}

void insertNode( NODE **r, int data)

{

if( *r == NULL)

{

NODE *temp = createNode( data);

*r = temp;

}

else

{

if( (**r).data <= data)

{

insertNode( &((**r).left), data);

}

else

{

insertNode( &((**r).right), data);

}

}

}

NODE* createNode( int data)

{

NODE *temp = (NODE*)malloc(sizeof(NODE));

(*temp).left = NULL;

(*temp).right = NULL;

(*temp).data = data;

return temp;

}