#include <iostream>
using namespace std;
struct node
{
node(int i,char *item2):data(i),data2(item2),left(NULL),right(NULL){}
int data;
char *data2;
node *left; //左孩子结点
node *right; //右孩子结点
void inorder(node *&root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->data<<' '<<root->data2<<endl;
inorder(root->right);
}
}
void insert(node *&ptr,int item,char item2[10]) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item,item2);
else if(item<ptr->data)
insert(ptr->left,item,item2);
else insert(ptr->right,item,item2);
}
node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用
{
if(ptr->data==item)
return ptr;
else if(item<ptr->data)
findy(ptr->left,item);
else findy(ptr->right,item);
}
void dele(node *&ptr) //删除值为item所在结点
{
if(ptr->left==NULL&&ptr->right==NULL)
ptr=NULL;
else if(ptr->right==NULL)
ptr=ptr->left;
else if(ptr->left==NULL)
ptr=ptr->right;
else
{
node *temp=ptr->left;
ptr=ptr->right;
node *temp2=ptr;
while(temp2->left!=NULL)
temp2=temp2->left;
temp2->left=temp;
}
}
node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。

{
if(ptr==NULL)
return NULL;
if(ptr->data==item)
return ptr;
else if(item<ptr->data)
find(ptr->left,item);
else find(ptr->right,item);
}
};
int main()
{
char a,b[100][10];
int t,i=0,j;
cout<<"输入结点个数:";
cin>>t;
cout<<"输入"<<t<<"个结点，结点之间用回车隔开（结点格式例子1,li):"<<endl; cin>>j>>a>>b[0];
node *x=new node(j,b[0]);
for(;i<t-1;i++)
{
cin>>j>>a>>b[i+1];
x->insert(x,j,b[i+1]);
}
cout<<"中序遍历为:"<<endl;
x->inorder(x); //作中序遍历
cout<<"\n输入要删除的结点元素关键值(输入-1程序结束):";
cin>>j;
while(j!=-1)
{
node *t=x->find(x,j); //定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j);
x->dele(y);
cout<<"中序遍历为:"<<endl;
x->inorder(x);
}
else
cout<<"无"<<j;
cout<<"\n输入要删除的结点元素关键值(输入-1程序结束):";
cin>>j;
}
return 0;
}。