C++-二叉搜索树
一、二叉树搜索树
1.1 二叉搜索树的概念
二叉搜索树(BST、Binary Search Tree)又称二叉排序树或二叉查找树，可以是一棵空树，也可以是具有以下性质的特殊二叉树：
1.如果左子树不为空，那么左子树上所有的节点的值(key)都小于根节点的值(key)。 2.如果右子树不为空，那么右子树上所有的节点的值(key)都大于根节点的值(key)。 3.左右子树也是一棵搜索二叉树。 4.搜索二叉树不允许有重复的值(key)。默认的二叉搜索树走中序遍历结果是升序。
1.2 二叉搜索树的操作
对于下面这棵二叉搜索树：
int a[] = { 8,3,1,10,6,4,7,14,13 };1.2.1二叉搜索树的查找
1.如果要查找的值(key)比根节点的值(key)要大，那么往右子树继续查找，如果比根节点的值(key) 小，那么往左子树查找。 2.最多查找高度次，如果走到空还没有找到，说明这个值不在该二叉搜索树里。1.2.2二叉搜索树的插入
两种情况 1.树为空，则直接新增一个节点，并将该节点赋值给根节点。 2.树不为空，先查找插入位置，然后插入新节点。依次插入16、0。插入成功返回true，插入失败返回false。
1.2.3二叉搜索树的删除
首先查找要删除的值是否在树中，如果不在，则返回false。如果在树中，又可能分为以下四种情况： 1.被删除的节点没有左右孩子。 1.被删除的节点只有左孩子。 2.被删除的节点只有右孩子。 3.被删除的节点既有左孩子，又有右孩子。情况1可以和情况2或3合并。合并以后的新情况：
1.被删除的节点只有左孩子，左孩子可能为空树。 2.被删除的节点只有右孩子。 3.被删除的节点既有左孩子，又有右孩子。情况1.被删除的节点只有左孩子，左孩子可能为空树。情况1的删除方法：
情况1存在的特殊情况以及处理方法：根节点只有左子树
情况2.被删除的节点只有右孩子。情况2的处理方式以及情况2的特殊情况的处理方式：
情况3：被删除的节点既有左孩子又有有孩子。情况3的处理方法：
替换法： 1.找到左子树的最大节点(最右节点)，或右子树的最小节点(最左节点)。 2.左子树的最右节点必定是没有右子树的，右子树的最左节点必定是没有左子树的。 3.将被删除的节点替换最右节点或最左节点。 4.删除替换后的最右节点或最左节点。以节点8和找右子树的最左节点为例：
二、二叉搜索树的实现
2.1 二叉搜索树的框架结构
1.二叉树的每个节点的结构
包含：模板参数K、一个显示构造函数、节点的值_key、指向左孩子的节点指针_left、指向右孩子的 节点指针_right。//1.二叉树的每个节点的结构 template<class K> struct BSTreeNode { //构造函数 BSTreeNode(const K& key=K()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} //成员变量 K _key; //key值 BSTreeNode<K>* _left; //指向左孩子 BSTreeNode<K>* _right; //指向右孩子 };2.二叉树的结构
包含：模板参数K、对节点名称的重命名，根节点_root，默认成员函数、功能成员函数//模板参数K template<class K> class BSTree { //对节点重命名 typedef BSTreeNode<K> Node; public: //成员函数 //1.默认成员函数 //构造函数 BSTree(); //拷贝构造函数 BSTree(const BSTree<K>& tree); //赋值重载函数 BSTree<K>& operator=(BSTree<K> tree); //析构函数 ~BSTree(); //... //2.功能成员函数 //查找 bool Find(const K& key); //插入 bool Insert(const K& key); //删除 bool Erase(const K& key); //中序遍历 void InOrder(); //... private: //成员变量 Node* root = nullptr; };其中功能成员函数又有递归版本和非递归版本。
2.2 实现
2.2.1 Find查找
非递归版本：
//查找 bool Find(const K& key) { Node* cur = _root; while (cur != nullptr) { if (key > cur->_key) { //继续去右子树查找 cur = cur->_right; } else if (key < cur->_key) { //继续去左子树查找 cur = cur->_left; } else { //找到了 return true; } } //没找到 return false; }递归版本：
//递归版本的查找 bool FindR(const K& key) { return _FindR(_root, key); } bool _FindR(Node* root, const K& key) { if (root == nullptr) { return false; } if (root->_key == key) { return true; } else if (root->_key < key) { return _FindR(root->_right, key); } else { return _FindR(root->_left, key); } }2.2.2 插入Insert
非递归版本：
//插入 bool Insert(const K& key) { //如果根为空，直接插入新节点 if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; //记录cur的父节点 Node* prev = _root; while (cur != nullptr) { prev = cur; if (key > cur->_key) { //继续去右子树 cur = cur->_right; } else if (key < cur->_key) { //继续去左子树 cur = cur->_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key > prev->_key) { prev->_right = new Node(key); } else { prev->_left = new Node(key); } return true; }递归版本：
递归版本的插入使用了引用传参，可以在找到插入位置时修改root可以直接插入//递归版本 bool InsertR(const K& key) { return _InsertR(_root, key); } //引用传参，方便插入 bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { //已经找到插入位置，直接插入 root = new Node(key); return true; } if (root->_key == key) { //搜索二叉树不允许有重复值 return false; } else if (root->_key > key) { _InsertR(root->_left, key); } else { _InsertR(root->_right, key); } return true; }2.2.3 删除
非递归版本：
//删除 bool Erase(const K& key) { Node* cur = _root; //指向cur的父节点 Node* prev = _root; while (cur&&cur->_key!=key) { prev = cur; if (cur->_key > key) { //去左子树 cur = cur->_left; } else if (cur->_key < key) { //去右子树 cur = cur->_right; } } if (cur == nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur->_left && cur->_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp = cur->_right; Node* parent = cur; while (tmp->_left != nullptr) { parent = tmp; tmp = tmp->_left; } //交换最左节点和cur节点的值_key swap(cur->_key, tmp->_key); //如果parent没有动，说明cur的第一个右孩子就是最左节点 if (parent == cur) { cur->_right = tmp->_right; } else { //如果parent动了，那么tmp就必定是parent的左孩子 parent->_left = tmp->_right; } delete tmp; } else if (cur->_right) { //只有右孩子 //1.特殊情况：如果cur等于_root if (cur == _root) { _root = cur->_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev->_key > cur->_key) { //是左孩子 prev->_left = cur->_right; } else { //是右孩子 prev->_right = cur->_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur == _root) { _root = cur->_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev->_key > cur->_key) { //是左孩子 prev->_left = cur->_left; } else { //是右孩子 prev->_right = cur->_left; } } delete cur; } return true; }递归版本：
递归版本的删除也使用的引用传参，可以更方便直接删除节点。//删除的递归版本 bool EraseR(const K& key) { return _EraseR(_root, key); } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { //没找到要删除的节点 return false; } if (root->_key > key) { return _EraseR(root->_left, key); } else if (root->_key < key) { return _EraseR(root->_right, key); } else { Node* cur = root; //找到了要删除的节点 if (root->_left && root->_right) { //有左右孩子 //1.找右子树的最左节点 Node* tmp = root->_right; while (tmp->_left != nullptr) { tmp = tmp->_left; } //交换最左节点和cur节点的值_key swap(root->_key, tmp->_key); //cur的右子树仍然能确保是一棵二叉搜索树，在cur的右子树里递归删除key _EraseR(root->_right, key); } else if (root->_right) { //只有右孩子 root = root->_right; delete cur; } else { //只有左孩子或没有孩子 root = root->_left; delete cur; } return true; } }2.2.4 中序遍历
递归版本：
void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root == nullptr) { return; } _InOrderR(root->_left); cout << root->_key << " "; _InOrderR(root->_right); }2.2.5 构造函数
//构造函数 BSTree() :_root(nullptr) {}2.2.6 拷贝构造函数
二叉搜索树的拷贝构造需要深拷贝。
//拷贝构造函数 BSTree(const BSTree<K>& tree) { //需要进行深拷贝 copy(_root, tree._root); } //root2拷贝至root1 void copy(Node*& root1, Node* root2) { if (root2 == nullptr) { root1 = nullptr; return; } root1 = new Node(root2->_key); copy(root1->_left, root2->_left); copy(root1->_right, root2->_right); }2.2.7 赋值重载函数
//赋值重载函数 BSTree<K>& operator=(BSTree<K> tree) { swap(_root, tree._root); return *this; }2.2.8 析构函数
//析构函数 ~BSTree() { destroy(_root); } void destroy(Node*& root) { if (root == nullptr) { return; } destroy(root->_left); destroy(root->_right); delete root; root = nullptr; }2.2.9 整体代码
//1.二叉树的每个节点的结构 template<class K> struct BSTreeNode { //构造函数 BSTreeNode(const K& key=K()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} //成员变量 K _key; //key值 BSTreeNode<K>* _left; //指向左孩子 BSTreeNode<K>* _right; //指向右孩子 }; //模板参数K template<class K> class BSTree { //对节点重命名 typedef BSTreeNode<K> Node; public: //构造函数 BSTree() :_root(nullptr) {} //拷贝构造函数 BSTree(const BSTree<K>& tree) { //需要进行深拷贝 copy(_root, tree._root); } //root2拷贝至root1 void copy(Node*& root1, Node* root2) { if (root2 == nullptr) { root1 = nullptr; return; } root1 = new Node(root2->_key); copy(root1->_left, root2->_left); copy(root1->_right, root2->_right); } //赋值重载函数 BSTree<K>& operator=(BSTree<K> tree) { swap(_root, tree._root); return *this; } //析构函数 ~BSTree() { destroy(_root); } void destroy(Node*& root) { if (root == nullptr) { return; } destroy(root->_left); destroy(root->_right); delete root; root = nullptr; } //2.功能成员函数 //查找 bool Find(const K& key) { Node* cur = _root; while (cur != nullptr) { if (key > cur->_key) { //继续去右子树查找 cur = cur->_right; } else if (key < cur->_key) { //继续去左子树查找 cur = cur->_left; } else { //找到了 return true; } } //没找到 return false; } //递归版本的查找 bool FindR(const K& key) { return _FindR(_root, key); } bool _FindR(Node* root, const K& key) { if (root == nullptr) { return false; } if (root->_key == key) { return true; } else if (root->_key < key) { return _FindR(root->_right, key); } else { return _FindR(root->_left, key); } } //插入 bool Insert(const K& key) { //如果根为空，直接插入新节点 if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; //记录cur的父节点 Node* prev = _root; while (cur != nullptr) { prev = cur; if (key > cur->_key) { //继续去右子树 cur = cur->_right; } else if (key < cur->_key) { //继续去左子树 cur = cur->_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key > prev->_key) { prev->_right = new Node(key); } else { prev->_left = new Node(key); } return true; } //递归版本的插入使用了引用传参，可以在找到插入位置时修改root可以直接插入 //递归版本 bool InsertR(const K& key) { return _InsertR(_root, key); } //引用传参，方便插入 bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { //已经找到插入位置，直接插入 root = new Node(key); return true; } if (root->_key == key) { //搜索二叉树不允许有重复值 return false; } else if (root->_key > key) { _InsertR(root->_left, key); } else { _InsertR(root->_right, key); } return true; } //删除 bool Erase(const K& key) { Node* cur = _root; //指向cur的父节点 Node* prev = _root; while (cur&&cur->_key!=key) { prev = cur; if (cur->_key > key) { //去左子树 cur = cur->_left; } else if (cur->_key < key) { //去右子树 cur = cur->_right; } } if (cur == nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur->_left && cur->_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp = cur->_right; Node* parent = cur; while (tmp->_left != nullptr) { parent = tmp; tmp = tmp->_left; } //交换最左节点和cur节点的值_key swap(cur->_key, tmp->_key); //如果parent没有动，说明cur的第一个右孩子就是最左节点 if (parent == cur) { cur->_right = tmp->_right; } else { //如果parent动了，那么tmp就必定是parent的左孩子 parent->_left = tmp->_right; } delete tmp; } else if (cur->_right) { //只有右孩子 //1.特殊情况：如果cur等于_root if (cur == _root) { _root = cur->_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev->_key > cur->_key) { //是左孩子 prev->_left = cur->_right; } else { //是右孩子 prev->_right = cur->_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur == _root) { _root = cur->_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev->_key > cur->_key) { //是左孩子 prev->_left = cur->_left; } else { //是右孩子 prev->_right = cur->_left; } } delete cur; } return true; } //删除的递归版本 bool EraseR(const K& key) { return _EraseR(_root, key); } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { //没找到要删除的节点 return false; } if (root->_key > key) { return _EraseR(root->_left, key); } else if (root->_key < key) { return _EraseR(root->_right, key); } else { Node* cur = root; //找到了要删除的节点 if (root->_left && root->_right) { //有左右孩子 //1.找右子树的最左节点 Node* tmp = root->_right; while (tmp->_left != nullptr) { tmp = tmp->_left; } //交换最左节点和cur节点的值_key swap(root->_key, tmp->_key); //cur的右子树仍然能确保是一棵二叉搜索树，在cur的右子树里递归删除key _EraseR(root->_right, key); } else if (root->_right) { //只有右孩子 root = root->_right; delete cur; } else { //只有左孩子或没有孩子 root = root->_left; delete cur; } return true; } } //中序遍历 void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root == nullptr) { return; } _InOrderR(root->_left); cout << root->_key << " "; _InOrderR(root->_right); } //... private: //成员变量 Node* _root = nullptr; };三、二叉搜索树的应用
3.1 K模型
K模型：K模型即只有key作为关键码，结构中只要存储key即可，关键码即为需要搜到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下:
1.以词库里所有单词作为key，构建一棵搜索二叉树。 2.在二叉树里检索该单词word是否存在，存在则拼写正确，如果不存在，则是该单词拼写错误。3.2 K-V模型
KV模型：每一个关键码key，都有一个与之对应的value，即<key,value>的键值对。
比如英汉词典中的英文和汉语就是对应关系，通过英文可以快速找到对应的中文，<word，chinese>。
再比如统计单词，单词和单词出现的次数也是一对key-value模型，<word，count>。
3.3 改造K模型为K-V模型
删除不需要改变，每个节点的结构需要改变，插入也只需要新增一个参数value和new节点时的参 数，find返回值改为找到的节点的地址，遍历只需要多打印一个value。//1.K-V模型的二叉树的每个节点的结构 template<class K,class V> struct BSTreeNode { //构造函数 BSTreeNode(const K& key = K(),const V& value=V()) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} //成员变量 K _key; //key值 V _value; BSTreeNode<K,V>* _left; //指向左孩子 BSTreeNode<K,V>* _right; //指向右孩子 }; //模板参数K,V template<class K,class V> class BSTree { //对节点重命名 typedef BSTreeNode<K,V> Node; public: //查找 Node* Find(const K& key) { Node* cur = _root; while (cur != nullptr) { if (key > cur->_key) { //继续去右子树查找 cur = cur->_right; } else if (key < cur->_key) { //继续去左子树查找 cur = cur->_left; } else { //找到了，返回当前节点 return cur; } } //没找到 return nullptr; } //插入 bool Insert(const K& key,const V& value) { //如果根为空，直接插入新节点 if (_root == nullptr) { _root = new Node(key,value); return true; } Node* cur = _root; //记录cur的父节点 Node* prev = _root; while (cur != nullptr) { prev = cur; if (key > cur->_key) { //继续去右子树 cur = cur->_right; } else if (key < cur->_key) { //继续去左子树 cur = cur->_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key > prev->_key) { prev->_right = new Node(key, value); } else { prev->_left = new Node(key, value); } return true; } //删除 bool Erase(const K& key) { Node* cur = _root; //指向cur的父节点 Node* prev = _root; while (cur && cur->_key != key) { prev = cur; if (cur->_key > key) { //去左子树 cur = cur->_left; } else if (cur->_key < key) { //去右子树 cur = cur->_right; } } if (cur == nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur->_left && cur->_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp = cur->_right; Node* parent = cur; while (tmp->_left != nullptr) { parent = tmp; tmp = tmp->_left; } //交换最左节点和cur节点的值_key swap(cur->_key, tmp->_key); //如果parent没有动，说明cur的第一个右孩子就是最左节点 if (parent == cur) { cur->_right = tmp->_right; } else { //如果parent动了，那么tmp就必定是parent的左孩子 parent->_left = tmp->_right; } delete tmp; } else if (cur->_right) { //只有右孩子 //1.特殊情况：如果cur等于_root if (cur == _root) { _root = cur->_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev->_key > cur->_key) { //是左孩子 prev->_left = cur->_right; } else { //是右孩子 prev->_right = cur->_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur == _root) { _root = cur->_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev->_key > cur->_key) { //是左孩子 prev->_left = cur->_left; } else { //是右孩子 prev->_right = cur->_left; } } delete cur; } return true; } //中序遍历 void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root == nullptr) { return; } _InOrderR(root->_left); cout << root->_key << root->_value << " "; _InOrderR(root->_right); } //... private: //成员变量 Node* _root = nullptr; };四、二叉搜索树的性能分析
插入和删除都需要先进行查找，因此查找效率变成了代表二叉搜索树的各个操作的性能。
二叉搜索树查找的时间复杂度：O(N)
1.当二叉搜索树接近一棵完全二叉树或满二叉树时，查找效率为O(log(N))。 2.当二叉搜索树是以有序的顺序插入时，查找效率为O(N)。在最坏情况下，二叉搜索树退化为了一只单支树，搜索性能就失去了，时间复杂度是按照最坏的情况进行计算的，因此二叉搜索树的时间复杂度为O(N)。