基本二叉搜索树的第K小元素

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef struct node *btlink;
 4 struct node
 5 {
 6     int data;
 7     btlink left;
 8     btlink right;
 9     int t;
10 };
11 
12 btlink BT;
13 void insert(btlink q, int x)
14 {  
15     btlink p = (btlink)malloc(sizeof(node)); 
16     p->data = x; 
17     p->left = NULL; 
18     p->right = NULL;
19     p->t=0;
20     if(q == NULL)
21     {    
22         BT = p; 
23         //printf("BT=%d
",BT->t);
24         return ; 
25     }       
26     while(q->left!=p&&q->right!=p)
27     {       
28         if(x<q->data)
29         {     
30             if(q->left)
31             {    
32                 q->t++;
33                 q = q->left;
34             }  
35             else
36             {  
37                 q->t++;
38                 q->left = p; 
39             }         
40         }        
41         else
42         {   
43             if(q->right)
44             {     
45                 q = q->right; 
46             }     
47             else
48             {   
49                 q->right = p; 
50             }  
51         }    
52     }   
53     return;
54 }
55 void InOrder(btlink root,int k)
56 {
57     
58     while(k!=root->t+1)
59     {
60         //printf("k=%d t=%d
",k,root->t);
61         if(k>root->t+1)
62         {
63             k=k-root->t-1;
64             root=root->right;
65         }
66         else
67         {
68             
69             root=root->left;
70         }
71     }
72     printf("%d
",root->data);
73 }
74 
75 int main()
76 {
77     int n,i,index=0,x;
78     char a[8];
79     scanf("%d",&n);
80     BT=(btlink)malloc(sizeof(node));
81     BT=NULL;
82     for(i=0;i<n;i++)
83     {
84         scanf("%s",a);
85         if(a[0]=='a')
86         {
87             scanf("%d",&x);
88             insert(BT,x);
89         }
90         else if(a[0]=='p')
91         {
92             
93             index++;
94             InOrder(BT,index);
95         }
96     }
97     return 0;
98 }
View Code