二叉搜索树的插入问题

yyaadet

1. 
   
2. binarytree.h
   
3. struct tree
   
4. {
   
5.         int data;
   
6.         int visited;      //0 visited ,1 unvisited
   
7.         struct tree *left,*right;
   
8. };
   
9. typedef struct tree Tree;
   
10. 
    
11. int bs_search(Tree *base , int key,Tree **p);
    
12. void insert(Tree **base, int key);
    
13. int delete_bst(Tree **base ,int key);
    
14. 
    
15. int delete(Tree **p);
    
16. void travel(Tree *base);  //inorder
    
17. void initial(Tree **base);
    
18. 
    
19. binarytree.c
    
20. #include<stdio.h>
    
21. #include<stdlib.h>
    
22. #include "binarytree.h"
    
23. 
    
24. //1 declare success ,0 declare fail
    
25. int bs_search(Tree *base , int key,Tree **p)
    
26. {
    
27.         if(base==NULL)
    
28.         {
    
29.                 *p=NULL;
    
30.                 return 0;
    
31.         }
    
32.         else
    
33.         {
    
34.                 Tree *temp,*parent;
    
35.                 temp=base;
    
36.                 while(temp!=NULL)
    
37.                 {
    
38.                         if(temp->data==key)
    
39.                         {
    
40.                                 *p=temp;
    
41.                                 return 1;
    
42.                         }
    
43.                         else if(temp->data<key)
    
44.                         {
    
45.                                 parent=temp;
    
46.                                 temp=temp->right;
    
47.                         }
    
48.                         else
    
49.                         {
    
50.                                 parent=temp;
    
51.                                 temp=temp->left;
    
52.                         }
    
53.                 }
    
54.                 *p=parent;
    
55.                 return 0;
    
56.         }
    
57. }
    
58. 
    
59. void insert(Tree **base,int key)
    
60. {
    
61.         Tree **p;
    
62.         Tree *temp;
    
63.         p=(Tree **)malloc(sizeof(Tree));
    
64.         if(bs_search(*base,key,p)==0)
    
65.         {
    
66.                 Tree *s=(Tree *)malloc(sizeof(Tree));
    
67.                 s->right=s->left=NULL;
    
68.                 s->data=key;
    
69.                 s->visited=0;
    
70.                 if(*p==NULL)
    
71.                 {
    
72.                         *base=s;
    
73.                 }
    
74.                 else if(key>(*p)->data)
    
75.                 {
    
76.                         temp=*p;
    
77.                         temp->right=s;
    
78.                 }
    
79.                 else
    
80.                 {
    
81.                         temp=*p;
    
82.                         temp->left=s;
    
83.                 }
    
84.         }
    
85.         free(p);
    
86. }
    
87. 
    
88. void travel(Tree *base)
    
89. {
    
90.         if(base==NULL)
    
91.                 return;
    
92.         else if(base->visited==0)
    
93.         {
    
94.                 base->visited=1;
    
95.                 travel(base->left);
    
96.                 printf(" %d ",base->data);
    
97.                 travel(base->right);
    
98.         }
    
99. }
    
100. 
     
101. int delete_bst(Tree **base , int key)
     
102. {
     
103.         if(*base==NULL)
     
104.                 return 0;
     
105.         else if(key==(*base)->data)
     
106.                 return delete(base);
     
107.         else if(key>(*base)->data)
     
108.                 return delete(&((*base)->right));
     
109.         else
     
110.                 return delete(&((*base)->left));
     
111. }
     
112. 
     
113. int delete(Tree **p)
     
114. {
     
115.         Tree *q;
     
116.         if((*p)->right==NULL)
     
117.         {
     
118.                 q=*p;
     
119.                 *p=(*p)->left;
     
120.                 free(q);
     
121.         }
     
122.         else if((*p)->left==NULL)
     
123.         {
     
124.                 q=*p;
     
125.                 *p=(*p)->right;
     
126.                 free(q);
     
127.         }
     
128.         else
     
129.         {
     
130.                 Tree *s;
     
131.                 q=*p;
     
132.                 s=(*p)->left;
     
133.                 while(s->right!=NULL)
     
134.                 {
     
135.                         q=s;
     
136.                         s=s->right;
     
137.                 }
     
138.                 (*p)->data=s->data;
     
139.                 if(q!=*p)
     
140.                         q->right=s->left;
     
141.                 else
     
142.                         q->left=s->left;
     
143.                 free(s);
     
144.         }
     
145.         return 1;
     
146. }
     
147. 
     
148. void initial(Tree **base)
     
149. {
     
150.         if(*base==NULL)
     
151.                 return;
     
152.         (*base)->visited=0;
     
153.         initial(&((*base)->left));
     
154.         initial(&((*base)->right));
     
155. }
     

复制代码