7-1

#include <iostream>
#include <algorithm>//注意后面使用的sort函数是C++ STL中的内容
using namespace std;

//顺序存储结构
typedef struct{
	int *R; //指向数据元素基址，0号不存元素
	int length ;
}SSTable; //静态顺序表

//输出顺序静态表
void PrintSST(SSTable &ST){
	int i;
	for(i=1; i<=ST.length; i++){
	cout<<ST.R[i]<<" ";
	}
	cout<<endl;
}

//创建顺序静态表
void CreateSST(SSTable &ST, int n){
	int i;
	ST.R = new int(n+1);
	ST.length = n;
	for( i=1; i<=n; i++)
	{
		cin>>ST.R[i];
	}
}

//顺序查找,找不到返回0
int Search_Seq(SSTable &ST, int key)
{
	//--------补充代码--Start------
	for (int i = 1; i <= ST.length; i ++) {
		if (ST.R[i] == key) {
			return i;
		}
	} 
	return 0;
	//--------补充代码--End-------
}

//折半查找算法，找不到返回0
int Search_Bin(SSTable &ST, int key)
{
	//--------补充代码--Start------
	int low = 1, high = ST.length, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (ST.R[mid] == key) {
			return mid;
		}
		else if (ST.R[mid] < key) {
			low = mid + 1;
		}
		else if (ST.R[mid] > key) {
			high = mid - 1;
		}	
	}
	return 0;
	//--------补充代码--End-------
}  


//主函数
int main()
{
	int n,key,select;
	SSTable SST;
	
	while(cin>>select)
	{
		if(select==0)
		return 0;
		else if(select==1)
		{
			cin>>n;
			CreateSST(SST, n);
			PrintSST(SST);
		}
		else if(select==2)
		{
			cin>>key;
			cout<<Search_Seq(SST,key)<<endl;
		}
		else if(select==3)
		{
			cin>>key;
			sort(SST.R+1,SST.R+SST.length+1);//对查找表进行升序排序
			cout<<Search_Bin(SST,key)<<endl;
		}
	}
	return 0;
}

7-2

#include <iostream>
using namespace std;

//二叉排序树结构
typedef struct Node{
	int data; 
	struct Node *lchild,*rchild; 
}BitNode, *BiTree;

//中序遍历
void InOrderTraverse(BiTree T)
{
	if(T!=NULL)
	{
		InOrderTraverse(T->lchild);
		cout<<T->data<<" ";
		InOrderTraverse(T->rchild);
  }
}

/*递归查找二叉排序树T中是否存在key,指针f指向t的双亲,其初始调用值为NULL*/
/*若查找成功，则指针p指向该数据的元素结点，并返回TRUE*/
/*否则，指针p指向查找路径上访问的最后一个结点并返回FALSE*/
int SearchBST(BiTree &T, int key, BiTree f, BiTree &p)
{
//--------补充代码--Start------
	if (T == NULL) {
		p = f;
		return 0;
	}
	else if (key == T->data) {
		p = T;
		return 1;
	}
	else if (key < T->data) {
		return SearchBST(T->lchild, key, T, p);
	}
	else if (key > T->data) {
		return SearchBST(T->rchild, key, T, p);
	}
//--------补充代码--End-------
}

//当二叉排序树t中不存在关键字等于key的数据元素时，插入key并返回TRUE，否则返回FALSE
void InsertBST(BiTree &T, int key)
{
//--------补充代码--Start------
	BiTree s, p;
	if (!SearchBST(T, key, NULL, p)) {
		s = new BitNode;
		s->data = key;
		s->lchild = s->rchild = NULL;
		if (T == NULL) {
			T = s;
		}
		else if (s->data < p->data) {
			p->lchild = s;
		} 
		else if (s->data > p->data) {
			p->rchild = s;
		}
	}
//--------补充代码--End-------
}


//主函数
int main()
{
	int i,n,key,select;
	BiTree p,T=NULL;

	while(cin>>select)
	{
		if(select==0)
			return 0;
		else if(select==1)
		{
			cin>>n;
			for(i=1; i<=n; i++)
			{
				cin>>key;
				//getchar();
				InsertBST(T, key);
			}
		}
		else if(select==2)
		{
			if(T)
			{
				InOrderTraverse(T);
				cout<<endl;
			}
		}
		else if(select==3)
		{
			cin>>key;
		    cout<<SearchBST(T, key, NULL, p)<<endl;
		}
	}
	return 0;
}