1 #include
      
        2 #include
       
         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\n",BT->t);24         return ; 25     }       26     while(q->left!=p&&q->right!=p)27     {       28         if(x
        
         data)29         {     30             if(q->left)31             {    32                 q->t++;33                 q = q->left;34             }  35             else36             {  37                 q->t++;38                 q->left = p; 39             }         40         }        41         else42         {   43             if(q->right)44             {     45                 q = q->right; 46             }     47             else48             {   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\n",k,root->t);61         if(k>root->t+1)62         {63             k=k-root->t-1;64             root=root->right;65         }66         else67         {68             69             root=root->left;70         }71     }72     printf("%d\n",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