/******************************************* =================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); }