/*******************************************
=================JJ日記=====================
作者: JJDiaries(阿呆)
郵箱：JJDiaries@gmail.com
日期: 2013-11-13
============================================
二叉查找樹，支持的操作包括：SERACH、MINIMUM、
MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE。
定理：對于一個高度為h的二叉查找樹，操作SERACH、MINIMUM、
MAXIMUM、PREDECESSOR、SUCCESSOR的運行時間均為O(h)
*******************************************/

/*================JJ日記=====================
作者: JJDiaries(阿呆)
郵箱：JJDiaries@gmail.com
日期: 2013-11-13
============================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDLEN 16
//定義一個節點，除了存放key值外，還包含了一個data字符數組用于存放一個單詞
struct node{
    int key;
    char data[WORDLEN];
    struct node *parent;
    struct node *left;
    struct node *right;
};
typedef struct node * tree;

/*============================================
樹的中序遍歷
INORDER_TREE_WALK(x)
    if x!=NIL
        then INORDER_TREE_WALK(left[x])
             print key[x]
             INORDER_TREE_WALK(left[x])
============================================*/   
void inorder_tree_walk(tree T)
{
    if(T!=NULL){
        inorder_tree_walk(T->left);
        printf("key:%d   words:%s/n",T->key,T->data);
        inorder_tree_walk(T->right);
    }
}

/*============================================
樹的搜索，返回含有關鍵字k的結點
TREE_SEARCH(x,k) //遞歸版本
    if x=NIL or k =key[x]
        then return x
    if k<key[x]
        then return TREE_SEARCH(left[x],k)
        else return TREE_SEARCH(right[x],k)

TREE_SEARCH(x,k) //非遞歸版本
    while x!=NIL and k!= key[x]
        do if k<key[x]
            then x <―― left[x]
            else x <―― right[x]
    return x
============================================*/
//遞歸版本
struct node* tree_search(tree T,int k)
{
    if(T==NULL || k == T->key)
        return T;
    if(k < T->key)
        return tree_search(T->left,k);
    else
        return tree_search(T->right,k);
}
//非遞歸版本
struct node* tree_search1(tree T,int k)
{
    while(T!=NULL && T->key!=k)
        if(k < T->key)
            T=T->left;
        else
            T=T->right;
    return T;
}

/*============================================
返回key值最小的結點
TREE_MINIMUM(x)
    while left[x]!=NIL
        do x <―― left[x]
    return x
============================================*/   
struct node* tree_minimum(tree T)
{
    while(T->left != NULL)
        T=T->left;
    return T;
}

/*============================================
返回key值最大的結點
TREE_MAXMUM(x)
    while right[x]!=NIL
        do x <―― right[x]
    return x
============================================*/
struct node* tree_maxmum(tree T)
{
    while(T->right != NULL)
        T=T->right;
    return T;
}
/*============================================   
中序遍歷下，返回某一結點的后繼結點
1）如果結點x有右子結點，則其后繼結點為右子樹中最小結點。
2）如果結點x沒有右子樹，且x有一個后繼y，則y是x的最低祖先結點
且y的左兒子也是x的祖先。
TREE_SUCCESSOR(x)
    if right[x] != NIL
        return TREE_MINIMUM(right[x])
    y=p[x]
    while y!=NIL and x=right[y] //如果x=left[y]，那么x的后繼就是y，跳出while循環，直接返回y即可
        do x <―― y
           y <―― p[y]
    return y
============================================*/   
struct node * tree_successor(struct node *T)
{
    if(T->right!=NULL)
        return tree_minimum(T->right);
    struct node *y=T->parent;
    while(y!=NULL && T == y->right){
        T=y;
        y=y->parent;
    }
    return y;
}

/*===========================================
插入操作
思路：從根節點一路往下尋找插入位置，用指針x跟蹤這條尋找路徑，并用指針y指向x的父結點
TREE_INSERT(T,z)
    y=NIL
    x=root[T]
    while x!= NIL //直到x為空，這個空位置即為需要插入的位置
        do y<―― x
            if key[z]<key[x]
                then x <―― left[x]
                else x <―― right[x]
    p[z]=y
    if y=NIL
        then root[T]=z //樹T為空時的情況
        else if key[z] < key[y]
            then left[y]=z //小于y的插在左邊，大于的插在右邊
            else right[y]=z
============================================*/   
void tree_insert(tree *PT,struct node *z)
{
    if(*PT==NULL){//樹為空，則將z作為根結點返回
        *PT=z;
        return;
    }
    struct node *y=NULL;
    struct node *x=*PT;
    while(x!=NULL){
        y=x;
        if(z->key < x->key)
            x=x->left;
        else
            x=x->right;
    }
    z->parent=y;
    if(z->key < y->key)
        y->left=z;
    else
        y->right=z;
}

/*===============================================
刪除操作
刪除操作分為三類情況：
1）若要刪除的節點z沒有子女，則只需修改z的父節點的該子女為NIL即可
2）若要刪除的節點z只有一個子女，則只需將z的這個子女與z的父節點連接起來即可
3）若要刪除的節點z有兩個子女，則需要先刪除z的后繼y，再用y的內容替換z的內容。
TREE_DELETE(T,z)
    if left[z]=NIL || right[z]=NIL  //把要刪除的節點先保存在y中
        then y <―― z 
        else y <―― TREE_SUCCESSOR(z)
    if left[y]!=NIL                 //將y的非空子女存放在x中
        then X <―― left[y]
        else x <―― right[y]
    if x!=NIL
        then p[x]=p[y]    //將要刪除節點的子女連接到要刪除節點的父節點上
    if p[y]=NIL     //如果要刪除的節點為根節點
        then root[T] <―― x
        else if y=left[p[y]]//
            then left[p[y]] <―― x
            else right[p[y]] <―― x
    if y!=z  //第三種情況，需要用y的內容替換z的內容
        then key[z] <―― key[y]
            copy y's other data to z
    return y
==============================================*/
struct node * tree_delete(tree *PT,struct node *z)
{
    struct node *delnode,*sonnode;
    if(z->left==NULL || z->right == NULL)//有一個子女或無子女，則要刪除的結點結尾z本身
        delnode=z;
    else                                 //有兩個子女，則要刪除的結點為z的后繼結點
        delnode=tree_successor(z);

    if(delnode->left!=NULL)
        sonnode=delnode->left;
    else
        sonnode=delnode->right;

    if(sonnode!=NULL)
        sonnode->parent=delnode->parent;
    if(delnode->parent==NULL)
        *PT=sonnode;
    else if(delnode->parent->left==delnode)
        delnode->parent->left=sonnode;
    else
        delnode->parent->right=sonnode;
    if(delnode!=z){
        z->key=delnode->key;
        strcpy(z->data,delnode->data);
    }
    return delnode;
}
//初始化一棵樹
tree init_tree(int key)
{   
    struct node * t;
    t=(tree)malloc(sizeof(struct node));
    if(t==NULL)
        return NULL;
    t->key=key;
    t->parent=t->left=t->right=NULL;
    return t;
}
//釋放資源
void fini_tree(tree T)
{
    if(T!=NULL){
        fini_tree(T->left);
        fini_tree(T->right);
        printf("free node(%d,%s) now/n",T->key,T->data);
        free(T);

    }
}
//測試程序
int main()
{
    tree myTree=init_tree(256);
    if(myTree==NULL)
        return 1;
    strcpy(myTree->data,"JJDiaries");
    struct record{
    int key;
    char word[WORDLEN];
    };
    struct record records[]={ {2,"Viidiot"},
                     {4,"linux-code"},
                     {123,"google"},
                     {345,"baidu"},
                     {543,"nsfocus"}
                    };
    int i;
    struct node *tmp;
    for(i=0;i<5;++i){
        tmp=(tree)malloc(sizeof(struct node));
        if(tmp==NULL)
            continue;
        tmp->key=records[i].key;
        strcpy(tmp->data,records[i].word);
        tmp->left=tmp->right=tmp->parent=NULL;
        tree_insert(&myTree,tmp);
    }
    inorder_tree_walk(myTree);
    struct node *del;
    del=tree_delete(&myTree,tree_search(myTree,345));
    printf("Delete node(%d,%s)/n",del->key,del->data);
    free(del);
    inorder_tree_walk(myTree);
    fini_tree(myTree);
}