#include <iostream>
using namespace std;
typedef char T;
struct Node{
T data;
Node * L;
Node * R;
Node(const T& d):data(d),L(),R(){}
Node(const T& d,Node *l,Node *r):data(d),L(l),R(r){}
};
class bst{
typedef Node* tree;
Node *rp;
int n;
public:
bst():rp(),n(){}
void clear(){clear(rp);n = 0;}
~bst(){clear()}
void insert(const T&d){insert(rp,new Node(d));++n}
tree& find(const T& d){return find(rp,d);}
void travel()const{travel(rp);cout<<endl;}
bool empty()const{return rp==NULL}
bool remove(const T&d)
{
tree &t = find(d);
if(t==NULL)return false;
Node * p = t;
if(t->L != NULL)insert(t->R,t->L);
t = t->R;
delete p;
--n;
return true;
}
const T& root()const{if(!rp) throw"空";return rp->data;}
int size()const{return n;};
void update(const T&olddata,const T&newdata)
{
if(remove(olddata)) insert(newdata);
}
void insert(tree t,Node *p){
if(t==NULL) t = p;
else if(p->data < t->data) insert(t->L,p);
else insert(t->R,p);
}
tree& find(tree& t,const T&d)//返回以d为根节点的根指针
{
if(t == null)return t;
else if(d==t->data) return t;
else if(d<t->data) return find(t->L,d);
else return find(t->R,d);
}
void travel(tree t)const{
if(t != NULL){
travel(t->L);
cout << t->data << '';
travel(t->R);
}
}
void clear(tree& t){
if(t != NULL){
clear(t->L);
clear(t->R);
delete t;t = NULL;
}
}
int high(tree t)
{
if(t == NULL)return 0 ;
int lh = high(t->L);
int rh = high(t->R);
return 1 + (lh > rh?lh:rh);
}
};
int main()
{
bst b;
b.insert('k');b.insert('s');b.insert('f');b.insert('t');
b.insert('a');b.insert('m');b.insert('x');b.insert('e');
b.travel();
b.update('a','z');
b.travel();
while(!b.empty())
b.remove(b.root());
cout << "size:" << b.size() << endl;
b.travel();
}