My Binary Search Tree's Delete Function In C doesn't work. What's the problem?

+1 vote
asked Nov 16, 2019 by 유나젤 (130 points)
please help me. I really don't know why it doesn't work.

#ifdef _MSC_VER

#define _CRT_SECURE_NO_WARNINGS

#endif

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "BST.h"

#include "Queue.h"

QueueNode *ar = NULL;

Queue *queue = NULL;

BST_Tree* tree = NULL;

int main()

{

int number;

    char output[1000];

    char input[1000];

    memset(output,'\0',sizeof(char));

memset(input,'\0',sizeof(char));

    queue = CreateQueue();

    tree = BST_Create(compareStr);

while(1)

{

printf("input 0(insert), 1(retrieve), 2(delete), 3(Preorder), 4(Inorder), 5(Postorder) :  ");

scanf("%d",&number);

switch(number){

case 0 : // 입력

//while(1)

{

memset(input,'\0',sizeof(char));

printf("String : ");

    scanf("%s",input);

    //if(input[0]=='e' && input[1]=='x' && input[2]=='i' && input[3]=='t')

// break;

        Enqueue(queue,input);

        

        if(ar==NULL)

        {

            ar=queue->front;

    BST_insert(tree,ar->Data);

}

else

{

ar=queue->rear;

BST_insert(tree,ar->Data);

}

break;

        }

case 1: // 검색

{

memset(input,'\0',sizeof(char));

printf("String : ");

    scanf("%s",input);

if(BST_retrieve(tree,input))

printf("%s is exist.\n",input);

    

break;

}

case 2: // 삭제

{

printf("String : ");

scanf("%s",input);

if(BST_retrieve(tree,input))

{

tree->root = BST_delete(tree->root,input);

(tree->count)--;

printf("%s is deleted.\n",input);

}

else

printf("%s is not exist\n",input);

break;

}

case 3 : //출력(Preorder)

{

Preorder(tree->root);

printf("\n");

break;

}

case 4:

{

Inorder(tree->root);

printf("\n");

break;

}

case 5:

{

Postorder(tree->root);

printf("\n");

break;

}

}

}

return 0;

}

----------------------main.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef enum {

    true = 1, false =0

} bool;

typedef struct node{

    void* dataPtr;

    struct node* left;

    struct node* right;

} Node;

typedef struct{

    int count;

    int (*compare)(void* argu1, void* argu2);

    Node* root;

} BST_Tree;

Node* insert(BST_Tree *tree, Node* root, Node* newPtr);

int compareStr(void *argu1, void *argu2);

BST_Tree* BST_Create(int (*compare)(void* argu1, void* argu2));

bool BST_insert(BST_Tree* tree, void* dataPtr);

void* retrieve(BST_Tree* tree, void* dataPtr, Node* root);

void* BST_retrieve(BST_Tree* tree, void* keyPtr);

Node* BST_delete(Node* root,void* dataPtr);

void traverse(Node* root, void(*printStr)(void* dataPtr));

void printStr(void * stuPtr);

void Preorder(Node *root);

void Inorder(Node *root);

void Postorder(Node *root);

int compareStr(void *argu1, void *argu2)

{

    return strcmp((char*)argu1, (char*)argu2);

}

BST_Tree* BST_Create(int (*compare)(void* argu1, void* argu2))

{

    BST_Tree* tree = NULL;

    tree = (BST_Tree*)malloc(sizeof(BST_Tree));

    if(tree)

    {

        tree->root = NULL;

        tree->count = 0;

        tree->compare = compareStr;

    }

    return tree;

}

bool BST_insert(BST_Tree* tree, void* dataPtr){

    Node* newPtr = NULL;

    newPtr = (Node*)malloc(sizeof(Node));

    if(!newPtr)

    return false;

    newPtr->right = NULL;

    newPtr->left = NULL;

    newPtr->dataPtr = dataPtr;

    if(tree->count==0)

        tree->root= newPtr;

    else

        insert(tree,tree->root,newPtr);

    (tree->count)++;

    return true;

}

Node* insert(BST_Tree *tree, Node* root, Node* newPtr){

    if(!root)

    return newPtr;

    

    if(tree->compare(newPtr->dataPtr,root->dataPtr)<0)

    {

        root->left = insert(tree,root->left,newPtr);

    }

    else

    {

        root->right = insert(tree,root->right,newPtr);

    }

    return root;

}

void* retrieve(BST_Tree* tree, void* dataPtr, Node* root)

{

    if(root){

        if(tree->compare(dataPtr,root->dataPtr)<0)

        return retrieve(tree,dataPtr,root->left);

        else if(tree->compare(dataPtr,root->dataPtr)>0)

        return retrieve(tree,dataPtr,root->right);

        else

        return root->dataPtr;

    }

    else

    return NULL;

}

void* BST_retrieve(BST_Tree* tree, void* keyPtr){

    if(tree->root)

    return retrieve(tree,keyPtr,tree->root);

    else

    return NULL;

}

Node* BST_delete(Node* root,void* dataPtr){

if(root==NULL){

return root;

}

if(dataPtr<root->dataPtr)

root->left = BST_delete(root->left,dataPtr);

else if(dataPtr>root->dataPtr)

{

root->right = BST_delete(root->right,dataPtr);

}

else{

Node* delPtr=NULL;

if(!root->right)

{

delPtr = root;

root=root->left;

free(delPtr);

return root;

}

else if(!root->left){

delPtr = root;

root=root->right;

free(delPtr);

return root;

}

else{

for(delPtr=root->left;delPtr->right!=NULL;delPtr=delPtr->right);

root->dataPtr = delPtr->dataPtr;

root->left = BST_delete(root->left,delPtr->dataPtr);

}

}

return root;

}

void Preorder(Node *root){

    if(root == NULL)

    return ;

    printf("%s ",root->dataPtr);

    Preorder(root->left);

    Preorder(root->right);

}

void Inorder(Node *root){

    if(root == NULL)

    return ;

    Inorder(root->left);

    printf("%s ",root->dataPtr);

    Inorder(root->right);

}

void Postorder(Node *root){

    if(root == NULL)

    return ;

    Postorder(root->left);

    Postorder(root->right);

    printf("%s ",root->dataPtr);

}

-----------------Tree.h

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef char Elements;

typedef struct tQueueNode{

Elements *Data;

struct tQueueNode *next;

}QueueNode;

typedef struct tQueue{

int count;

QueueNode *front;

    QueueNode *rear;

} Queue;

Queue *CreateQueue();

void Enqueue(Queue *pQueue,Elements *data);

Elements* Dequeue(Queue *pQueue);

Queue *CreateQueue(){

Queue *pQueue = (Queue*)malloc(sizeof(Queue));

if(pQueue==NULL)

return NULL;

pQueue->count=0;

pQueue->front = NULL;

pQueue->rear = NULL;

return pQueue;

}

void Enqueue(Queue *pQueue,Elements *data){

QueueNode *pQueueNode = (QueueNode*)malloc(sizeof(QueueNode)); // 큐노드 생성

if(pQueueNode == NULL)

return;

pQueueNode->Data = (char*)malloc(1000000);

strcpy(pQueueNode->Data,data);

pQueueNode->next = NULL;    

if(pQueue->count<=0)

{

    pQueue->front = pQueueNode;

    pQueue->rear = pQueueNode;

}

else

{

    pQueue->rear->next=pQueueNode;

    pQueue->rear = pQueueNode;

}

pQueue->count++;

}

Elements* Dequeue(Queue *pQueue){

if((pQueue)->count<=0) return 0;

else {

QueueNode *Now = NULL; // QueueNode 생성

Elements *Data = NULL; // 뽑을 값 Data 생성

Data= (char*)malloc(sizeof(char)*128);

Now = (pQueue)->front; // 생성한 QueueNode의 위치를 Top으로 지정

Data = Now->Data; // Data 값 추출

if(pQueue->count==1)

{

    pQueue->front=pQueue->rear=NULL;

}

else

{

    pQueue->front = Now->next; // Top의 위치를 Now의 Next로 변경

}

free(Now); // Now 메모리 해방

pQueue->count--; // 카운트 -1

return Data; // 값 리턴

}

}

------------Queue.h

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...