实验题目：
二叉查找树
[实验目的]
验证二叉查找树相关算法。二叉查找树是一棵可为空的二叉树，若非空则其所有结点之关键 词互异，且中根遍历形成按关键词递增序排列的结点序列。二叉查找树中的任一结点P，它的 左子树中结点的关键词都小于P的关键词，而右子树中结点的关键词都大于P的关键词，并且 结点P的左右子树也都是二叉查找树。
[实验内容及要求]
1. 依次输入int型数数值序列，每输入一给定数值K ，如果K不在二叉查找树中，则在树的 适当位置插入包含K的一个新结点，并输出此二叉查找树的中根遍历序列。
2. 如果K在二叉查找树中，则输出其所在层数，以及此二叉查找树的中根遍历序列。
函数部分：
typedef struct bstree{
int data;
struct bstree* left;
struct bstree* right;
}bst,*pbst;
int str2int(string str){
int data_int=0;
if(str[0]=='-'){
for(int i=1;i<str.length();i++)
{
data_int*=10;
data_int+=(int(str[i])-48);//string 转 int
}
return -data_int;
}else{
for(int i=0;i<str.length();i++)
{
data_int*=10;
data_int+=(int(str[i])-48);//string 转 int
}
}
return data_int;
}
void Root_traversal(pbst head){ //中根遍历
if(head==NULL)
return;
Root_traversal(head->left);
cout<<head->data<<' ';
Root_traversal(head->right);
}
pbst Insert(pbst t,int data,int &stage){ //插入节点
if (t == NULL)
{
t = (pbst)malloc(sizeof(bst));
t->left = t->right = NULL;
t->data = data;
return t;
}
if (data < t->data){
stage++;
t->left = Insert(t->left, data,stage);
}
else if(data > t->data){
stage++;
t->right = Insert(t->right, data,stage);
}
cout<<"element "<<data<<" is in stage "<<stage<<endl;
return t;
}
pbst Createbstree(vector<int>data){ //创建树
int stage=0;
pbst head=NULL;
for (int i = 0; i < data.size(); i++){
stage=0;
head = Insert(head, data[i],stage);
Root_traversal(head);
cout<<endl;
}
return head;
}
调用部分：
string d;
vector<int>data;
cout<<"please input data(to stop input *):";
cin>>d;
while(d[0]!='*'){
data.push_back(str2int(d));
cout<<"please input data(to stop input *):";
cin>>d;
}
pbst head=Createbstree(data);
Root_traversal(head);