#include <iostream>
using namespace std;
typedef int T;
class bst//有序的二叉查找树
{
	struct Node
	{
		T data;
		Node * L;
		Node * R;
		Node(const T&d):data(d),L(),R(){}//将L或R初始化为0
		Node(const T&d,Node * l,Node * r):data(d),L(l),R(r){}
	};
	typedef Node* tree;
	Node * root;//根结点
	int n;//记录节点个数
public:
	bst():root(),n(){}
	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);
	}
	void insert(const T& d)
	{
		insert(root,new Node(d));
		++n;
	}
	tree& find(tree& t,const T& d)//查找,&代表指针本身
	{
		if(t==NULL) return t;//返回tree类型的
		else if(d==t->data) return t;
		else if(d<t->data) return find(t->L,d);
		else return find(t->R,d);
	}
	tree& find(const T& d)
	{
		return find(root,d);
	}
	void travel(tree t) const//遍历
	{
		if(t!=NULL)
		{
			travel(t->L);
			cout<<t->data<<" ";
			travel(t->R);
		}
	}
	void travel()
	{
		travel(root);
		cout<<endl;
	}
	bool empty()const//是否为空
	{
		return root==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;//t指向右子树
		delete p;//删除结点空间
		--n;
		return true;
	}
	int size()const {return n;}
	void update(const T& olddata,const T& newdata)//修改数据
	{
		if(remove(olddata)) insert(newdata);//删除旧的，插入新的
	}
	const T& rdata()const
	{
		if(!root) throw "空";
		return root->data;
	}
	void clear(tree& t)//清空，释放内存
	{
		if(t!=NULL)
		{
			clear(t->L);
			clear(t->R);
			delete t;
			t=NULL;
			cout<<"内存释放完成！\n";
			n=0;
		}
	}
	void clear()
	{
		clear(root);
	}
	int height(tree t)//高度
	{
		if(t==NULL) return 0;
		int lh=height(t->L);
		int rh=height(t->R);
		return 1+(lh>rh?lh:rh);
	}
	int height()
	{
		return height(root);
	}
};

int main()
{
	bst b;
	b.insert(4);//插入
	b.insert(5);
	b.insert(-23);
	b.insert(24);
	b.insert(77);
	b.insert(20);
	b.update(20,28);//20修改为28
	b.remove(4);//删除4的节点
	b.travel();//遍历一下
	cout<<b.rdata()<<endl;
	return 0;
}

g++ -o tree.out tree.cpp

./tree.out