大神的世界

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

#define INFINTE 2147483647

typedef struct node{
    int value;
    int leftThread, rightThread;
    struct node *leftChild, *rightChild;

}Tree;

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

Tree * next(Tree *root);

int main()
{
    Tree *dummyNode = (Tree *)malloc(sizeof(Tree));
    Tree *treeA = (Tree *)malloc(sizeof(Tree));

    dummyNode->value = 0;
    dummyNode->leftChild = treeA;
    dummyNode->rightChild = dummyNode;
    dummyNode->leftThread = 0;
    dummyNode->rightThread = 0;

    treeA->value = INFINTE;
    treeA->leftChild = dummyNode;
    treeA->rightChild = dummyNode;
    treeA->leftThread = 1;
    treeA->rightThread = 1;

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

    int key;
    
    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:
                inorderTraversal(dummyNode);
                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 = *root;
    while(tmp){
        if(key > tmp->value){
            if(tmp->rightThread)
                break;
            tmp = tmp->rightChild;
        }
        else if(key < tmp->value){
            if(tmp->leftThread)
                break;
            tmp =  tmp->leftChild;
        }
        else{
            printf("%d exists\n", key);
            return;
        }
    }

    if(key > tmp->value){
        TreeNode->rightChild = tmp->rightChild;
        TreeNode->leftChild = tmp;
        TreeNode->rightThread = 1;
        TreeNode->leftThread = 1;
        tmp->rightChild = TreeNode;
        tmp->rightThread = 0;
    }
    else{
        TreeNode->leftChild = tmp->leftChild;
        TreeNode->rightChild = tmp;
        TreeNode->leftThread =1;
        TreeNode->rightThread = 1;
        tmp->leftChild = TreeNode;
        tmp->leftThread = 0;
    }
}

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){
                if(tmp->rightThread)
                    break;
                tmp = tmp->rightChild;
            }
            else if(key < tmp->value){
                if(tmp->leftThread)
                    break;
                tmp = tmp->leftChild;
            }
            else
                break;

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

        if(tmp->value == key){
            if(tmp->leftThread && tmp->rightThread){
                if(tmp == *root)
                    (*root)->value = INFINTE;
                else{
                    if(key > parent->value){
                        parent->rightChild = tmp->rightChild;
                        parent->rightThread = 1;
                        tmp->rightChild = tmp->leftChild = NULL;
                    }
                    else{
                        parent->leftChild = tmp->leftChild;
                        parent->leftThread = 1;
                        tmp->rightChild = tmp->leftChild = NULL;
                     }
                    
                    free(tmp);
                }
            }
            else if(tmp->leftThread){
                if(tmp == *root){
                    (*root)->leftChild->leftChild = (*root)->rightChild; // dummy points to new root
                    Tree *p = next(*root);
                    p->leftChild = (*root)->leftChild; // next (inorder) node's leftChild points to dummy

                    *root = tmp->rightChild;
                    tmp->leftChild = tmp->rightChild = NULL;
                }
                else{
                    if(key > parent->value){
                        Tree *p = next(tmp);
                        p->leftChild = parent;
                        parent->rightChild = tmp->rightChild;
                    }
                    else{
                        Tree *p = next(tmp);
                        p->leftChild = parent;
                        parent->leftChild = tmp->rightChild;
                    }
                }
                tmp->rightChild = tmp->leftChild = NULL;
                free(tmp);
            }
            else if(tmp->rightThread){
                if(tmp == *root){
                    (*root)->rightChild->leftChild = (*root)->leftChild; // dummy points to new root
                    Tree *p = (*root)->leftChild;
                    while(!p->rightThread)
                        p = p->rightChild;

                    p->rightChild = (*root)->rightChild; // prev (inorder) node's rightChild points to dummy

                    *root = tmp->leftChild;
                    tmp->leftChild = tmp->rightChild = NULL;
                }
                else{
            
                    Tree *p = tmp->leftChild;
                    while(!p->rightThread)
                        p = p->rightChild;
                    p->rightChild = parent;

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

                substitute  = tmp->leftChild;
                substituteP = tmp;
                while(!substitute->rightThread){
                    substituteP = substitute;
                    substitute = substitute->rightChild;
                }

                if(substituteP == tmp){
                    if(!substitute->leftThread){
                        Tree *p = substitute->leftChild;
                        while(!p->rightThread)
                            p = p->rightChild;
                        p->rightChild = tmp;

                        tmp->leftChild = substitute->leftChild;
                        substitute->leftChild = substitute->rightChild = NULL;
                    }
                    else{
                        tmp->leftChild = substitute->leftChild;
                        tmp->leftThread = 1;
                    }

                }
                else{
                    if(!substitute->leftThread){
                        substituteP->rightChild = substitute->leftChild;
                        Tree *p = substitute->leftChild;
                        while(!p->rightThread)
                            p = p->rightChild;
                        p->rightChild = substitute->rightChild;
                        substitute->leftChild = substitute->rightChild = NULL;
                    }
                    else{
                        substituteP->rightChild = substitute->rightChild;
                        substituteP->rightThread = 1;
                        substitute->leftChild = substitute->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 inorderTraversal(Tree *root)
{
    Tree *ptr = root;
    while(1){
        ptr = next(ptr);
        if(ptr == root) break;
        printf("%d ", ptr->value);
    }
    printf("\n\n");
}

Tree *next(Tree *root)
{
    Tree *ptr = root->rightChild;

    if(!root->rightThread)
        while(!ptr->leftThread)
            ptr = ptr->leftChild;

    return ptr;
}

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 && !tmp->leftThread)
                queue[rear-1] = tmp->leftChild;
            else
                queue[rear-1] = NULL;

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

        printf("\n");
    }
}