#include <iostream>
using namespace std;
// 有序二叉树(二叉搜索树)
class Tree {
public:
	// 构造过程中初始化为空树
	Tree (void) : m_root (NULL), m_size (0) {}
	// 析构过程中销毁剩余节点
	~Tree (void) {
		clear ();
	}
	// 插入数据
	void insert (int data) {
		insert (new Node (data), m_root);
		++m_size;
	}
	// 删除第一个匹配数据，不存在返回false
	bool erase  (int data) {
		Node*& node = find (data, m_root);
		if (node) {
			// 左插右
			insert (node->m_left, node->m_right);
			Node* temp = node;
			// 右提升
			node = node->m_right;
			delete temp;
			--m_size;
			return true;
		}
		return false;
	}
	// 删除所有匹配数据
	void remove (int data) {
		while (erase (data));
	}
	// 清空树
	void clear (void) {
		clear (m_root);
		m_size = 0;
	}
	// 将所有的_old替换为_new
	void update (int _old, int _new) {
		while (erase (_old))
			insert (_new);
	}
	// 判断data是否存在
	bool find (int data) {
		return find (data, m_root) != NULL;
	}
	// 中序遍历
	void travel (void) {
		travel (m_root);
		cout << endl;
	}
	// 获取大小
	size_t size (void) {
		return m_size;
	}
	// 获取树高
	size_t height (void) {
		return height (m_root);
	}
private:
	// 节点
	class Node {
	public:
		Node (int data) : m_data (data),
			m_left (NULL), m_right (NULL) {}
		int m_data; // 数据
		Node* m_left; // 左树
		Node* m_right; // 右树
	};
	void insert (Node* node, Node*& tree) {
		if (! tree)
			tree = node;
		else if (node) {
			if (node->m_data < tree->m_data)
				insert (node, tree->m_left);
			else
				insert (node, tree->m_right);
		}
	}
	// 返回子树tree中值与data相匹配的节点的父节点中
	// 指向该节点的成员变量的别名
	Node*& find (int data, Node*& tree) {
		if (! tree)
			return tree;
		else
		if (data =http://www.mamicode.com/= tree->m_data)>
二叉排序树（插入、删除、更新、遍历、搜索、求树高。。。）