TREE CODE

TREE CODE FOR MY LEARNING..

 

 

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

#define TREE_TYPE int

struct TREE{
    TREE_TYPE value;
    struct TREE *left;
    struct TREE *right;
};


void insert(TREE_TYPE value);
void myinsert(TREE_TYPE value);
void find(TREE_TYPE value);
void pre_order_traverse(void (*callback)(TREE_TYPE value));
void destory_tree();
void destory_node(struct TREE *child);
void delete_valueintree(TREE_TYPE value);
void do_qianxu(struct TREE *current, void (*callback)(TREE_TYPE value));
void do_houxu(struct TREE *current, void (*callback)(TREE_TYPE value));
void do_zhongxu(struct TREE *current, void (*callback)(TREE_TYPE value));
void mycb(TREE_TYPE value);//my callback

int counttree();
int ctt(struct TREE *root);
int getdepth(struct TREE *root);
int getwidth(struct TREE *root);

static struct TREE *tr;
static struct TREE *tr1;
char command[10];
int main(int argc, char *argv){
    TREE_TYPE inputvalue = 0;//For operate value

    int inputn = 0;//count for input

    char *desc = "[insert][display][destory][delete]";
    
    //struct TREE t7 = {9, NULL, NULL};

    //struct TREE t8 = {17, NULL, NULL};

    //struct TREE t9 = {26, NULL, NULL};

    //struct TREE t10 = {29, NULL, NULL};

    //struct TREE t1 = {5,NULL, &t7};

    //struct TREE t2 = {16, NULL, &t8};

    //struct TREE t3 = {12, &t1, &t2};

    //struct TREE t4 = {28, &t9, &t10};

    //struct TREE t5 = {25, NULL, &t4};

    //struct TREE t6 = {20, &t3, &t5};

    printf("Please enter command: ");
    while((inputn = scanf("%s", command)) == 1){
        if(strncmp(command, "insert", 6) == 0){
            if((inputn = scanf("%d", &inputvalue)) == 1){
                insert(inputvalue);
                printf("Please enter command: ");
                continue;
            }
        }

        if(strncmp(command, "delete", 6) == 0){
            if((inputn = scanf("%d", &inputvalue)) == 1){
                delete_valueintree(inputvalue);
                printf("Please enter command: ");
                continue;
            }
        }

        if(strncmp(command, "display", 7) == 0){
            pre_order_traverse(mycb);
            printf("Please enter command: ");
            continue;
        }

        if(strncmp(command, "destory", 7) == 0){
            destory_tree();
            printf("Please enter command: ");
            continue;
        }

        if(strncmp(command, "exit", 4) == 0){
            puts("ByeBye!");
            return 0;
        }

        if(strncmp(command, "count", 4) == 0){
            printf("Count: %d\n", counttree());
            printf("Please enter command: ");
            continue;
        }

        if(strncmp(command, "find", 4) == 0){
            if((inputn = scanf("%d", &inputvalue)) == 1){
                find(inputvalue);
                printf("Please enter command: ");
                continue;
            }
        }

        if(strncmp(command, "ch", 2) == 0){
            printf("Height: %d\n", getdepth(tr));
            printf("Please enter command: ");
            continue;
        }

        printf("Error command!Re-enter: \n");
        continue;
    }

    return 0;
}

void find(TREE_TYPE value){
    struct TREE *current;
    
    current = tr;

    while(current != NULL){
        if(current->value == value){
            printf("Got it!");
            if(current->left != NULL || current->right != NULL){
                if(current->left != NULL)
                    printf("It's left child[%d]", current->left->value);
                if(current->right != NULL)
                    printf("It's right child[%d]", current->right->value);
                putchar('\n');
            }else
                printf("It has no child!\n");
            return;
        }else
            current = value > current->value? current->right: current->left;
    }
    printf("Not found!\n");
}

int counttree(){
    return ctt(tr);
}

int ctt(struct TREE *root){
    if(root == NULL)
        return 0;
    else if(root != NULL && root->left == NULL && root->right == NULL)
        return 1;
    else
        return 1 + ctt(root->left) + ctt(root->right);
        //(root != NULL? 1:0) + ctt(root->right) + ctt(root->left)

        //+ (root->right != NULL && root->left != NULL)? 2:((root->right != NULL || root->left != NULL)?1:0);

}

void destory_tree(){
    destory_node(tr);
}

void destory_node(struct TREE *child){
    if(child->left != NULL){
        destory_node(child->left);
        child->left = NULL;//Maybe it's not null after call free(), to be tested...

    }
    if(child->right != NULL){
        destory_node(child->right);
        child->right = NULL;
    }
    free(child);
}

void delete_valueintree(TREE_TYPE value){
    struct TREE *current;
    struct TREE *parent;
    struct TREE **link;
    TREE_TYPE temp;//search largest value in left childs


    link = &tr;

    while((current = *link) != NULL){// =.=! fucking code..

        if(value == current->value)
            break;
        else
            link = value > current->value?&current->right:&current->left;
    }

    if(current == NULL){
        puts("Not found!");
        exit(EXIT_FAILURE);
    }

    if(current->left == NULL && current->right == NULL){
        //current = NULL;

        *link = NULL;//set the node point to null

        free(current);
        printf("Delete value[%d] in node alonely!\n", value);
        return;
    }

    if(current->left == NULL && current->right != NULL){
        *link = current->right;
        free(current);
        printf("Delete value[%d] in right node!\n", value);
        return;
    }

    if(current->right == NULL && current->left != NULL){
        *link = current->left;
        free(current);
        printf("Delete value[%d] in left node!\n", value);
        return;
    }

    if(current->right != NULL && current->left != NULL){
        // We must set the largest node in the left childs


        while(current != NULL){
            parent = current;
            temp = parent->value;
            current = parent->right;
        }

        delete_valueintree(temp);// this must be

        (*link)->value = temp;
        
        printf("Delete value[%d] in Remove!\n", value);
        return;
    }
}

void insert(TREE_TYPE value){
    int flag = 0;
    struct TREE *current;
    struct TREE **next;

    next = &tr;

    while((current = *next) != NULL){
        if(value < current->value){
            next = &current->left;
            flag = 1;
        }
        else{
            assert(value != current->value);
            next = &current->right;
            flag = 2;
        }
    }
    
    current = (struct TREE *)malloc(sizeof(struct TREE));
    assert(current);
    current->value = value;
    current->left = NULL;
    current->right = NULL;
    *next = current;
    printf("Add new child[%d] in %s successfully!\n", value, flag == 0?"Root":(flag == 1?"Left":"Right"));
}


/*
*当tr1为null时, 特殊情况特殊处理

*当tr1不是null时，我们需要找到新节点需要重新放置的位置

*当值稍小时， 往左放，否则，往右放，当找到空节点时就ok了

* 此时我们需要将新节点挂上去, 如何挂上去, 把那个指向那个位置的指针的内容换掉 * 就可以了，使用指向指针的指针就可以

*/ 

void myinsert(TREE_TYPE value){
    struct TREE *current;
    struct TREE **link;

    if(tr1 == NULL){
        current = (struct TREE *)malloc(sizeof(struct TREE));
        assert(current);

        current->value = value;
        current->left = NULL;
        current->right = NULL;

        tr1 = current;
        return;
    }
    
    link = &tr1;

    while((current = *link) != NULL){
        if(value < current->value){
            link = &current->left;
        }
        else{
            assert(value != current->value);
            link = &current->right;
        }
    }
    
    current = (struct TREE *)malloc(sizeof(struct TREE));
    assert(current);

    current->value = value;
    current->left = NULL;
    current->right = NULL;

    *link = current;
}

void do_qianxu(struct TREE *current, void (*callback)(TREE_TYPE value)){
    if(current != NULL){
        callback(current->value);
        do_qianxu(current->left, callback);
        do_qianxu(current->right, callback);    
    }
}

void do_zhongxu(struct TREE *current, void (*callback)(TREE_TYPE value)){
    if(current != NULL){
        do_zhongxu(current->left, callback);
        callback(current->value);
        do_zhongxu(current->right, callback);
    }
}

void do_houxu(struct TREE *current, void (*callback)(TREE_TYPE value)){
    if(current != NULL){
        do_houxu(current->left, callback);
        do_houxu(current->right, callback);
        callback(current->value);
    }
}

void pre_order_traverse(void (*callback)(TREE_TYPE value)){
    printf("[Mid Left Right]:");
    do_qianxu(tr, callback);
    putchar('\n');
    printf("[Left Mid Right]:");
    do_zhongxu(tr, callback);
    putchar('\n');
    printf("[Left Right Mid]:");
    do_houxu(tr, callback);
    putchar('\n');

}

void mycb(TREE_TYPE value){
    printf("%d ", value);
}


int getdepth(struct TREE *root){
    if(root == NULL)
        return 0;
    else if(root != NULL && root->left == NULL && root->right == NULL)
        return 1;
    else
        return 3 + getdepth(root->left) + getdepth(root->right);
}

int getwidth(struct TREE *root){
    
    return 0;
}