二叉查找树(一)

/******************************************* 
二叉查找树，支持的操作包括：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:%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 kkey)  
        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->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)  
        de