二叉

二叉搜索树的概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

二叉搜索树还有一个特征：按照中序走的话是一个升序的状态。所以二叉树搜索树可以叫做二叉排序树或二叉查找树。

二叉搜索树的操作及实现 二叉搜索树的结构 首先实现一个结点类，结点类当中包含三个成员变量：结点值、左指针、右指针，同时结点类当中要对成员变量进行初始化，需要实现一个构造函数，用于将结点的左右指针置空和初始化指定结点值。

结点类的代码实现：

复制 //二叉树搜索树结点类 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; //可以给一个构造函数，也可以直接写一个缺省值 };