网站建设7个基,wordpress建站主题,知名网站制作案例,济南定制网页设计前言 在c语言阶段的数据结构系列中已经学习过二叉树#xff0c;但是这篇文章是二叉树的进阶版#xff0c;因为首先就会讲到一种树形结构“二叉搜索树”#xff0c;学习二叉搜索树的目标是为了更好的理解map和set的特性。二叉搜索树的特性就是左子树键值小于根#xff0c;右…前言 在c语言阶段的数据结构系列中已经学习过二叉树但是这篇文章是二叉树的进阶版因为首先就会讲到一种树形结构“二叉搜索树”学习二叉搜索树的目标是为了更好的理解map和set的特性。二叉搜索树的特性就是左子树键值小于根右子树键值大于根所以二叉搜索树就天然的具有查找功能有时二叉搜索树又叫二叉排序树或者二叉查找树。
目录
前言
Ⅰ、二叉搜索树概念
Ⅱ、二叉搜索树操作
Ⅲ、二叉搜索树的实现
Ⅳ、 二叉搜索树的应用
Ⅴ、二叉搜索树的性能分析
Ⅵ、二叉树进阶面试题 Ⅰ、二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: ●若它的左子树不为空则左子树上所有节点的值都小于根节点的值 ●若它的右子树不为空则右子树上所有节点的值都大于根节点的值 ●它的左右子树也分别为二叉搜索树 ●它没有重复的键值 Ⅱ、二叉搜索树操作 int a[ ] {8, 3, 1, 10, 6, 4, 7, 14, 13}; 1. 二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 2. 二叉搜索树的插入
插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 1. 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下 ●情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除 ●情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除 ●情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题--替换法删除
如图理解情况a实质就是删除1,4,7,13可以直接删除。 关于情况b情况c就需要详细探讨 对于情况d是最难以理解的这种情况就好比删除3和8他们是需要替换法删除的场景这种情况就需要找子树右边的最小值(minright)找到之后minright的key值与cur的key交换(赋值)后再判断后进行链接。 但是通下面代码我们发现这段代码删除8时就会发现root为nullptr这样就出现错误了还有一个问题就是minright可以是parent左右子树所以关于删除的时候还需要判断是否parent的左右子树 Ⅲ、二叉搜索树的实现
二叉搜索树代码的实现查找插入是比较容易理解的对于删除考虑的情况比较多。主要分三种情况1.直接删除2.左右子树为nullptr交换删除3.左右子树都不为nullptr需要找minright替换key值后链接。
对于整个结构与我之前学习的二叉树基本一样只是用到了c封装了节点该节点中有左右节点和key值通过模板实现不同参数的调用。
非递递归代码实现如下
#pragma once
#include iostream
#include string
using namespace std;namespace K
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);_rootnullptr;}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-_right cur;}else{parent-_left 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{// 1、左为空// 2、右为空// 3、左右都不为空替换删除if (cur-_left nullptr){//if (parent nullptr)if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//if (parent nullptr)if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 右子树的最小节点Node* parent cur;Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}cur-_key minRight-_key;if (minRight parent-_left){parent-_left minRight-_right;}else{parent-_right minRight-_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}private:void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}Node* Copy(Node *root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key)cur cur-_right;else if (cur-_key key)cur cur-_left;elsereturn true;}return false;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;};
}
递归
这里递归主要讲解删除Erase相信大家之前对递归也是有所涉猎的。对于Erase的实现开始也是通过递归查找key节点还需要循环找到minright然后通过(swap)交换key值和minright值之后再通过递归cur的子树删除。下面我们就来深入分析递归删除列如删除如图3。 ●1.先通过递归查找到删除节点 ●2.如果是左右子树为nullptr直接链接到根root ●3.这里如果删除的是3就是通过上面步骤找到3为cur然后判断出cur的左右子树都不为nullptr这时就需要寻找minright找到minright之后swap交换3,4然后递归删除4节点的右子树的3。 最后需要注意的一点是递归就会调用_root所以我们可以在类中先封装再调用。
非递归代码实现如下
namespace K
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);_rootnullptr;}void InOrder(){_InOrder(_root);cout endl;}bool InsertR(const K key){return _InsertR(_root,key);}bool FindR(const K key){return _FindR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}private:void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}Node* Copy(Node *root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}bool _EraseR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}swap(root-_key, minRight-_key);// 转换后在子树中去删除节点return _EraseR(root-_right, key);}delete del;return true;}}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key)return _InsertR(root-_right, key);else if (root-_key key)return _InsertR(root-_left, key);elsereturn false;}bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right);}else if (root-_key key){return _FindR(root-_left);}else{return true;}}
private:Node* _root nullptr;};
}Ⅳ、 二叉搜索树的应用
1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 ○以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 ○在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2. KV模型每一个关键码key都有与之对应的值Value即的键值对。该种方式在现实生活中非常常见 ○比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文就构成一种键值对 ○再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是就构成一种键值对。
改造二叉搜索树为KV结构如下
namespace KV
{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:bool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);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, value);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return nullptr;}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_key : root-_value endl;_Inorder(root-_right);}private:Node* _root nullptr;};
}
测试1通过英文查找中文这个时候就用到KV搜索树我们可以给树的key和value定义都为string类型然后将信息插入到KV搜索树。最后通过查找key值如果有就打印value即可。
void TestBSTree2()
{//词库中单词都放进这个搜索树中//key的搜索模型判断在不在//场景检查单词拼写是否正确/车库出入系统/...//K::BSTreestring dict;//Key/Value的搜索模型通过Key查或者修改ValueKV::BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(string, 字符串);dict.Insert(left, 左边);dict.Insert(right, 右边);string str;while(cin str){KV::BSTreeNodestring, string* ret dict.Find(str); if (ret){cout ret-_value endl;}else{cout 没有这个单词 endl;}}}
编译结果sort 排序 left 左边 right 右边 hello 没有这个单词测试2统计水果出现的次数
void TestBSTree3()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };KV::BSTreestring, int countTree;for (auto e : arr){auto* ret countTree.Find(e);if (ret nullptr){countTree.Insert(e, 1);}else{ret-_value;}}countTree.Inorder();
}
Ⅴ、二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为$log_2 N$
最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为$\frac{N}{2}$
问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插 入关键码二叉搜索树的性能都能达到最优那么我们后续章节学习的AVL树和红黑树就可以上场了。
Ⅵ、二叉树进阶面试题
这些题目更适合使用C完成难度也更大一些 1. 二叉树创建字符串。OJ链接 2. 二叉树的分层遍历1。OJ链接 3. 二叉树的分层遍历2。OJ链接 4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接 5. 二叉树搜索树转换成排序双向链表。OJ链接 6. 根据一棵树的前序遍历与中序遍历构造二叉树。 OJ链接 7. 根据一棵树的中序遍历与后序遍历构造二叉树。OJ链接 8. 二叉树的前序遍历非递归迭代实现 。OJ链接 9. 二叉树中序遍历 非递归迭代实现。OJ链接 10. 二叉树的后序遍历 非递归迭代实现。OJ链接
