C++分析二叉搜索树

目录

二叉搜索树

二叉搜索树结构设计

二叉搜索树操作设计

二叉搜索树的查找

二叉搜索树的插入

二叉搜索树的中序遍历

二叉搜索树的删除

二叉搜索树应用

二叉搜索树的效率

---

二叉搜索树

二叉搜索树，也称二叉排序树

因为二叉搜索树如果执行中序遍历，则是一个升序的结果，所以也称为二叉排序树

二叉搜索树的特点：

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

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

它的左右子树也分别为二叉搜索树，一般情况下，常规二叉搜索树中节点的key值没有重复的情况

二叉搜索树结构设计

 // 定义树每一个节点结构template<class T>struct binarySearchTreeNode{// key值T _key;// 左子树指针binarySearchTreeNode<T>* _left;// 右子树指针binarySearchTreeNode<T>* _right;​//单个节点构造函数binarySearchTreeNode(T key):_key(key), _left(nullptr), _right(nullptr){}};

二叉搜索树操作设计

以下面的数组进行分析

 int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

按顺序依次实现下面的功能：

1. 二叉搜索树的查找

2. 二叉搜索树的插入

3. 二叉搜索树的中序遍历

4. 二叉搜索树的删除

二叉搜索树的查找

设计二叉搜索树时，因为二叉搜索树需要满足key值不重复，所以在插入数值之前需要先实现查找，确保二叉搜索树中当前没有该值

因为二叉搜索树满足左子树的节点值比根节点的值小，右子树的节点值比根节点的值大，所以在查找时可以采用类似二分的思想，假设查找值设为target

1. 如果target > root->_key时，则target出现的位置只可能在右子树

2. 如果target < root->_key时，则target出现的位置只可能在左子树

3. 二者相等代表查找到target

设计思路：

因为查找只需要判断是否存在即可，所以返回值类型设计为bool类型，从根节点开始向下遍历树，如果根节点不为空，判断当前节点的值与target的大小，如果target > root->_key，则走向右子树，否则走左子树

// 树查找bool findNode(const T& target){node* cur = _root;while (cur){if (target == cur->_key){// 如果找到返回truereturn true;}else if (target > cur->_key){// 目标值大走右子树cur = cur->_right;}else{// 目标值小走左子树cur = cur->_left;}}​//循环走完时证明没找到，返回falsereturn false;}

二叉搜索树的插入

有了二叉搜索树的查找后，在插入前需要调用查找函数判断插入的数值不是树中已经存在的数值。如果不存在插入的数值，则可以正常插入。

插入的步骤如下：

1. 判断节点值是否存在树中，存在则返回false，否则接着插入操作

2. 通过new创建一个节点，传入需要的key值进行初始化

3. 判断根节点是否为空，根节点为空则新节点作为根节点，否则接着插入操作

4. 插入节点时，如果插入的key > root->_key，则走左子树，否则走右子树，直到走到叶子结点，在遍历的过程中，需要一个变量parent记录父亲节点，否则无法插入新的节点

5. 当循环走完后，parent记录的就是需要的父亲节点，但是需要判断插入位置，如果插入的key比parent节点的值小，则插入在parent的左子树，否则插入在其右子树

6. 插入完成后返回true

// 树插入bool insertNode(const T& key){// 判断key是否已经存在if (findNode(key)){// 已经存在时插入失败return false;}// 创建node节点node* newNode = new node(key);// 判断根节点是否为空，为空则作为第一个节点if (_root == nullptr){_root = newNode;return true;}// 根节点不为空时接着遍历插入node* cur = _root;// 定义父亲节点记录父亲的位置node* parent = _root;while (cur){if (key > cur->_key){// 大于根节点数据，插入在右子树，走到左子树的空位置parent = cur;cur = cur->_right;}else if (key < cur->_key){// 小于根节点数据，插入在左子树，走到右子树的空位置parent = cur;cur = cur->_left;}}​// 循环走完后当前cur为空，parent为叶子节点，链接新节点if (parent->_key < key){// 如果是右子树，则插入在右子树parent->_right = newNode;}else{// 否则插入在左子树parent->_left = newNode;}​return true;}

插入过程如下：

二叉搜索树的中序遍历

二叉搜索树的遍历等同于二叉树的遍历，但是需要注意：如果中序遍历函数有形参root，则在类外无法传入创建的对象树中的_root，所以为了处理这个问题可以使用子函数，子函数放在类内，可以访问当前类成员_root

首先设计子函数为中序遍历执行函数，设计思路参考二叉树基础中的二叉树中序遍历

 // 中序遍历——子函数void _inOrder(const node* root){// 如果节点为空返回if (root == nullptr){return;}​// 中序遍历_inOrder(root->_left);cout << root->_key << " " ;_inOrder(root->_right);}

接着设计主调函数，设计主调函数则不需要设计形参，只需要传入一个类成员_root给子函数即可，此时的_root为this->_root，this指针中为调用对象的地址

 // 中序遍历——主函数void inOrder(){// 调用子函数_inOrder(_root);cout << endl;}

二叉搜索树的删除

二叉搜索树的节点删除有三种情况：

1. 节点为叶子结点，直接删除，例如图中的1,4,7,13：

2. 节点有一个孩子节点，删除节点时需要先找到该节点的父亲节点，由该父亲节点链接其孩子节点，例如图中的14节点

3. 节点有两个孩子节点，因为删除该节点后仍需要满足左子树的节点值比根节点的值小，右子树的节点值比根节点的值大，所以考虑在删除节点的左孩子节点的最右孩子节点或者删除节点的右孩子节点的最左孩子节点中选一个节点，将其值覆盖需要删除的父亲节点的值，再删除选择的孩子节点，例如删除图中的3节点

因为初始化时，将新创建的节点的左右指针置为空，所以如果删除叶子结点，也可以相当于用其父亲节点链接到空节点nullptr，所以对于第一种情况可以归类到第二种情况，总共两种情况需要考虑

删除步骤：（复习时请画图理解）

1. 判断根节点是否为空，如果根节点为空不执行删除，否则继续执行删除

2. 查找待删除节点是否存在，如果删除节点存在不存在不执行删除，否则继续执行删除

3. 查找节点的位置，如果找到了节点就开始删除：

   1. 考虑第一种情况（没有孩子节点和只有一个孩子节点），根据前面的分析，只需要将待删除节点的父亲节点链接其孩子节点即可。首先确定待删除的节点是左孩子为空还是右孩子为空，以左孩子为空为例，如果待删除节点的左孩子为空，则链接时，需要将待删除节点的父亲节点链接到待删除节点的右孩子，链接完成后删除节点，跳出循环即可

   2. 考虑第二种情况（有两个孩子节点），首先从错误的角度分析，批判一下为什么是错误的。对于两个孩子节点的情况来说，根据前面的分析，可以找一个节点覆盖待删除的节点的值，再删除该替换节点。所以可以分为两种情况：1. 存在待删除节点的左子树的最右侧值（左子树的最大值）2. 存在待删除节点的右子树的最左侧值（右子树的最小值）。既然有两种情况，那么两种情况均需要进行考虑吗？实际上，只需要考虑一种情况，例如选择待删除节点的右子树的最左节点，在二叉搜索树中，这个右子树最左节点一定存在，具体原因画图分析。接着设计思路：因为在遍历过程中需要找到最左节点，所以用replaceNode来代表，因为最后删除的代替节点可能还存在孩子节点，所以依旧需要使用到第一种情况的思路，此时需要一个replaceNodeP记录替代节点的父亲节点的位置，找到replaceNode节点后将其值覆盖给删除的节点即可（也可以使用交换，但是没有必要），再进行第一种情况的步骤，最后删除替代节点即可

   3. 考虑完上述两种情况后，还有一种情况，如果只有一个根节点时，只考虑上面两种情况会导致程序崩溃，只有一个根节点时，此时根节点的左右子树均为空，属于第一种情况，删除之前需要让根指向其左孩子或者右孩子

void eraseNode(const T& key){// 如果根节点为空，则不执行删除if (_root == nullptr){return;}​// 查找节点，如果节点不存在不执行删除if (findNode(key) == false){return;}​node* parent = _root;node* cur = _root;while (cur){if (key > cur->_key){// 大走右子树parent = cur;cur = cur->_right;}else if (key < cur->_key){// 小走左子树parent = cur;cur = cur->_left;}else{// 找到，删除if (cur->_right == nullptr){// 考虑根节点的情况if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else if (parent->_left == cur){parent->_left = cur->_left;}}delete cur;break;}else if (cur->_left == nullptr){// 考虑根节点的情况if (cur == _root){_root = cur->_right;}else{// 找到孩子的位置后链接if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}}delete cur;break;}else{// 两个孩子节点// 找出适合的替代节点，选择右子树的最左孩子node* replaceNodeP = cur;node* replaceNode = cur->_right;​// 一直向左子树走直到找到替代节点while (replaceNode->_left){replaceNodeP = replaceNode;replaceNode = replaceNode->_left;}​// 将replaceNode的值覆盖需要删除的节点cur->_key = replaceNode->_key;// 将replaceNode的父亲指向替换节点的孩子if (replaceNodeP->_left == replaceNode){// 找的右子树的最左节点，一定没有左孩子replaceNodeP->_left = replaceNode->_right;}else{// replaceNodeP与待删除节点时同一个节点replaceNodeP->_right = replaceNode->_right;}delete replaceNode;break;}}}}

二叉搜索树应用

1. K模型：在K模型中，只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索的值

2. KV模型：每一个关键码key都有对应的值value，称为<Key, Value>的键值对

对于前面实现的二叉搜索树来说，即为K模型，对前面的结构添加value值，构成<Key, Value>键值对模型

• 修改单个节点结构

// 定义树每一个节点结构template<class T, class V>struct binarySearchTreeNode{// key值T _key;// value值V _value;// 左子树指针binarySearchTreeNode<T, V>* _left;// 右子树指针binarySearchTreeNode<T, V>* _right;​//单个节点构造函数binarySearchTreeNode(const T& key, const V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}};

• 修改查找函数返回值

// 树查找node* findNode(const T& target){node* cur = _root;while (cur){if (target == cur->_key){// 如果找到返回节点return cur;}else if (target > cur->_key){// 目标值大走右子树cur = cur->_right;}else{// 目标值小走左子树cur = cur->_left;}}​//循环走完时证明没找到，返回空指针return nullptr;}

• 修改插入函数

// 树插入bool insertNode(const T& key, const V& value){// 判断key是否已经存在if (findNode(key)){// 已经存在时插入失败return false;}// 创建node节点node* newNode = new node(key, value);// 判断根节点是否为空，为空则作为第一个节点if (_root == nullptr){_root = newNode;return true;}// 根节点不为空时接着遍历插入node* cur = _root;// 定义父亲节点记录父亲的位置node* parent = _root;while (cur){if (key > cur->_key){// 大于根节点数据，插入在右子树，走到左子树的空位置parent = cur;cur = cur->_right;}else if (key < cur->_key){// 小于根节点数据，插入在左子树，走到右子树的空位置parent = cur;cur = cur->_left;}}​// 循环走完后当前cur为空，parent为叶子节点，链接新节点if (parent->_key < key){// 如果是右子树，则插入在右子树parent->_right = newNode;}else{// 否则插入在左子树parent->_left = newNode;}​return true;}

修改三处即可让原有的K模型变为KV模型

下面是常见的KV模型实际使用

void Test_dict(){// 单词字典Key_Value::binarySearchTree<string, string> dict;dict.insertNode("string", "字符串");dict.insertNode("tree", "树");dict.insertNode("left", "左边、剩余");dict.insertNode("right", "右边");dict.insertNode("sort", "排序");// 读取输入判断是否存在于字典中string str;while (cin >> str){Key_Value::binarySearchTreeNode<string, string>* ret = dict.findNode(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "无此单词" << endl;}}}

void Test_fruits_count(){// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };Key_Value::binarySearchTree<string, int> fruitsCount;Key_Value::binarySearchTreeNode<string, int>* countNode;for (auto& str : arr){countNode = fruitsCount.findNode(str);if (countNode == nullptr){// 没出现过直接插入fruitsCount.insertNode(str, 1);}else{// 出现过改变出现次数countNode->_value++;}}​// 遍历fruitsCount.inOrder();}

二叉搜索树的效率

在上面的二叉搜索树中，一般情况下，时间复杂度为，但是最坏情况下会退化到（单支树）