#include <stdio.h>
#include  <stdlib.h>
#define MAXL 100
typedef int KeyType;
typedef char InfoType[10];
typedef struct 
{	
	KeyType key;                /*KeyType為關(guān)鍵字的數(shù)據(jù)類型*/
	InfoType data;              /*其他數(shù)據(jù)*/
} NodeType;
typedef NodeType SeqList[MAXL];	/*順序表類型*/

int SeqSearch(SeqList R, int n,KeyType k)
{
	int i=n;
	R[0].key=k;
	while(R[i].key!=k)
		i--;
	return i;

}
int BinSearch(SeqList R, int n,KeyType k)
{
	int low=0,high=n-1,mid;
	while (low<=high) 
	{
		mid=(low+high)/2;
		if (R[mid].key==k)   	
			return mid;
		if (R[mid].key>k)     	
			high=mid-1;
		else
			low=mid+1;       	
	}
	return -1;
}

typedef struct node           		/*記錄類型*/
{
	KeyType key;              		
	InfoType data;             	
	struct node *lchild,*rchild;	
} BSTNode;


bool insert(BSTNode *&b,KeyType e)
{
   BSTNode *p,*pre;
   if(b==NULL)
   {b=(BSTNode *)malloc(sizeof(BSTNode));
    b->lchild=b->rchild=NULL;
    b->key=e;
	return true;
   }
   p=b;
   while(p!=NULL)
   {
      if(p->key==e)
		  false;
	  pre=p;
	  if(e<p->key)
		  p=p->lchild;
	  else
		  p=p->rchild;
   }
   p=(BSTNode *)malloc(sizeof(BSTNode));
   p->lchild=p->rchild=NULL;
   p->key=e;
   if(p->key<pre->key)
	   pre->lchild=p;
   else
	   pre->rchild=p;
   return false;
}

void Create_bit(BSTNode *&b,KeyType a[],int n)
{
  b=NULL;
  for(int i=1;i<=n;i++)
	  insert(b,a[i]);


}
int disp[10];
int l=0;
void inord(BSTNode *b)
{
  if(b!=NULL)
  {
    inord(b->lchild );
	disp[l++]=b->key;
	inord(b->rchild);
  }
}
bool Bitsearch(BSTNode *b,KeyType k,BSTNode *&p)
{
   p=b;
   while(p!=NULL)
   {if(p->key==k)
		   return true;
	 if(k<p->key)
		   p=p->lchild;
	 else
		   p=p->rchild;
   }
  return false;
}
void main()
{
	int i,n;
	BSTNode *t,*p;
	SeqList R;
	KeyType a[]={0,11,23,32,45,54,67,73,85,90,100},x=73;
    KeyType b[]={0,34,56,2,13,6,87,44,22};
    n=8;
	for(i=1;i<=n;i++)
		R[i].key=b[i];
	i=SeqSearch(R,n,2);
	n=11;
	for (i=0;i<n;i++)
		R[i].key=a[i];
	i=BinSearch(R,n,x);
	Create_bit(t,b,8);
	inord(t);
	bool k=Bitsearch(t,66,p);

}