1 /*************************************************************************  2   这是一个二叉查找树，实现了以下操作：插入结点、构造二叉树、删除结点、查找、  3   查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时间复杂度  4   均为o(h),其中h是树的高度  5   注释很详细，具体内容就看代码吧  6 *************************************************************************/  7   8 #include<stdio.h>  9 #include<stdlib.h> 10  11 //二叉查找树结点描述 12 typedef int KeyType; 13 typedef struct Node 14 { 15     KeyType key;          //关键字 16     struct Node * left;   //左孩子指针 17     struct Node * right;  //右孩子指针 18     struct Node * parent; //指向父节点指针 19 }Node,*PNode; 20  21 //往二叉查找树中插入结点 22 //插入的话，可能要改变根结点的地址，所以传的是二级指针 23 void inseart(PNode * root,KeyType key) 24 { 25     //初始化插入结点 26     PNode p=(PNode)malloc(sizeof(Node)); 27     p->key=key; 28     p->left=p->right=p->parent=NULL; 29     //空树时，直接作为根结点 30     if((*root)==NULL){ 31         *root=p; 32         return; 33     } 34     //插入到当前结点（*root）的左孩子 35     if((*root)->left == NULL && (*root)->key > key){ 36         p->parent=(*root); 37         (*root)->left=p; 38         return; 39     } 40     //插入到当前结点（*root）的右孩子 41     if((*root)->right == NULL && (*root)->key < key){ 42         p->parent=(*root); 43         (*root)->right=p; 44         return; 45     } 46     if((*root)->key > key) 47         inseart(&(*root)->left,key); 48     else if((*root)->key < key) 49         inseart(&(*root)->right,key); 50     else 51         return; 52 } 53  54 //查找元素,找到返回关键字的结点指针，没找到返回NULL 55 PNode search(PNode root,KeyType key) 56 { 57     if(root == NULL) 58         return NULL; 59     if(key > root->key) //查找右子树 60         return search(root->right,key); 61     else if(key < root->key) //查找左子树 62         return search(root->left,key); 63     else 64         return root; 65 } 66  67 //查找最小关键字,空树时返回NULL 68 PNode searchMin(PNode root) 69 { 70     if(root == NULL) 71         return NULL; 72     if(root->left == NULL) 73         return root; 74     else  //一直往左孩子找，直到没有左孩子的结点 75         return searchMin(root->left); 76 } 77  78 //查找最大关键字,空树时返回NULL 79 PNode searchMax(PNode root) 80 { 81     if(root == NULL) 82         return NULL; 83     if(root->right == NULL) 84         return root; 85     else  //一直往右孩子找，直到没有右孩子的结点 86         return searchMax(root->right); 87 } 88  89 //查找某个结点的前驱 90 PNode searchPredecessor(PNode p) 91 { 92     //空树 93     if(p==NULL) 94         return p; 95     //有左子树、左子树中最大的那个 96     if(p->left) 97         return searchMax(p->left); 98     //无左子树,查找某个结点的右子树遍历完了 99     else{100         if(p->parent == NULL)101             return NULL;102         //向上寻找前驱103         while(p){104             if(p->parent->right == p)105                 break;106             p=p->parent;107         }108         return p->parent;109     }110 }111 112 //查找某个结点的后继113 PNode searchSuccessor(PNode p)114 {115     //空树116     if(p==NULL)117         return p;118     //有右子树、右子树中最小的那个119     if(p->right)120         return searchMin(p->right);121     //无右子树,查找某个结点的左子树遍历完了122     else{123         if(p->parent == NULL)124             return NULL;125         //向上寻找后继126         while(p){127             if(p->parent->left == p)128                 break;129             p=p->parent;130         }131         return p->parent;132     }133 }134 135 //根据关键字删除某个结点,删除成功返回1,否则返回0136 //如果把根结点删掉，那么要改变根结点的地址，所以传二级指针137 int deleteNode(PNode* root,KeyType key)138 {139     PNode q;140     //查找到要删除的结点141     PNode p=search(*root,key);142     KeyType temp;    //暂存后继结点的值143     //没查到此关键字144     if(!p)145         return 0;146     //1.被删结点是叶子结点，直接删除147     if(p->left == NULL && p->right == NULL){148         //只有一个元素，删完之后变成一颗空树149         if(p->parent == NULL){150             free(p);151             (*root)=NULL;152         }else{153             //删除的结点是父节点的左孩子154             if(p->parent->left == p)155                  p->parent->left=NULL;156             else  //删除的结点是父节点的右孩子157                  p->parent->right=NULL;158             free(p);159         }160     }161 162     //2.被删结点只有左子树163     else if(p->left && !(p->right)){164         p->left->parent=p->parent;165         //如果删除是父结点，要改变父节点指针166         if(p->parent == NULL)167             *root=p->left;168         //删除的结点是父节点的左孩子169         else if(p->parent->left == p)170             p->parent->left=p->left;171         else //删除的结点是父节点的右孩子172             p->parent->right=p->left;173         free(p);174     }175     //3.被删结点只有右孩子176     else if(p->right && !(p->left)){177         p->right->parent=p->parent;178         //如果删除是父结点，要改变父节点指针179         if(p->parent == NULL)180             *root=p->right;181         //删除的结点是父节点的左孩子182         else if(p->parent->left == p)183             p->parent->left=p->right;184         else //删除的结点是父节点的右孩子185             p->parent->right=p->right;186         free(p);187     }188     //4.被删除的结点既有左孩子，又有右孩子189     //该结点的后继结点肯定无左子树(参考上面查找后继结点函数)190     //删掉后继结点,后继结点的值代替该结点191     else{192         //找到要删除结点的后继193         q=searchSuccessor(p);194         temp=q->key;195         //删除后继结点196         deleteNode(root,q->key);197         p->key=temp;198     }199     return 1;200 }201 202 //创建一棵二叉查找树203 void create(PNode* root,KeyType *keyArray,int length)204 {205     int i;206     //逐个结点插入二叉树中207     for(i=0;i<length;i++)208         inseart(root,keyArray[i]);209 }210 211 int main(void)212 {213     int i;214     PNode root=NULL;215     KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};216     create(&root,nodeArray,11);217     for(i=0;i<2;i++)218         deleteNode(&root,nodeArray[i]);219     printf("%d\n",searchPredecessor(root)->key);220     printf("%d\n",searchSuccessor(root)->key);221     printf("%d\n",searchMin(root)->key);222     printf("%d\n",searchMax(root)->key);223     printf("%d\n",search(root,13)->key);224     return 0;225 }