二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
-
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
-
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
-
它的左右子树也分别为二叉搜索树
二叉搜索树还有一个特征：按照中序走的话是一个升序的状态。所以二叉树搜索树可以叫做二叉排序树或二叉查找树。
二叉搜索树的操作及实现
二叉搜索树的结构
首先实现一个结点类，结点类当中包含三个成员变量：结点值、左指针、右指针，同时结点类当中要对成员变量进行初始化，需要实现一个构造函数，用于将结点的左右指针置空和初始化指定结点值。
结点类的代码实现：
//二叉树搜索树结点类
template<class K>
struct BSTreeNode {
BSTreeNode<K>* _left;//左指针
BSTreeNode<K>* _right;//右指针
K _key;//节点值
//构造函数
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree {
//喜欢在类里进行类型重定义，因为受到类域的限制
typedef BSTreeNode<K> Node;
private:
Node* _root = nullptr; //可以给一个构造函数，也可以直接写一个缺省值
};