【C++】二叉树进阶
目录
前言
一、二叉搜索树
2.1 二叉搜索树的概念
2.2 二叉搜索树的操作
2.3 二叉搜索树的实现
2.4 二叉搜索树的应用
2.5 二叉搜索树的性能分析
二、二叉树的经典OJ题
前言
二叉树在前面C数据结构已经讲过，本篇文章再讲是为了接下来的map和set：map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构，二叉搜索树的特性了解，有助于更好的理解map和set的特性，并且在这里讲解一些二叉树的OJ题目，容易让大家接受。
一、二叉搜索树
2.1 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
2.2 二叉搜索树的操作
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
1. 二叉搜索树的查找
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- 最多查找高度次，走到空还没找到，则这个值不存在。
2. 二叉搜索树的插入
- 树为空，则直接新增节点，赋值给root指针。
- 树不为空，则按照二叉搜索树性质查找插入位置，插入新节点。
3. 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回，如果存在，则要删除的节点分成下面四种情况：
- 要删除的节点无孩子节点。
- 要删除的节点只有左孩子节点。
- 要删除的节点只有右孩子节点。
- 要删除的节点有左，右孩子节点。
看起来有待删除的节点有4中情况，实际情况1可以与情况2或者3合并起来，因此真正的删除过程如下：
- 情况2：删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点---直接删除
- 情况3：删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点---直接删除
- 情况4：在它的右子树中寻找中序下的第一个节点（关键码最小），用它的值填补到被删除节点中，再来处理该节点的删除问题---替换法删除
2.3 二叉搜索树的实现
#pragma once
#include <iostream>
using namespace std;template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){ }
};template<class K>
class BSTree
{typedef BSTNode<K> Node;
public:bool find(const K& key){Node* node = _root;while (node){if (node->_key < key) node = node->_right;else if (node->_key > key) node = node->_left;else return true;}return false;}bool Insert(const K& key){// 该树为空，直接赋值给根节点if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) parent = cur, cur = cur->_right; // 比当前根的值大，往右走else if (cur->_key > key) parent = cur, cur = cur->_left; // 比当前根的值小，往左走else return false; // 当前的值存在，无法插入}// 找到了新增节点的双亲节点，与双亲节点比较大小后插入合适位置cur = new Node(key);if (parent->_key > key) parent->_left = cur;else parent->_right = cur;return true;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) parent = cur, cur = cur->_right; // 比当前根的值大，往右走else if (cur->_key > key) parent = cur, cur = cur->_left; // 比当前根的值小，往左走else {// 当前节点只有左孩子节点if (nullptr == cur->_right) {// 删除的是根节点if (nullptr == parent) {_root = _root->_left;}else {// 判断cur在parent的左边还是右边if (parent->_key > cur->_key) parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;return true;}// 当前节点只有右孩子节点else if (nullptr == cur->_left) {// 删除的是根节点if (nullptr == parent) {_root = _root->_right;}else {// 判断cur在parent的左边还是右边if (parent->_key > cur->_key) parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;return true;}// 当前节点左右孩子都存在，不能直接删除，用替换法删除else {// 找到当前节点右子树中的最小值的节点Node* rightmin = cur->_right;Node* rightminp = cur;while (rightmin->_left) rightminp = rightmin, rightmin = rightmin->_left;cur->_key = rightmin->_key;// 判断最小值节点是否是双亲节点的左孩子，然后删除该节点if (rightminp->_left == rightmin) rightminp->_left = rightmin->_right;else rightminp->_right = rightmin->_right;delete rightmin;return true;}}}// key不存在，无法删除return false;}// 中序遍历void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << ' ';_InOrder(root->_right);}
private:Node* _root = nullptr;
};测试代码：
#include "SearchBinaryTree.h"int main()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> tree;for (auto i : a) tree.Insert(i);tree.InOrder();for (auto i : a) tree.erase(i);return 0;
}
2.4 二叉搜索树的应用
1. K模型：K模型即只有可以作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
- 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
2. KV模型：每一个关键码key，都有与之对应的值value，即<key, value>的键值对。这种方式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与之对应的中文，英文单词与之对应的中文<word, chinese>的键值对
- 再比如统计单词次数，统计成功后，给定单词就可以快速找到其出现的次数，单词与其出现次数<word, count>构建的键值对。
template<class K, class V>
struct BSTNode
{K _key;V _val;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& val):_key(key),_val(val),_left(nullptr),_right(nullptr){ }
};// erase没有更改，就没有展示
template<class K, class V>
class BSTree
{typedef BSTNode<K, V> Node;
public:Node* find(const K& key){Node* node = _root;while (node){if (node->_key < key) node = node->_right;else if (node->_key > key) node = node->_left;else return node;}return nullptr;}bool Insert(const K& key, const V& val){// 该树为空，直接赋值给根节点if (_root == nullptr){_root = new Node(key, val);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) parent = cur, cur = cur->_right; // 比当前根的值大，往右走else if (cur->_key > key) parent = cur, cur = cur->_left; // 比当前根的值小，往左走else return false; // 当前的值存在，无法插入}// 找到了新增节点的双亲节点，与双亲节点比较大小后插入合适位置cur = new Node(key, val);if (parent->_key > key) parent->_left = cur;else parent->_right = cur;return true;}
private:Node* _root = nullptr;
};测试代码：
#include <string>
#include "SearchBinaryTree.h"int main()
{// 输入单词，查找单词对应的中文翻译BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("tree", "树");dict.Insert("left", "左边、剩余");dict.Insert("right", "右边");dict.Insert("sort", "排序");// 插入词库中所有单词string str;while (cin >> str){BSTNode<string, string>* ret = dict.find(str);if (ret == nullptr){cout << "单词拼写错误，词库中没有这个单词:" << str << endl;}else{cout << str << "中文翻译:" << ret->_val << endl;}}return 0;
}
2.5 二叉搜索树的性能分析
插入和删除的操作都必须先查找，查找效率代表了二叉搜索树各个操作的性能。
对有n个结点的二叉树，若每个节点的查找概率相等，则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN(以2为底)。
最坏情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N。
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续学习的AVL树和红黑树就可以上场了。
二、二叉树的经典OJ题
二叉搜索树与双向链表
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:void _Convert(TreeNode* root, TreeNode*& last){if(root == nullptr)return;// 中序遍历二叉搜索树所有节点// 对每个节点只让该节点连接上一个节点，上一个节点连接该节点// 该节点处理完，该节点变为下一个节点的上一个节点_Convert(root->left, last);last->right = root;root->left = last;last = root;_Convert(root->right, last);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;TreeNode* head = new TreeNode(0);TreeNode* ret = head;head->left = head;head->right = head;_Convert(pRootOfTree, head);ret->right->left = nullptr;return ret->right;}
};
从前序与中序遍历序列构造二叉树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend){if(inbegin >= inend)return nullptr;// 该区间的根节点为前序遍历中的该区间的第一个节点TreeNode* root = new TreeNode(preorder[prei]);int i;// 在中序遍历中找到该节点一样的值，该值左区间为当前根节点的左子树，该值右区间为当前根节点的右子树for(i = inbegin; i < inend; i++){if(preorder[prei] == inorder[i])break;}prei++;root->left = _buildTree(preorder, inorder, prei, inbegin, i);root->right = _buildTree(preorder, inorder, prei, i + 1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int prei = 0;return _buildTree(preorder, inorder, prei, 0, inorder.size());}
};根据二叉树创建字符串
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:string tree2str(TreeNode* root) {if(nullptr == root) return "";if(root->left == nullptr && root->right == nullptr) return to_string(root->val);if(root->right == nullptr) return to_string(root->val) + "(" + tree2str(root->left) + ")";return to_string(root->val) + "(" + tree2str(root->left) + ")" + "(" + tree2str(root->right) + ")";}
};