文章目录

• 为什么要学这一节
• 1. 二叉搜索树
• • 1.1 二叉搜索树概念
  • 1.2 二叉搜索树操作
  • 1.3 二叉搜索树的实现
  • 1.4 二叉搜索树的应用
  • 1.5 二叉搜索树的性能分析
• 2. 经典题目
• • 2.1 最近公共祖先
  • 2.2 从前序与中序遍历序列构造二叉树
  • 2.3 二叉树的前序遍历（非递归）

为什么要学这一节

二叉树在前面C数据结构阶段已经讲过，本节取名二叉树进阶是因为：

1. map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构
2. 二叉搜索树的特性了解，有助于更好的理解map和set的特性
3. 二叉树中部分面试题稍微有点难度，在前面讲解大家不容易接受，且时间长容易忘
4. 有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻烦。

因此本节借二叉树搜索树，对二叉树部分进行收尾总结。

1. 二叉搜索树

1.1 二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

1.2 二叉搜索树操作

1. 二叉搜索树的查找
   a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
   b、最多查找高度次，走到到空，还没找到，这个值不存在。
2. 二叉搜索树的插入
   插入的具体过程如下：
   a. 树为空，则直接新增节点，赋值给root指针
   b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

3. 二叉搜索树的删除

• 首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
  a. 要删除的结点无孩子结点
  b. 要删除的结点只有左孩子结点
  c. 要删除的结点只有右孩子结点
  d. 要删除的结点有左、右孩子结点
• 看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
  情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
  情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
  情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

1.3 二叉搜索树的实现

#pragma once
#include 
#include 
using namespace std;
namespace key
{templatestruct BSTreeNode{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K& key): _left(nullptr), _right(nullptr), _key(key){}};templateclass BSTree{typedef BSTreeNode Node;private:void destoryTree(Node* root){if (root == nullptr)return;destoryTree(root->_right);destoryTree(root->_left);delete root;}Node* CopyTree(const Node* root)// 前序遍历递归{if (root = nullptr)return nullptr;Node* copyNode = new Node(root->_key);copyNode->_left = CopyTree(root->_left);copyNode->_right = CopyTree(root->_right);return copyNode;}public://自己写了拷贝构造函数，编译器就不会默认生成构造函数//default用于强制编译器自己生成构造(C++11)BSTree() = default;BSTree(const BSTree& t){_root = CopyTree(t._root);}~BSTree(){destoryTree(_root);_root = nullptr;}BSTree& operator=(BSTree t){swap(_root, t._root);return *this;}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;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{return false;}}cur = new Node(key);if (key > parent->_key){parent->_right = cur;}else if (key < parent->_key){parent->_left = cur;}return true;}bool 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 true;}}return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{// 一个孩子、没有孩子：托孤// 两个孩子：替代法if (cur->_left == nullptr){// 删根节点// if (parent == nullptr)if (cur == _root){_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}//两个孩子：替代法。用左子树的最右节点 或 右树的最左节点else{//用右树的最左节点替代Node* minParent = cur;// 存父亲，不能给nullptr，因为右子树的根可能就是minRightNode* minRight = cur->_right;// 存while (minRight->_left)// 找右树的最左{minParent = minRight;minRight = minRight->_left;}swap(cur->_key, minRight->_key);// 开始托孤// return erase(key);交换后不符合二叉搜索树了。找不到key了。if (minRight = minParent->_left){minParent->_left = minRight->_right;}else{minParent->_right = minRight->_right;}delete minRight;}return true;}}return false;// cur为空，找不到要删的}void InOrder()// 在类外传递root很麻烦，所以再套一层{_InOrder(_root);cout << endl;}// 递归bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key)//Node*& root是为了直接链接新节点。root的值是空，但root同时是父节点的left指针的别名{if (root == nullptr)return false;if (key > root->_key)return _EraseR(root->_right, key);else if (key < root->_key)return _EraseR(root->_left, key);else{Node* del = root;if (root->_left == nullptr){root = root->_right;// root是父节点孩子的别名。return true;}else if (root->_right == nullptr){root = root->_left;return true;}else{Node* minRight = root->_right;while (minRight->_left){minRight = minRight->_left;}swap(minRight->_key, root->_key);return _EraseR(root->_right, key);// 递归删除，删除左为空的节点}}}bool _InsertR(Node*& root, const K& key)//Node*& root是为了直接链接新节点。root的值是空，但root同时是父节点的left指针的别名{if (root == nullptr){root = new Node(key);return true;}if (key > root->_key)return _InsertR(root->_right, key);else if (key < root->_key)return _InsertR(root->_left, key);elsereturn false;}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (key < root->_key)_FindR(root->_left, key);else if (key > root->_key)_FindR(root->_right, key);elsereturn true;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;};void test1(){BSTree t;int a[] = { 14,1,76,42,13,5 };for (auto e : a){t.InsertR(e);}t.InOrder();for (auto e : a){t.EraseR(e);}t.InOrder();}
}

1.4 二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
   比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

   • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树。
   • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：

   • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
   • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对

namespace key_value
{templatestruct BSTreeNode{BSTreeNode* _left;BSTreeNode* _right;const K _key;V _value;BSTreeNode(const K& key, const V& value): _left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass BSTree{typedef BSTreeNode Node;public:void InOrder()// 在类外传递root很麻烦，所以再套一层{_InOrder(_root);cout << endl;}// 递归Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}bool EraseR(const K& key){return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key)//Node*& root是为了直接链接新节点。root的值是空，但root同时是父节点的left指针的别名{if (root == nullptr)return false;if (key > root->_key)return _EraseR(root->_right, key);else if (key < root->_key)return _EraseR(root->_left, key);else{Node* del = root;if (root->_left == nullptr){root = root->_right;// root是父节点孩子的别名。return true;}else if (root->_right == nullptr){root = root->_left;return true;}else{Node* minRight = root->_right;while (minRight->_left){minRight = minRight->_left;}swap(minRight->_key, root->_key);return _EraseR(root->_right, key);// 递归删除，删除左为空的节点}}}bool _InsertR(Node*& root, const K& key, const V& value)//Node*& root是为了直接链接新节点。root的值是空，但root同时是父节点的left指针的别名{if (root == nullptr){root = new Node(key, value);return true;}if (key > root->_key)return _InsertR(root->_right, key, value);else if (key < root->_key)return _InsertR(root->_left, key, value);elsereturn false;}Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (key < root->_key)_FindR(root->_left, key);else if (key > root->_key)_FindR(root->_right, key);elsereturn root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;};void Test1(){BSTree ECDict;ECDict.InsertR("root", "根");ECDict.InsertR("string", "字符串");ECDict.InsertR("left", "左边");ECDict.InsertR("insert", "插入");//...string str;while (cin >> str)  //while (scanf() != EOF){//BSTreeNode* ret = ECDict.FindR(str);auto ret = ECDict.FindR(str);if (ret != nullptr){cout << "对应的中文:" << ret->_value << endl;//ret->_key = "";ret->_value = "";}else{cout << "无此单词，请重新输入" << endl;}}}
}

1.5 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

• 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2Nlog_2 Nlog2​N
• 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N2\frac{N}{2}2N​

问题：如果退化成单支树，二叉搜索树的性能就失去了。

那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了

2. 经典题目

2.1 最近公共祖先

二叉树的最近公共祖先

class Solution {
public:bool isInSubTree(TreeNode* tree, TreeNode* x){if(tree == nullptr)return false;if(tree == x)return true;return isInSubTree(tree->left, x)|| isInSubTree(tree->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr)return nullptr;if(root == p || root == q)return root;bool pInLeft = isInSubTree(root->left, p);bool pInRight = !pInLeft;bool qInLeft = isInSubTree(root->left, q);bool qInRight = !qInLeft;if(pInLeft && qInLeft){return lowestCommonAncestor(root->left, p, q);}else if(pInRight && qInRight){return lowestCommonAncestor(root->right, p, q);}else{return root;}}
};

要一个个找，效率无法保证。把题目转化为相交链表求交点，把它的路径求出来，在找交点，交点即为最近公共祖先。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool Route(TreeNode* root, TreeNode* x, stack& path){if(root == nullptr)return false;path.push(root);if(root == x)return true;else if(Route(root->left, x, path))return true;else if(Route(root->right, x, path))return true;else{path.pop();return false;}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack pPath, qPath;Route(root, p, pPath);Route(root, q, qPath);//将这题转化为相交链表求交点，先让它们长度相同while(pPath.size() > qPath.size())pPath.pop();while(pPath.size() < qPath.size())qPath.pop();//再同时走，求交点while(pPath.top()!= qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};

2.2 从前序与中序遍历序列构造二叉树

从前序与中序遍历序列构造二叉树

/*** 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& preorder, vector& inorder, int& prei, int inBegin, int inEnd){if(inBegin>inEnd)return nullptr;TreeNode* root = new TreeNode(preorder[prei]);prei++;int rooti = inBegin;while(rooti<=inEnd){if(inorder[rooti] == root->val)break;elserooti++;}root->left = _buildTree(preorder, inorder, prei, inBegin, rooti-1);root->right = _buildTree(preorder, inorder, prei, rooti+1, inEnd);return root;}TreeNode* buildTree(vector& preorder, vector& inorder) {int prei = 0, inBegin = 0, inEnd = preorder.size()-1;TreeNode* root = _buildTree(preorder, inorder, prei, inBegin, inEnd);return root;}
};

2.3 二叉树的前序遍历（非递归）

非递归前序遍历

/*** 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:vector preorderTraversal(TreeNode* root) {vector v;stack st;TreeNode* cur = root;while(cur || !st.empty()){//遍历左路节点，左路节点入栈——访问一棵树的开始while(cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}//依次取左路节点的右子树访问TreeNode* top = st.top();st.pop();//访问左路节点的右子树--子问题cur = top->right;}return v;}
};