/*******************************************
=================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
#include
#include
#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:%sn",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 kright,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 != NULL)
        T=T->left;
    return T;
}

/*============================================
返回key值最大的结点
TREE_MAXMUM(x)
    while right[x]!=NIL
        do x 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 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 yright;
    }
    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