在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树的结点数加１.试写一时间复杂度为Ｏ(logn)的算法，确定树中第k个结点的位置。 算法：当前结点的序列位置等于父结点序列位置+lsize值， 算法关键之处是确定父结点的序列位置：往右搜索时，留下当前结点的序列位置作为父结点序列位置
#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 typedef int Status; typedef struct Node { int data; int lsize; struct Node *llink,*rlink; }Node,*Tree; Status SearchBST(Tree T,int key,Tree f,Tree *p); Status InsertBST(Tree *T,int e); void Search_kth(Tree T,int k); int main() { Tree T; T=(Tree)malloc(sizeof(Node)); T=NULL; int e; printf("What number you want to search--0 to quit:"); scanf("%d",&e); while(e) { if(InsertBST(&T,e)) printf("Done!"); else printf("It`s been inserted already."); printf("\nWhat number you want to search--0 to quit:"); scanf("%d",&e); } int k; printf("\nWhich one you want to search--0 to quit:"); scanf("%d",&k); while(k) { Search_kth(T,k); printf("\nWhich one you want to search--0 to quit:"); scanf("%d",&k); } return 0; } Status SearchBST(Tree T,int key,Tree f,Tree *p) { if(!T) { *p=f; return FALSE; } else if(key==T->data) { *p=T; return TRUE; } else if(key<T->data) { T->lsize++; return SearchBST(T->llink,key,T,p); } else return SearchBST(T->rlink,key,T,p); } Status InsertBST(Tree *T,int e) { Tree p; p=(Tree)malloc(sizeof(Node)); if(!SearchBST(*T,e,NULL,&p)) { Tree s; s=(Tree)malloc(sizeof(Node)); s->data=e; s->llink=s->rlink=NULL; s->lsize=1; if(!p) (*T)=s; else if(e<p->data) p->llink=s; else p->rlink=s; return TRUE; } else return FALSE; } void Search_kth(Tree T,int k) { if(k>0) { int f,cur; Tree p; p=(Tree *)malloc(sizeof(Tree)); p=T; f=0; cur=T->lsize; while(p) { if(cur==k) { printf("The %dth is:%d",k,p->data); break; } else if(k<cur) { p=p->llink; cur=f+p->lsize; } else { if(p->rlink) { f=cur; //算法关键之处是：往右搜索时，留下当前结点的序列位置作为父结点序列位置 p=p->rlink; cur=f+p->lsize; } else { printf("\nk值超出范围."); break; } } } } else printf("\nk值不正确."); }