零、前言
我们都知道二叉树只有附加上一些特性才具有实用的价值，而本章主要讲解二叉树进阶的内容-二叉搜索树
一、二叉搜索树概念及分析
- 概念：
二叉搜索树（Binary Search Tree）又称二叉排序树，也称作二叉查找树它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
示图：
性能：
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为O(log n)（理想状态下和完全二叉树形似）
注：对于极端状态下，查找、插入为O(n)（形似单链表）
示图：
二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如map，set等
二、二叉搜索树的详解及模拟
1、二叉搜索树的结构
- 二叉搜索树结点结构：
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; public: bool Insert(const K& key); Node* Find(const K& key); bool Erase(const K& key); void InOrder(); private: void _InOrder(Node* root); Node* _root = nullptr; };
注：由于二叉搜索树的特性，所以二叉搜索树不能修改key
2、二叉树搜索树的构造和析构
- 实现代码：
BSTree() :_root(nullptr) {} BSTree(const BSTree<K>& t) { _root = _Copy(t._root); } BSTree<K>& operator=(BSTree<K> t) { std::swap(_root, t._root); return *this; } ~BSTree() { _Destory(_root); } Node* _Copy(Node* root) { //空结点构建 if (root == nullptr) return nullptr; //构建当前结点 Node* newnode = new Node(root->_key); //递归构建左右子树 newnode->_left = _Copy(root->_left); newnode->_right = _Copy(root->_right); return newnode; } void _Destory(Node*& root) { if (root == nullptr) return; //后序遍历释放结点 _Destory(root->_left); _Destory(root->_right); //释放置空结点 delete root; root = nullptr; }
3、二叉搜索树的查找
- 具体操作过程：
- 若走到空节点，则搜索失败，返回空指针
- 若key大于当前结点的数据域之值，则搜索右子树
- 若key小于当前结点的数据域之值，则搜索左子树
- 若key等于当前结点的数据域之值，则查找成功，返回当前结点地址
- 示图：查找32
- 迭代实现：
Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return cur; } } return nullptr; }
- 递归实现：
Node* FindR(const K& key) { return _FindR(_root,key); } Node* _FindR(Node* root, const K& key) { if (root == nullptr) return nullptr; if (root->_key == key) return root; else if (root->_key > key) return _FindR(root->_left, key); else return _FindR(root->_right, key); }
- 注意：
- 实现子函数便于递归，并且保护私有成员
- 子函数一般建议设置为私有，避免接口暴露
