关于数据结构:构建二叉排序树及查找删除结点递归二叉链表

#include<iostream>
using namespace std;
#define ENDFLAG '#'
typedef struct ElemType{char key;}ElemType;
typedef struct BSTNode{
    ElemType data;    
    BSTNode *lchild,*rchild;    
}BSTNode,*BSTree;
// 查找
BSTree SearchBST(BSTree T,char 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);                           
}
// 插入
void InsertBST(BSTree &T,ElemType e) {if(!T) {                            
         BSTree S = new BSTNode;                    
         S->data = e;                            
         S->lchild = S->rchild = NULL;    
         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) {
  T=NULL;
  ElemType e;
  cin>>e.key; 
  while(e.key!=ENDFLAG){InsertBST(T, e);              
    cin>>e.key;        
  }          
}
// 删除
void DeleteBST(BSTree &T,char key) {
  BSTree p=T;BSTree f=NULL;                             
  BSTree q;
  BSTree s;
  while(p){if (p->data.key == key) break;            
   f=p;                                        
   if (p->data.key> key)  p=p->lchild;         
   else p=p->rchild;                            
  }
if(!p) return;                             
if ((p->lchild)&& (p->rchild)) {         
     q = p;
     s = p->lchild;
     while (s->rchild)                        
       {q = s; s = s->rchild;}                     
     p->data = s->data;                           
     if(q!=p){q->rchild = s->lchild;}
     else q->lchild = s->lchild;            
     delete s;
  }
else{if(!p->rchild) {q = p; p = p->lchild;}
    else if(!p->lchild) {q = p; p = p->rchild;}
      if(!f) T=p;                               
      else if (q==f->lchild) f->lchild = p;   
      else f->rchild = p;                     
      delete q;
    }
}
// 中序遍历
void InOrderTraverse(BSTree &T){if(T){InOrderTraverse(T->lchild);
    cout<<T->data.key;
    InOrderTraverse(T->rchild);
    }
}
int main(){
    BSTree T;
    cout<<"输出若干字符 #完结：";
    CreateBST(T);
    cout<<"有序二叉树中序遍历：";
    InOrderTraverse(T);
    cout<<endl; 
    char key;
    cout<<"待查找字符：";
    cin>>key;
    BSTree result=SearchBST(T,key);
    if(result)
    {cout<<"找到字符"<<key<<endl;}
    else
    {cout<<"未找到字符"<<key<<endl;}
    cout<<"待删除字符：";
    cin>>key;
    DeleteBST(T,key);
    cout<<"有序二叉树中序遍历：";
    InOrderTraverse(T);
}