大神的世界

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

#define INFINTE 2147483647

typedef struct node{
    int value;
    struct node *leftChild, *rightChild;
}Tree;

void print(Tree **root);
void insert(Tree **root, int key);
void delete(Tree **root, int key);
void search(Tree **root, int key);

int main()
{
    char manual[] = "menu:\n1.insert\n2.delete\n3.search\n4.print(reference, it's hard to align!)\n5.exit\n\nop:";
    int op;

    int key;
    Tree *treeA = (Tree *)malloc(sizeof(Tree));
    treeA->value = INFINTE;
    treeA->leftChild = NULL;
    treeA->rightChild = NULL;

    while(1){
        printf("%s", manual);
        scanf("%d", &op);

        switch(op){
            case 1:
                printf("\ninsert value:");
                scanf("%d", &key);
                insert(&treeA, key);
                break;

            case 2:
                printf("\ndelete value:");
                scanf("%d", &key);
                delete(&treeA, key);
                break;

            case 3:
                printf("\nsearch value:");
                scanf("%d", &key);
                search(&treeA, key);
                break; 

            case 4:
                print(&treeA);
                break;

            case 5:
                exit(0);
        }
    }
    return 0;
}

void insert(Tree **root, int key)
{

    if((*root)->value == INFINTE){
        (*root)->value = key;
        return;
    }

    Tree *TreeNode = (Tree *)malloc(sizeof(Tree));
    TreeNode->value = key;
    TreeNode->leftChild = TreeNode->rightChild = NULL;

    Tree *tmp, *parent;

    tmp = parent = *root;
    while(tmp){

        parent = tmp;
        if(key > tmp->value)
            tmp = tmp->rightChild;
        else if(key < tmp->value)
            tmp =  tmp->leftChild;
        else{
            printf("%d exists\n", key);
            return;
        }
    }

    if(key > parent->value)
        parent->rightChild = TreeNode;
    else
        parent->leftChild = TreeNode;

}

void delete(Tree **root, int key)
{
    if((*root)->value == INFINTE)
        printf("Tree is empty!\n\n");
    else{
        Tree *tmp, *parent;
        tmp = parent = *root;
        while(tmp){
            if(key > tmp->value)
                tmp = tmp->rightChild;
            else if(key < tmp->value)
                tmp = tmp->leftChild;
            else
                break;

            if(tmp && tmp->value != key)
                parent = tmp;
        }

        if(tmp){
            if(!tmp->leftChild && !tmp->rightChild){
                if(tmp == *root)
                    (*root)->value = INFINTE;
                else{
                    if(key > parent->value)
                        parent->rightChild = NULL;
                    else
                        parent->leftChild = NULL;
                    
                    free(tmp);
                }
            }
            else if(!tmp->leftChild){
                if(tmp == *root)
                    *root = tmp->rightChild;
                else{
                    if(key > parent->value)
                        parent->rightChild = tmp->rightChild;
                    else
                        parent->leftChild = tmp->rightChild;
                }
                tmp->rightChild = NULL;
                free(tmp);
            }
            else if(!tmp->rightChild){
                if(tmp == *root)
                    (*root) = tmp->leftChild;
                else{
                    if(key > parent->value)
                        parent->rightChild = tmp->leftChild;
                    else
                        parent->leftChild = tmp->leftChild;
                }
                
                tmp->leftChild = NULL;
                free(tmp);
            }
            else{
                Tree *substitute, *substituteP;

                substitute  = tmp->leftChild;
                substituteP = tmp;
                while(substitute->rightChild){
                    substituteP = substitute;
                    substitute = substitute->rightChild;
                }
                if(substituteP == tmp){
                    if(substitute->leftChild){
                        tmp->leftChild = substitute->leftChild;
                        substitute->leftChild = NULL;
                    }
                    tmp->leftChild = NULL;
                }
                else{
                    if(substitute->leftChild){
                        substituteP->rightChild = substitute->leftChild;
                        substitute->leftChild = NULL;
                    }
                    substituteP->rightChild = NULL;
                }

                tmp->value = substitute->value;
                free(substitute);
            }
            printf("%d has been deleted\n\n", key);
        }
        else
            printf("%d not found!\n\n", key);
    }
}

void search(Tree **root, int key){

    int flag = 0;

    Tree *tmp = *root;

    while(tmp){
        printf("%d -> ", tmp->value);
        if(key > tmp->value)
            tmp = tmp->rightChild;
        else if(key < tmp->value)
            tmp = tmp->leftChild;
        else{
            flag = 1;
            break;
        }
    }

    if(flag)
        printf("%d found!\n\n", key);
    else
        printf("... not found!\n\n");
}

void print(Tree **root)
{
    if((*root)->value == INFINTE){
        printf("Tree is empty\n\n");
        return;
    }

    int end_flag = 0;

    Tree *queue[100];
    int rear = 0;
    int front = 0;

    Tree *tmp;

    queue[rear] = *root;
    for(int i = 1, level = 0; !end_flag;i*=2, level++){
        end_flag = 1;

        int j = i;
        for(int k = 20-2*level; k>0; k--)
            printf("_");

        while(j--){
            tmp = queue[front];
            front = (front+1)%100;

            for(int k = 10-2*level; k>0; k--)
                printf("_");

            if(tmp){
                end_flag = 0;
                printf("%d", tmp->value);
            }
            else
                printf(" ");

            rear = (rear+2)%100;

            if(tmp && tmp->leftChild)
                queue[rear-1] = tmp->leftChild;
            else
                queue[rear-1] = NULL;

            if(tmp && tmp->rightChild)
                queue[rear] = tmp->rightChild;
            else
                queue[rear] = NULL; 
        }

        printf("\n");
    }
}