什么是二叉查找树
　　在数据结构中，有一个奇葩的东西，说它奇葩，那是因为它重要，这是树。而在树中，二叉树又是当中的贵族。二叉树的一个重要应用是它们在查找中的应用，于是有了二叉查找树。 使二叉树成为一颗二叉查找树，需要满足以下两点：
　　对于树中的每个节点X，它的左子树中所有项的值都要小于X中的项；
　　对于树中的每个节点Y，它的右子树中所有项的值都要大于X中的项。
　　二叉查找树的基本操作
　　以下是对于二叉查找树的基本操作定义类，然后慢慢分析是如何实现它们的。
　　template<class T>
　　class BinarySearchTree
　　{
　　public:
　　// 构造函数，初始化root值
　　BinarySearchTree() : root(NULL){}
　　// 析构函数，默认实现
　　~BinarySearchTree() {}
　　// 查找小值，并返回小值
　　const T &findMin() const;
　　// 查找大值，并返回大值
　　const T &findMax() const;
　　// 判断二叉树中是否包含指定值的元素
　　bool contains(const T &x) const;
　　// 判断二叉查找树是否为空
　　bool isEmpty() const { return root ? false : true; }
　　// 打印二叉查找树的值
　　void printTree() const;
　　// 向二叉查找树中插入指定值
　　void insert(const T &x);
　　// 删除二叉查找树中指定的值
　　void remove(const T &x);
　　// 清空整个二叉查找树
　　void makeEmpty() const;
　　private:
　　// 指向根节点
　　BinaryNode<T> *root;
　　void insert(const T &x， BinaryNode<T> *&t) const;
　　void remove(const T &x， BinaryNode<T> *&t) const;
　　BinaryNode<T> *findMin(BinaryNode<T> *t) const;
　　BinaryNode<T> *findMax(BinaryNode<T> *t) const;
　　bool contains(const T &x， BinaryNode<T> *t) const;
　　void printTree(BinaryNode<T> *t) const;
　　void makeEmpty(BinaryNode<T> *&t) const;
　　};
　　findMin和findMax实现
　　根据二叉查找树的性质：
　　对于树中的每个节点X，它的左子树中所有项的值都要小于X中的项；
　　对于树中的每个节点Y，它的右子树中所有项的值都要大于X中的项。
　　我们可以从root节点开始：
　　一直沿着左节点往下找，直到子节点等于NULL为止，这样可以找到小值了；
　　一直沿着右节点往下找，直到子节点等于NULL为止，这样可以找到大值了。
　　如下图所示：

　　在程序中实现时，有两种方法：
　　使用递归实现；
　　使用非递归的方式实现。
　　对于finMin的实现，我这里使用递归的方式，代码参考如下：
　　BinaryNode<T> *BinarySearchTree<T>::findMin(BinaryNode<T> *t) const
　　{
　　if (t == NULL)
　　{
　　return NULL;
　　}
　　else if (t->left == NULL)
　　{
　　return t;
　　}
　　else
　　{
　　return findMin(t->left);
　　}
　　}
　　在findMin()的内部调用findMin(BinaryNode<T> *t)，这样防止了客户端知道了root根节点的信息。上面使用递归的方式实现了查找小值，下面使用循环的方式来实现findMax。
　　template<class T>
　　BinaryNode<T> *BinarySearchTree<T>::findMax(BinaryNode<T> *t) const
　　{
　　if (t == NULL)
　　{
　　return NULL;
　　}
　　while (t->right)
　　{
　　t = t->right;
　　}
　　return t;
　　}
　　在很多面试的场合下，面试官一般都是让写出非递归的版本；而在对树进行的各种操作，很多时候都是使用的递归实现的，所以，在平时学习时，在理解递归版本的前提下，需要关心一下对应的非递归版本。
　　contains实现
　　contains用来判断二叉查找树是否包含指定的元素。代码实现如下：
　　template<class T>
　　bool BinarySearchTree<T>::contains(const T &x， BinaryNode<T> *t) const
　　{
　　if (t == NULL)
　　{
　　return false;
　　}
　　else if (x > t->element)
　　{
　　return contains(x， t->right);
　　}
　　else if (x < t->element)
　　{
　　return contains(x， t->left);
　　}
　　else
　　{
　　return true;
　　}
　　}
　　算法规则如下：
　　首先判断需要查找的值与当前节点值的大小关系；
　　当小于当前节点值时，在左节点中继续查找；
　　当大于当前节点值时，在右节点中继续查找；
　　当找到该值时，直接返回true。
　　insert实现
　　insert函数用来向儿茶查找树中插入新的元素，算法处理如下：
　　首先判断需要插入的值域当前节点值得大小关系；
　　当小于当前节点值时，在左节点中继续查找插入点；
　　当大于当前节点值时，在右节点中继续查找插入点；
　　当等于当前节点值时，什么也不干。
　　代码实现如下：
　　template<class T>
　　void BinarySearchTree<T>::insert(const T &x， BinaryNode<T> *&t) const
　　{
　　if (t == NULL)
　　{
　　t = new BinaryNode<T>(x， NULL， NULL);
　　}
　　else if (x < t->element)
　　{
　　insert(x， t->left);
　　}
　　else if (x > t->element)
　　{
　　insert(x， t->right);
　　}
　　}
　　remove实现
　　remove函数用来删除二叉查找树中指定的元素值，这个处理起来比较麻烦。在删除子节点时，需要分以下几种情况进行考虑（结合下图进行说明）： 如下图所示：

　　需要删除的子节点，它没有任何子节点；例如图中的节点9、节点17、节点21、节点56和节点88；这些节点它们都没有子节点；
　　需要删除的子节点，只有一个子节点（只有左子节点或右子节点）；例如图中的节点16和节点40；这些节点它们都只有一个子节点；
　　需要删除的子节点，同时拥有两个子节点；例如图中的节点66等。
　　对于情况1，直接删除对应的节点即可；实现起来时比较简单的；
　　对于情况2，直接删除对应的节点，然后用其子节点占据删除掉的位置；
　　对于情况3，是比较复杂的。首先在需要被删除节点的右子树中找到小值节点，然后使用该小值替换需要删除节点的值，然后在右子树中删除该小值节点。