算法10---二叉搜索树

  1 #include <stdio.h>  2 #include <stdlib.h>  3   4 #ifndef _Tree_H  5   6 struct treenode;  7 typedef  struct treenode *position;  8 typedef struct treenode *searchtree;  9  10  11  12 searchtree makeempty(searchtree T);//二叉搜索树置空 13 position find(searchtree T,int key);//在二叉搜索树内查找key 14 position find_in_recursion(searchtree T,int key);//递归查找 15 position findmin(searchtree T);//找二叉搜索树内最小值 16 position findmax(searchtree T);//找二叉搜索树内最大值 17 searchtree tree_successor(searchtree T);//二叉搜索树内后继节点 18 searchtree tree_predecessor(searchtree T);//二叉搜索树内前驱 19  20 position insertposition(searchtree T,int key);//用于找到key值的插入点 21 void insert(searchtree T,int key);//插入值，非递归方法 22 searchtree insert_recursion(searchtree T,int key);//递归方法插入值 23 void transplant(searchtree T,position u,position v);//使用节点v代替u 24 void tree_delete(searchtree T,int key);// 25  26 void inorder_tree_work(searchtree T);//中序遍历二叉搜索树 27  28  29 #endif 30  31  32 typedef struct treenode 33 { 34     int key; 35     int data; 36     searchtree left; 37     searchtree right; 38     searchtree parent; 39 }treenode; 40  41  42 //中序遍历 43 void inorder_tree_work(searchtree T) 44 { 45     if (T!=NULL) 46     { 47         inorder_tree_work(T->left); 48         printf("%d\n",T->key); 49         inorder_tree_work(T->right); 50     } 51 } 52  53  54 //清空搜索树 55  56 searchtree makeempty(searchtree T) 57 { 58     if (T!=NULL) 59     { 60         makeempty(T->left); 61         makeempty(T->right); 62         free(T); 63     } 64     return NULL; 65 } 66  67 //查找，一种方法是递归，一种方法是非递归 68 //我们先采用递归的方法 69 position find(searchtree T,int key) 70 { 71     if (T==NULL||key==T->key) 72     { 73         return T; 74     } 75     if (key<T->key) 76     { 77         return find(T->left,key); 78     } 79     else 80         return find(T->right,key); 81 } 82  83  84 position find_in_recursion(searchtree T,int key) 85 { 86     while (T!=NULL&&key!=T->key) 87     { 88         if (key<T->key) 89         { 90             T=T->left; 91         } 92         else 93             T=T->right; 94     } 95     return T; 96 } 97  98  99 //找二叉搜索树中的最大值和最小值也有递归和非递归的方法，不过我们在这采用非递归的方法；100 101 position findmin(searchtree T)102 {103     while (T->left!=NULL)104     {105         T=T->left;106     }107     return T;108 }109 110 position findmax(searchtree T)111 {112     while (T->right!=NULL)113     {114         T=T->right;115     }116     return T;117 }118 119 120 //找二叉搜索树的前驱和后驱节点121 122 position tree_successor(position T)123 {124     if (T->right!=NULL)125     {126         return findmax(T->right);127     }128     position y;129     y=T->parent;130     while(y!=NULL&&T==y->right)131     {132         T=y;133         y=y->parent;134     }135     return y;136 }137 138 position tree_predecessor(position T)139 {140     if (T->right!=NULL)141     {142         return findmin(T->left);143     }144     position y;145     y=T->parent;146     while(y!=NULL&&T==y->left)147     {148         T=y;149         y=y->parent;150     }151     return y;152 }153 154 //先采用递归的方法155 156 searchtree insert_recursion(searchtree T,int key)157 {158     if (T==NULL)159     {160         T=(treenode *)malloc(sizeof(struct treenode));161         if (T==NULL)162         {163             printf("out of space!\n");164             return NULL;165         }166         else167         {168             T->key=key;169             T->left=T->right=NULL;170         }171     }172     else if (key<T->key)173     {174         T->left=insert_recursion(T->left,key);175     }176     else177         T->right=insert_recursion(T->right,key);178 179 180     return T;181 182 }183 184 position insertposition(searchtree T,int key)185 {186     position s;187     position p = T;188     while(p!=NULL)189     {190         s=p;191         if (p->key==key)192         {193             return NULL;194         }195         p=(key<p->key)? p->left:p->right;196     }197     return s;198 }199 200 void insert(searchtree T,int key )201 {202     position p=insertposition(T,key);203     position y=NULL;204     position x=T;205     while(x!=NULL)206     {207         y=x;208         if (key<x->key)209         {210             x=x->left;211         }212         else213             x=x->right;214     }215     p->parent=y;216     if (y==NULL)217     {218         T=p;219     }220     else if (p->key<y->key)221     {222         y->left=p;223     }224     else225         y->right=p;226 227 }228 229 //二叉搜索树的删除操作230 void transplant(searchtree T,position u,position v)//使用节点v代替u231 {232     if (u->parent==NULL)233     {234         T=u;235     }236     else if (u==u->parent->left)237     {238         u->parent->left=v;239     }240     else241         u->parent->right=v;242     if (v!=NULL)243     {244         v->parent=u->parent;245     }246 }247 248 void tree_delete(searchtree T,int key)//二叉搜索树的删除操作249 {250     position p=insertposition(T,key);251     if (p->left==NULL)252         transplant(T,p,p->right);253     else if (p->right==NULL)254         transplant(T,p,p->left);255     else256     {257         position y=findmin(p->right);258         if (y->parent!=p)259         {260             transplant(T,y,y->right);261             y->right=p->right;262             y->right->parent=y;263         }264         transplant(T,p,y);265         y->left=p->left;266         y->left->parent=y;267     }   268 }269 270 int main()271 {272     return 0;273 274 }