王道：OJ15

课时15作业

Description

读取10个元素 87  7 60 80 59 34 86 99 21  3，然后建立二叉查找树，排序后输出3  7 21 34 59 60 80 86 87 99，针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），然后输出2

Input 

标准输入读取10个元素 87  7 60 80 59 34 86 99 21  3

Output 

中序遍历输出有序，每个元素占3个字母位置
3  7 21 34 59 60 80 86 87 99

接着输出2即可（就是元素21的下标），注意2直接在行首输出即可。

#include <stdio.h>
#include <stdlib.h>
typedef int BiElemType;
typedef struct BiTNode
{BiElemType data;struct BiTNode* L_chid;struct BiTNode* R_chid;
}BiTNode,*BiTree;
typedef struct tag//辅助队列
{BiTree q;//存储树对应的结点的地址struct tag *q_next;
}tag_t,*ptag_t;
typedef int ElemType;
typedef struct {ElemType * elem;//存，申请的空间的首地址int tab_length;//存储动态数组里元素的个数
}SSTable;
void ST_Init(SSTable &t,int len)
{t.tab_length=len+1;//多一个空间用于存储哨兵，是为了后面判断简化条件t.elem=(ElemType*) malloc(sizeof (ElemType));
}
void InOrder(BiTree t)
{if(t){InOrder(t->L_chid);printf("%3d",t->data);InOrder(t->R_chid);}
}void Print_table(SSTable t)
{int i;for ( i = 1; i < t.tab_length; i++) {printf("%3d",t.elem[i]);}printf("\n");
}
int Binary_select(SSTable t,ElemType e)
{int low=0,high=t.tab_length-1,mid;while (low<=high)//避免两个指针重合的时候，循环结束还没有确定i{mid=(high+low)/2;if(t.elem[mid]==e){return mid;} else if(t.elem[mid]<e){low=mid+1;} else{high=mid-1;}}}
void Print(SSTable t)
{int i;for ( i = 0; i < t.tab_length; i++) {printf("%3d",t.elem[i]);}printf("\n");
}
int compare(const void* left,const void *right)
{//排序，返回任意两个元素的差值，从小到大排序return *(ElemType*)left-*(ElemType*)right;
}
int main() {BiTree tree=NULL;//永远指向根结点，初始化树结点,为零才可以放入跟结点BiTree p_new;//指向当前放入的结点//队列ptag_t q_head=NULL,q_tail=NULL,q_new=NULL,q_cur;//q_cur用于指向当前的父结点，填满孩子再移动BiElemType c;SSTable t;ST_Init(t,10);int i=1;while (i<11){scanf("%d",&c);t.elem[i]=c;p_new=(BiTree) calloc(1,sizeof (BiTNode));//申请空间用于树结点p_new->data=c;q_new=(ptag_t) calloc(1,sizeof (tag_t));q_new->q=p_new;//存储当前结点的地址if(NULL==tree){//此时队列是空的，存入根结点tree=p_new;q_head=q_new;q_tail=q_new;q_cur=q_new;} else{//当前尾指针（指向上一个结点）的next指向当前结点，再移动尾指针到当前结点q_tail->q_next=q_new;q_tail=q_new;if (NULL==q_cur->q->L_chid){//q_cur->q表示上一个结点q_cur->q->L_chid=p_new;} else if(NULL==q_cur->q->R_chid){q_cur->q->R_chid=p_new;q_cur=q_cur->q_next;}}i++;}
//    InOrder(tree);
//    printf("\n");
//    Print_table(t);qsort(t.elem,t.tab_length,sizeof (ElemType),compare);Print_table(t);int e=21;//scanf("%d",&e);int f=Binary_select(t,e)-1;if(f){printf("%d",f);}return 0;
}