bst.cc

资深C++讲师授课代码

#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(0),R(0){++cnt;}
		static int cnt;
		~Node(){--cnt;}
	};
	Node* root;
	static void clear(Node*& tr){
		if(tr==NULL) return;
		clear(tr->L);
		clear(tr->R);
		delete tr;
		tr = NULL;
	}
	static void travel(Node* tr){
		if(tr==NULL) return;
		travel(tr->L);
		cout << tr->data << ' ';
		travel(tr->R);
	}
	static void insert(Node*& tr, Node* p){
		if(tr==NULL) tr = p;
		else if(p->data < tr->data) insert(tr->L, p);
		else insert(tr->R, p);
	}
public:
	bst():root(NULL){}
	void clear(){clear(root);}
	void travel(){travel(root); cout<<endl;}
	int size(){return Node::cnt;}
	bool empty(){return root==NULL;}
	void insert(const T& d){insert(root, new Node(d));}
	bool erase(const T& d);
	bool find(const T& d);
	bool update(const T& od, const T& nd);
	~bst(){clear();}
};
int bst::Node::cnt = 0;
int main()
{
	bst b;
	b.insert(53);
	b.insert(30);
	b.insert(72);
	b.insert(84);
	b.insert(61);
	b.insert(39);
	b.insert(14);
	b.insert(9);
	b.insert(23);
	b.insert(34);
	b.insert(47);
	b.insert(79);
	b.travel();
	cout << "count:" << b.size() << endl;
}