I implement red-black tree in C language and output it as a TXT file, but TREE is not output after deleting it

#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } nodeColor;

typedef struct rbnode {
    int key;
    nodeColor color;
    struct rbnode* left, * right, * parent;
} rbnode;

typedef struct QueueNode {
    rbnode* data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// Queue 관련 함수들
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, rbnode* data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    }
    else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

rbnode* dequeue(Queue* q) {
    if (q->front == NULL) {
        return NULL;
    }
    QueueNode* temp = q->front;
    rbnode* data = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

// 함수 프로토타입 선언
rbnode* newNode(int key);
void leftRotate(rbnode** root, rbnode* x);
void rightRotate(rbnode** root, rbnode* x);
void insert(rbnode** root, rbnode* x);
void insertFixup(rbnode** root, rbnode* x);
void delete(rbnode** root, rbnode* z);
void deleteFixup(rbnode** root, rbnode* x);
rbnode* searchNode(rbnode* root, int key);
void printInorder(rbnode* root, FILE* fout);
void printLevelorder(rbnode* root, FILE* fout);
void freeRBTree(rbnode* root);


rbnode* newNode(int key) {
    rbnode* node = (rbnode*)malloc(sizeof(rbnode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->color = 'R'; // 새로운 노드는 레드로 삽입
    return node;
}

rbnode* searchNode(rbnode* root, int key) {
    rbnode* currentNode = root;
    while (currentNode != NULL) {
        if (key == currentNode->key) {
            return currentNode;
        }
        else if (key < currentNode->key) {
            currentNode = currentNode->left;
        }
        else {
            currentNode = currentNode->right;
        }
    }
    return NULL; // 해당 키를 가진 노드를 찾지 못한 경우
}

void BSTInsert(rbnode** root, rbnode* z) {
    rbnode* y = NULL;
    rbnode* x = *root;

    while (x != NULL) {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;

    if (y == NULL)
        *root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
}

// 레드-블랙 트리 삽입
void leftRotate(rbnode** root, rbnode* x) {
    rbnode* y = x->right;
    x->right = y->left;
    if (y->left != NULL) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == NULL) {
        *root = y;
    }
    else if (x == x->parent->left) {
        x->parent->left = y;
    }
    else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

void rightRotate(rbnode** root, rbnode* y) {
    rbnode* x = y->left;
    y->left = x->right;
    if (x->right != NULL) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == NULL) {
        *root = x;
    }
    else if (y == y->parent->right) {
        y->parent->right = x;
    }
    else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

void insert(rbnode** root, rbnode* x) {
    // 새로운 노드 x를 이진 탐색 트리에 삽입
    rbnode* y = NULL;
    rbnode* z = *root;

    // 이진 탐색 트리에서 x의 위치를 찾음
    while (z != NULL) {
        y = z;
        if (x->key < z->key) {
            z = z->left;
        }
        else {
            z = z->right;
        }
    }
    x->parent = y;
    if (y == NULL) {
        *root = x; // 트리가 비어있을 경우 root로 설정
    }
    else if (x->key < y->key) {
        y->left = x;
    }
    else {
        y->right = x;
    }

    x->left = NULL;
    x->right = NULL;
    x->color = RED; // 새로운 노드는 레드로 삽입되므로 RB 특성을 위반하지 않음

    // 삽입 후 트리를 수정해야 할 필요가 있으므로 insertFixup 호출
    insertFixup(root, x);
}


void insertFixup(rbnode** root, rbnode* x) {
    while (x != *root && x->parent->color == RED) {
        if (x->parent == x->parent->parent->left) {
            rbnode* y = x->parent->parent->right; // uncle

            if (y != NULL && y->color == RED) {
                // Case 1: Uncle node y is red
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            }
            else {
                // Case 2: Uncle node y is black and x is a right child
                if (x == x->parent->right) {
                    x = x->parent;
                    leftRotate(root, x);
                }

                // Case 3: Uncle node y is black and x is a left child
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rightRotate(root, x->parent->parent);
            }
        }
        else {
            // Symmetric cases
            rbnode* y = x->parent->parent->left; // uncle

            if (y != NULL && y->color == RED) {
                // Case 1: Uncle node y is red
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            }
            else {
                // Case 2: Uncle node y is black and x is a left child
                if (x == x->parent->left) {
                    x = x->parent;
                    rightRotate(root, x);
                }

                // Case 3: Uncle node y is black and x is a right child
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                leftRotate(root, x->parent->parent);
            }
        }
    }
    (*root)->color = BLACK; // Root node must be black
}

rbnode* treeMinimum(rbnode* x) {
    while (x->left != NULL) {
        x = x->left;
    }
    return x;
}


rbnode* treeSuccessor(rbnode* x) {
    if (x->right != NULL) {
        return treeMinimum(x->right);
    }
    rbnode* y = x->parent;
    while (y != NULL && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}


void delete(rbnode** root, rbnode* z) {
    if (z == NULL) return;

    rbnode* y, * x;
    if (z->left == NULL || z->right == NULL) {
        y = z;
    }
    else {
        y = treeSuccessor(z);
    }

    if (y->left != NULL) {
        x = y->left;
    }
    else {
        x = y->right;
    }

    if (x != NULL) {
        x->parent = y->parent;
    }

    if (y->parent == NULL) {
        *root = x;
    }
    else if (y == y->parent->left) {
        y->parent->left = x;
    }
    else {
        y->parent->right = x;
    }

    if (y != z) {
        z->key = y->key;
    }

    if (y->color == BLACK) {
        deleteFixup(root, x);
    }

    // 삭제한 노드의 부모 노드와의 연결을 끊음
    if (y->parent != NULL) {
        if (y->parent->left == y) {
            y->parent->left = NULL;
        }
        else {
            y->parent->right = NULL;
        }
    }

    free(y);
}



void deleteFixup(rbnode** root, rbnode* x) {
    rbnode* w;
    while (x != *root && x != NULL && x->color == BLACK) {
        if (x == x->parent->left) {
            w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(root, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            }
            else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(root, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(root, x->parent);
                x = *root; // 반복문 종료
            }
        }
        else {
            // Symmetric cases
            w = x->parent->left; // uncle

            if (w->color == RED) {
                // Case 1: Uncle node w is red
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(root, x->parent);
                w = x->parent->left;
            }

            if (w->right->color == BLACK && w->left->color == BLACK) {
                // Case 2: Uncle node w is black and both of w's children are black
                w->color = RED;
                x = x->parent;
            }
            else {
                if (w->left->color == BLACK) {
                    // Case 3: Uncle node w is black, w's left child is black, and w's right child is red
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(root, w);
                    w = x->parent->left;
                }
                // Case 4: Uncle node w is black, w's left child is red, and w's right child is black
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(root, x->parent);
                x = *root; // 반복문 종료
            }
        }
    }
    if (x != NULL) {
        x->color = BLACK; // 루트 노드는 블랙으로 설정
    }
}


void printInorder(rbnode* root, FILE* fout) {
    if (root != NULL) {
        printInorder(root->left, fout); // 왼쪽 서브트리 출력
        fprintf(fout, "%d ", root->key); // 현재 노드 출력
        printInorder(root->right, fout); // 오른쪽 서브트리 출력
    }
}


void printLevelorder(rbnode* root, FILE* fout) {
    if (root == NULL) return;

    Queue* q = createQueue();
    enqueue(q, root);

    while (q->front != NULL) {
        rbnode* current = dequeue(q);
        fprintf(fout, "%d ", current->key);

        if (current->left != NULL) {
            enqueue(q, current->left);
        }
        if (current->right != NULL) {
            enqueue(q, current->right);
        }
    }
}

void printInorderToFile(rbnode* root, FILE* fout) {
    if (root == NULL) return;
    printInorderToFile(root->left, fout);
    fprintf(fout, "%d ", root->key);
    printInorderToFile(root->right, fout);
}

void printLevelorderToFile(rbnode* root, FILE* fout) {
    if (root == NULL) return;
    rbnode* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        rbnode* node = queue[front++];
        fprintf(fout, "%d ", node->key);
        if (node->left != NULL) queue[rear++] = node->left;
        if (node->right != NULL) queue[rear++] = node->right;
    }
}

void freeRBTree(rbnode* node) {
    if (node == NULL) return;
    freeRBTree(node->left);
    freeRBTree(node->right);
    free(node);
}

int main(int argc, char* argv[]) {
    if (argc != 3) {
        printf("Usage: %s input.txt output.txtn", argv[0]);
        return 1;
    }

    FILE* fin = fopen(argv[1], "r"); // 입력 파일 열기
    FILE* fout = fopen(argv[2], "w"); // 출력 파일 열기
    if (!fin || !fout) {
        printf("Error opening file.n");
        return 1;
    }

    // Red-Black Tree 생성
    rbnode* root = NULL;
    int key;

    // 입력 파일에서 데이터를 읽어서 Red-Black Tree에 삽입
    while (fscanf(fin, "%d", &key) != EOF) {
        // 중복된 값 제거
        if (searchNode(root, key) == NULL) {
            rbnode* n = newNode(key);
            insert(&root, n);
        }
    }

    // 삽입 후 결과 출력
    fprintf(fout, "");
    printInorder(root, fout);
    fprintf(fout, "n");

    fprintf(fout, "");
    printLevelorder(root, fout);
    fprintf(fout, "n");

    // 입력 파일을 처음으로 되돌리고 삭제할 노드를 찾아서 삭제
    rewind(fin);
    while (fscanf(fin, "%d", &key) != EOF) {
        rbnode* n = searchNode(root, key);
        if (n != NULL) {
            delete(&root, n);
        }
    }

    // 삭제 후 결과 출력
    fprintf(fout, "");
    printInorder(root, fout);
    fprintf(fout, "n");

    fprintf(fout, "");
    printLevelorder(root, fout);
    fprintf(fout, "n");

    // 파일 닫기
    fclose(fin);
    fclose(fout);

    // Red-Black Tree의 메모리 해제
    freeRBTree(root);

    return 0;
}

If i insert the txt file and run the code, the result 2 lines output well after installing in output.txt, but after deleting, nothing is output in the result 2 lines. Please solve the problem.

Inorder traversal after insertion: 2 3 6 7 8 10 11 13 18 22 26
Levelorder traversal after insertion: 10 7 18 3 8 11 22 2 6 13 26
Inorder traversal after deletion:
Levelorder traversal after deletion:

Like this…

I don’t know how to solve it

  • c

New contributor

user25216557 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị

Filed under: Kiến thức lập trình - @ 04:07

Thẻ:

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật