#include <iostream>
#include <cstdio>
using namespace std;

typedef struct
{
char key;
}ElemType;

typedef struct BSTNode
{
ElemType data;
BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

int n;

BSTree SearchBST(BSTree T,char key) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if((!T)|| key==T->data.key) return T;       	            	//查找结束
else if (key<T->data.key)  return SearchBST(T->lchild,key);	//在左子树中继续查找
else return SearchBST(T->rchild,key);    		   			//在右子树中继续查找
} // SearchBST

void InsertBST(BSTree &T, ElemType e)
{ //当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
if(!T){
BSTree S = new BSTNode;
S->data = e;
S->lchild = S->rchild = NULL;       //新结点*S作为叶子结点
T = S;
}else if(e.key < T->data.key)
InsertBST(T->lchild, e);
else if (e.key> T->data.key)
InsertBST(T->rchild, e);
}

void CreateBST(BSTree &T)
{  //依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
T = NULL;
ElemType e;
cin >> e.key;
while(e.key!='#'){   //#作为输入结束标志
n++;
InsertBST(T, e);
cin>>e.key;
}
}

void DeleteBST(BSTree &T, char key)
{//从二叉排序树T中删除关键字等于key的结点
BSTree p = T;
BSTree f = NULL;
BSTree q;
BSTree s;
while(p){
if(p->data.key == key)
break;
f = p;                  //*f为*p的双亲结点
if(p->data.key > key)
p = p->lchild;      //在*p的左子树中继续查找
else
p = p->rchild;      //在*p的右子树中继续查找
}
if(!p){
cout<<"并不存在该点"<<endl;
return;
}

if(p->lchild && p->rchild){     //被删结点*p左右子树均不空
q = p;
s = p->lchild;
while(s->rchild){
//向右到尽头
q = s;
s = s->rchild;
}
p->data = s->data;          //s指向被删结点的“前驱”
if(q != p){
q->rchild = s->lchild;
}
else{
q->lchild = s->lchild;
}
delete s;
}
else{                           //被删结点*p无右子树，只需重接其左子树
if(!p->rchild){
q = p;
p = p->lchild;
}
else if(!p->lchild){          //被删结点*p无左子树，只需重接其右子树
q = p;
p = p->rchild;
}
if(!f)
T = p;
else if(q == f->lchild)
f->lchild = p;
else
f->rchild = p;
delete q;
}
n--;
}

//中序遍历
void InOrderTraverse(BSTree &T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data.key;
InOrderTraverse(T->rchild);
}
}

void Print(BSTree &T, int n)
{
int i;
if(T){
Print(T->rchild,n+5);
for(i = 0; i < n; i++){
cout<<(" ");
}
printf("%5c\n",T->data.key);
Print(T->lchild, n+5);
}
}

{
cout<<"-------------------平衡二叉树------------------------"<<endl;
cout<<"1.创建平衡二叉树"<<endl;
cout<<"2.查找元素"<<endl;
cout<<"3.删除元素"<<endl;
cout<<"4.退出"<<endl;
}

int main()
{
BSTree T, result;
int sel,flag = 1;
char key;
while(flag){
cin>>sel;
switch(sel)
{
case 1: cout<<"请输入一行字符，以#结束输入"<<endl;
CreateBST(T);
cout<<"当前有序二叉树中序遍历结果为"<<endl;
InOrderTraverse(T);
cout<<endl;
Print(T, n);
break;
case 2: cout<<"请输入待查找字符"<<endl;
cin>>key;
result=SearchBST(T,key);
if(result)
{cout<<"找到字符"<<key<<endl;}
else
{cout<<"未找到"<<key<<endl;}
break;
case 3: cout<<"请输入待删除的字符"<<endl;
cin>>key;
DeleteBST(T,key);
cout<<"当前有序二叉树中序遍历结果为"<<endl;
InOrderTraverse(T);
cout<<endl;
Print(T, n);
break;
case 4: flag = 0;
break;

}
}
cout<<"谢谢您的使用"<<endl;
return 0;
}