C++知识点

知识点"/>

C++知识点

C++知识点 – 二叉搜索树

文章目录

• C++知识点 -- 二叉搜索树
• 一、概念
• 二、实现
• • 1.结构
  • 2.成员函数
• 三、二叉搜索树模型
• • 1.K模型
  • 2.KV模型

一、概念

二叉搜索树又称二叉排序树，具有以下性质：
1.若其左子树不为空，则左子树上的所有节点都小于根节点的值；
2.若其右子树不为空，则右子树上的所有节点都大于根节点的值；
3.它的左右子树也分别问二叉搜索树；

注：
1.二叉搜索树最多查找高度次；
2.中序遍历后的序列是从小到大排好序的；
3.二叉搜索树中相同的值只能出现一次；
4.二叉搜索树增删查改的时间复杂度为O(h)，h是树的高度，最坏情况下为O(N)；

二、实现

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:private:Node* _root = nullptr;
};

二叉搜索树的结构如上，其节点的结构包含数据和指向左右子树的指针，需要写构造函数；二叉搜索树的成员包含一个指向根节点的指针。

2.成员函数

1.Insert
非递归版

	bool Insert(const K& key){if (_root == nullptr)//如果根节点为空，则直接插入到根节点处{_root = new Node(key);return true;}Node* parent = nullptr;//记录cur的父节点，便于创建新节点后进行连接Node* cur = _root;while (cur)//寻找合适的空节点{if (key < cur->_Key)//key < cur->_Key向左走{parent = cur;cur = cur->_left;}else if (key > cur->_Key)//key > cur->_Key向右走{parent = cur;cur = cur->_right;}else//树中有相同的节点了，插入失败{return false;}}cur = new Node(key);if (key > parent->_Key)//将新节点连接到树中{parent->_right = cur;}else{parent->_left = cur;}return true;}

二叉搜索树必须将数据插入到空位置；如果根节点为空，直接插入到根节点；根节点不为空，则开始向下寻找空位置，拿插入数据和cur进行对比，大就向右走，小就向左走，如果这个值已存在，则插入失败；
插入成功要返回true，失败返回false；

递归版
由于递归函数是一定需要传参来进行递归的，在类中写成成员函数就会遇到调用时无法访问私有成员变量的问题：

	bool InsertR(Node*& root, const K& key){if (root == nullptr)//root为空，找到空位置，开始插入新节点{root = new Node(key);//root的类型是引用，此时root是其父节点的左(右)指针的引用，所以直接将root指向新节点就相当于将新节点连接到树中了return true;}if (key > root->_Key)//root不为空，开始向下寻找合适的空位置{return InsertR(root->_right, key);}else if (key < root->_Key){return InsertR(root->_left, key);}else{return false;}}

上面的成员函数InsertR，在调用时需要传根节点_root，但是_root是私有成员，无法在类外访问，因此递归函数的调用出现了问题，解决方案有如下两种：
1.写一个getRoot函数来得到_root;
2.将InsertR定义为私有，然后再定义一个公有的InsertR来调用私有的InsertR；
这里实现第二种方案：

public:bool InsertR(const K& key){return _InsertR(_root, key);}
private:bool _InsertR(Node*& root, const K& key){if (root == nullptr)//root为空，找到空位置，开始插入新节点{root = new Node(key);//root的类型是引用，此时root是其父节点的左(右)指针的引用，所以直接将root指向新节点就相当于将新节点连接到树中了return true;}if (key > root->_Key)//root不为空，开始向下寻找合适的空位置{return InsertR(root->_right, key);}else if (key < root->_Key){return InsertR(root->_left, key);}else{return false;}}

这里_InsertR中root参数的类型是Node&，这个引用的使用非常巧妙，在函数进行递归时，root是其父节点的左（右）指针的别名，在找到空位置后，直接将root指向新节点，就相当于将父节点的指针指向了新节点，直接就将新节点连接到树中了；

2.InOrder中序遍历

public:void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(const Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_Key << ' ';_InOrder(root->_right);}

3.Find
非递归版

	bool Find(const K& key){Node* cur = _root;while(cur){if (key < cur->_Key){cur = cur->_left;}else if (key > cur->_Key){cur = cur->_right;}else{return true;}}return false;}

递归版

public:bool FindR(const K& key){return _FindR(_root, key);}
private:bool _FindR(const Node* root, const K& key){if (root == nullptr){return false;}if (key < root->_Key){return _FindR(root->_left, key);}else if (key > root->_Key){return _FindR(root->_right, key);}else{return true;}}

4.Erase
非递归版
Erase要分几种情况：
（1）待删除的节点没有孩子；
（2）待删除的节点有一个孩子；

我们把这两种情况归为一类，操作都是将待删除结点的子树托孤给其父节点；

有一种特殊情况：待删除的是根节点_root，此时cur的parent为空，这种情况需要单独判断；
（3）待删除的节点有两个孩子；

此时可以使用替换法，找到待删除节点cur的左子树的最大节点（或右子树的最小节点），将其与cur交换key，然后删除替换的节点；

特殊情况为：删除的节点为根节点，其右子树如上图，需要将minParent赋初值为cur，防止min的left为空，minParent赋不上值；

	bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (key < cur->_Key)//寻找待删除的节点{parent = cur;cur = cur->_left;}else if (key > cur->_Key){parent = cur;cur = cur->_right;}else//找到了待删除的节点{//1.其左子树为空if (cur->_left == nullptr){if (cur == _root)//若待删除的是根节点{_root = cur->_right;//托孤:将cur的右子树托给_root}else{if (cur = parent->_left)//若cur是其父节点的左子树，则托孤给父节点的左指针{parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;cur = nullptr;}//2.其右子树为空else if (cur->_right == nullptr){if (cur == _root)//若待删除的是根节点{_root = cur->_left;//托孤:将cur的左子树托给_root}else{if (cur = parent->_left)//若cur是其父节点的左子树，则托孤给父节点的左指针{parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;cur = nullptr;}//3.左右子树都不为空else{//替换法：找cur左子树的最大值或者右子树的最小值的节点与cur交换，然后删除交换后的替换节点Node* min_parent = cur;//赋初始值为cur的目的是：防止cur的右孩子的左子树为空，右子树不为空，导致min_parent无法赋值Node* min = cur->_right;while (min->_left)//找到cur右子树的最小值{min_parent = min;min = min->_left;}swap(min->_Key, cur->_Key);//交换min和cur的Keyif (min = min_parent->_left)//若min_parent的左子节点为min，则将min的右子树托孤给min_parent的左指针{min_parent->_left = min->_right;}else{min_parent->_right = min->_right;}delete min;min = nullptr;}return true;}}return false;}

递归版
1.删除的节点子节点有空的；

root使用引用的作用：递归到最后一层的时候，root既是需要删除的节点，又是root的父节点的左（右）指针，直接给root赋值就可以实现节点的连接；
root使用引用，也可以解决删除根节点的问题，无需加入其它判断；
2.待删除的节点有两个子节点

这里root作为别名就不起作用了，因为删除的不是root处的节点，而是与root交换的节点（右子树的最小节点）；

在交换后，就要在root的自述中找值为key的节点进行交换，但是上图的方法是不行的，因为在交换后从root开始的树就混乱了，不是二叉搜索树了（4 > 3）；

这是正确写法，因为与root交换的一定在其右子树的最左节点，右子树一定还满足二叉搜索树，从其右子树的根节点开始找就能找见；

这种删除根节点的情况也能解决，在交换后就会root的右子树进行删除；

public:bool EraseR(const K& key){return _EraseR(_root, key);}
private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)//root为空，则没有key节点{return false;}if (key < root->_Key)//小于root的值，去左子树中找{return _EraseR(root->_left, key);}else if (key > root->_Key)//大于root的值，去右子树中找{return _EraseR(root->_right, key);}else//找到了待删除的节点{//1.该节有空的子节点Node* del = root;if (root->_left == nullptr){root = root->_right;//root既是待删除的节点，又是root父节点的左（右）指针，所以直接给root托孤其子节点，就可以实现与父节点的连接}else if (root->_right == nullptr){root = root->_left;}//2.该节点左右均不为空else{//找右子树的最左节点进行替换Node* min = root->_right;while (min){min = min->_left;}swap(min->_Key, root->_Key);return _EraseR(root->_right, key);//在root的右子树中去删除替换的节点}delete del;del = nullptr;return true;}}

5.析构函数
由于涉及到资源申请，所以需要自己写析构函数，采用后序遍历进行析构；

public:~BSTree(){_Destory(_root);}
private:void _Destory(Node* root){if (root == nullptr){return;}return _Destory(root->_left);return _Destory(root->_right);delete root;root = nullptr;}

6.拷贝构造
需要进行深拷贝，前序遍历节点进行拷贝；

public:BSTree(const BSTree<K>& t){_root = _Copy(t._root);}
private:Node* _Copy(const Node* root){if (root == nullptr){return nullptr;}Node* copyNode = new Node(root->_Key);copyNode->_left = _Copy(root->_left);copyNode->_right = _Copy(root->_right);return copyNode;}

由于我们自己写了拷贝构造函数，但是没有显式写构造函数，编译器是不会自行生成默认构造的，还需要我们自己来写：

	//BSTree()//默认构造//{}BSTree() = default;//也可以这样，这是c++11的用法，强制编译器生成默认构造

7.赋值重载

	BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}

三、二叉搜索树模型

1.K模型

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值；
使用场景：判断关键词在不在；
1.刷卡进宿舍楼；
2.检查一篇英文文献的单词拼写是否正确；
上面实现的就是K模型的二叉搜索树；

2.KV模型

每一个关键码key，都有与之对应的值value，即<key, value>的键值对，通过搜索key，来找到对应的value；
使用场景：
1.中英互译；
2.统计水果出现的次数；

KV模型的代码需要对上面的二叉搜索树代码进行一定的更改，将key和value绑定在一起；

namespace KeyValue
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _Key;V _Value;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _Key(key), _Value(value){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:bool Insert(const K& key, const V& value){if (_root == nullptr)//如果根节点为空，则直接插入到根节点处{_root = new Node(key, value);return true;}Node* parent = nullptr;//记录cur的父节点，便于创建新节点后进行连接Node* cur = _root;while (cur)//寻找合适的空位置{if (key < cur->_Key)//key < cur->_Key向左走{parent = cur;cur = cur->_left;}else if (key > cur->_Key)//key > cur->_Key向右走{parent = cur;cur = cur->_right;}else//树中有相同的节点了，插入失败{return false;}}cur = new Node(key, value);if (key > parent->_Key)//将新节点连接到树中{parent->_right = cur;}else{parent->_left = cur;}return true;}void InOrder(){_InOrder(_root);cout << endl;}Node* Find(const K& key)//find要返回对应节点的指针{Node* cur = _root;while (cur){if (key < cur->_Key){cur = cur->_left;}else if (key > cur->_Key){cur = cur->_right;}else{return cur;}}return nullptr;}private:void _InOrder(const Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_Key << ':' << root->_Value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};}

测试代码

void testBSTree2()
{KeyValue::BSTree<string, string> dict;dict.Insert("sort", "排序");dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("string", "字符串");dict.Insert("insert", "插入");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << "对应的中文：" << ret->_Value << endl;}else{cout << "无此单词！" << endl;}}
}

结果

注：要结束while (cin >> str)的循环流插入，可以输入CTRL + Z，再输入一个换行（或者直接CTRL + C结束进程）；