pc端购物网站建站,郑州高端网站建设怎么样,和网站开发公司如何签合同,手机网页版qq目录
一、内容说明
二、二叉搜索树
2.1 二叉搜索树概念
2.2 二叉搜索树操作
2.2.1 二叉搜索树的查找
2.2.2 二叉搜索树的插入
2.2.3 二叉搜索树的删除
2.3 二叉搜索树的实现
2.3.1 二叉搜索树的节点设置
2.3.2 二叉搜索树的查找函数
2.3.2.1 非递归实现
2.3.2.2 递…目录
一、内容说明
二、二叉搜索树
2.1 二叉搜索树概念
2.2 二叉搜索树操作
2.2.1 二叉搜索树的查找
2.2.2 二叉搜索树的插入
2.2.3 二叉搜索树的删除
2.3 二叉搜索树的实现
2.3.1 二叉搜索树的节点设置
2.3.2 二叉搜索树的查找函数
2.3.2.1 非递归实现
2.3.2.2 递归实现
2.3.3 二叉搜索树的插入函数
2.3.3.1 非递归实现
2.3.4 二叉搜索树的中序遍历
2.3.5 二叉搜索树的删除函数
2.3.5.1 非递归实现当我们需要删除一个节点时找到删除节点需要记录当前节点的父亲节点防止删除的当前节点时防止当前的节点的父亲节点中的指针变为野指针
2.3.6 二叉搜索树代码的整体实现
2.4 二叉搜索树的应用
2.5 二叉搜索树的性能分析
结尾 一、内容说明 二叉树在前面C数据结构阶段已经讲过非线性表之堆的实际应用和二叉树的遍历-CSDN博客 map和set特性需要先铺垫二叉搜索树而二叉搜索树也是一种树形结构二叉搜索树的特性了解有助于更好的理解map和set的特性二叉树中部分面试题稍微有点难度在前面讲解大家不容易接受且时间长容易忘有些OJ题使用C语言方式实现比较麻烦比如有些地方要返回动态开辟的二维数组非常麻烦。
此次二叉树是为后面map和set的实现做铺垫也是对二叉树进行收尾。 二、二叉搜索树
2.1 二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 2.2 二叉搜索树操作 2.2.1 二叉搜索树的查找
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。b、最多查找高度次走到到空还没找到这个值不存在。
2.2.2 二叉搜索树的插入
插入的具体过程如下
a. 树为空则直接新增节点赋值给root指针b. 树不空按二叉搜索树性质查找插入位置插入新节点 2.2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况
a. 要删除的结点无孩子结点b. 要删除的结点只有左孩子结点c. 要删除的结点只有右孩子结点d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除 2.3 二叉搜索树的实现
2.3.1 二叉搜索树的节点设置
templateclass K
struct BSTreeNode
{K _val;BSTreeNodeK* _left;BSTreeNodeK* _right;BSTreeNode(const K val):_val(val),_left(nullptr),_right(nullptr){}
}; 2.3.2 二叉搜索树的查找函数
从根节点开始查找若查找值比根节点小继续向左子树寻找若查找值比根节点大继续向右子树寻找。最多查找高度次若查找到空那么在这棵树中没有这个值返回false。
2.3.2.1 非递归实现
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:bool Find(const K key){Node* cur _root;while (cur){if (cur-_val key){cur cur-_left;}else if(cur-_val key){cur cur-_right;}else{return true;}}return false;}
private:// 成员变量Node* _root nullptr;
};2.3.2.2 递归实现
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:bool FindR(const K key)//使用递归查找{return _FindR(_root, key);}
private:bool _FindR(Node* _root,const K key){if (_root nullptr)return false;if (_root-_val key){return _FindR(_root-_left, key);}else if (_root-_val key){return _FindR(_root-_right, key);}else{return true;}}
private:Node* _root;
}; 2.3.3 二叉搜索树的插入函数
若树为空创建一个节点赋值给root。若树不为空按照二叉搜索树的性质查找插入位置插入新节点
2.3.3.1 非递归实现
//插入
bool Insert(const K key)
{Node* cur _root;Node* parent nullptr;if (_root nullptr){Node* newnode new Node(key);_root newnode;}else{while (cur){if (cur-_val key){parent cur;cur cur-_left;}else if (cur-_val key){parent cur;cur cur-_right;}else{return false;}}Node* newnode new Node(key);if (parent-_val key){parent-_left newnode;}else{parent-_right newnode;}}return true;
}
2.3.3.2 递归实现
bool InsertR(const K key)//使用递归插入
{return _InsertR(_root, key);
}bool _InsertR(Node* root, const K key)
{if (root nullptr){root new Node(key);return true;}if (root-_val key){return _InsertR(root-_right, key);}else if (root-_val key){return _InsertR(root-_left, key);}else{return false;}
} 2.3.4 二叉搜索树的中序遍历
二叉树的中序遍历是先递归遍历左子树再访问根节点最后递归遍历右子树。
void InOrder()
{_InOrder(_root);cout endl;
}void _InOrder(Node* cur)
{ //递归的形式遍历if (cur nullptr)return;_InOrder(cur-_left);cout cur-_val ;_InOrder(cur-_right);
} 2.3.5 二叉搜索树的删除函数
2.3.5.1 非递归实现 当我们需要删除一个节点时找到删除节点需要记录当前节点的父亲节点防止删除的当前节点时防止当前的节点的父亲节点中的指针变为野指针
bool Erase(const K key)
{Node* cur _root;Node* parent nullptr;while (cur){if (cur-_val key){parent cur;cur cur-_left;}else if (cur-_val key){parent cur;cur cur-_right;}else//找到了需要找的值{if (cur-_left nullptr)//左为空{if (parent nullptr)//删除结点为根结点{_root cur-_right;}else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}//右为空else if (cur-_right nullptr){if (parent nullptr)//删除结点为根结点{_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}//左右不为空else{Node* parent cur;Node* leftmax cur-_left;while (leftmax-_right){parent leftmax;leftmax leftmax-_right;}swap(cur-_val, leftmax-_val);if (parent-_left leftmax){parent-_left leftmax-_left;}else{parent-_right leftmax-_left;}cur leftmax;}delete cur;return true;}}return false;
}
2.3.6.2 递归实现 这里bool _EraseR(Node* root, const K key)中的作用也是通过改变当前节点直接改变父亲节点的指向。
bool EraseR(const K key)//使用递归删除
{return _EraseR(_root, key);
}
bool _EraseR(Node* root, const K key)
{if (root nullptr)return false;if (root-_val key){_EraseR(root-_left, key);}else if (root-_val key){_EraseR(root-_right, key);}else{Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Node* leftMax root-_left;while (leftMax-_right){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return _EraseR(root-_left, key);}delete del;return true;}
} 2.3.6 二叉搜索树代码的整体实现
namespace lxp
{templateclass Kstruct BSTreeNode{K _val;BSTreeNodeK* _left;BSTreeNodeK* _right;BSTreeNode(const K val):_val(val),_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);}//插入bool Insert(const K key){Node* cur _root;Node* parent nullptr;if (_root nullptr){Node* newnode new Node(key);_root newnode;}else{while (cur){if (cur-_val key){parent cur;cur cur-_left;}else if (cur-_val key){parent cur;cur cur-_right;}else{return false;}}Node* newnode new Node(key);if (parent-_val key){parent-_left newnode;}else{parent-_right newnode;}}return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_val key){cur cur-_left;}else if(cur-_val key){cur cur-_right;}else{return true;}}return false;}bool Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (cur-_val key){parent cur;cur cur-_left;}else if (cur-_val key){parent cur;cur cur-_right;}else//找到了需要找的值{if (cur-_left nullptr)//左为空{if (parent nullptr)//删除结点为根结点{_root cur-_right;}else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}//右为空else if (cur-_right nullptr){if (parent nullptr)//删除结点为根结点{_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}//左右不为空else{Node* parent cur;Node* leftmax cur-_left;while (leftmax-_right){parent leftmax;leftmax leftmax-_right;}swap(cur-_val, leftmax-_val);if (parent-_left leftmax){parent-_left leftmax-_left;}else{parent-_right leftmax-_left;}cur leftmax;}delete cur;return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* cur){ //递归的形式遍历if (cur nullptr)return;_InOrder(cur-_left);cout cur-_val ;_InOrder(cur-_right);}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:Node* Copy(Node* root){if (root nullptr)return nullptr;Node* copyroot new Node(root-_val);copyroot-_left Copy(root-_left);copyroot-_right Copy(root-_right);return copyroot;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_val key){_EraseR(root-_left, key);}else if (root-_val key){_EraseR(root-_right, key);}else{Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Node* leftMax root-_left;while (leftMax-_right){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return _EraseR(root-_left, key);}delete del;return true;}}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_val key){return _InsertR(root-_right, key);}else if (root-_val key){return _InsertR(root-_left, key);}else{return false;}}bool _FindR(Node* _root,const K key){if (_root nullptr)return false;if (_root-_val key){return _FindR(_root-_left, key);}else if (_root-_val key){return _FindR(_root-_right, key);}else{return true;}}private:Node* _root;};
} 2.4 二叉搜索树的应用
1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2. KV模型每一个关键码key都有与之对应的值Value即的键值对。该种方式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是就构成一种键值对。
templateclass K, class V
struct 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 V
class 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* cur _root;Node* prev nullptr;while (cur){prev cur;// 当当前节点的值大于要插入的值那么向左找if (cur-_key key){cur cur-_left;}// 当当前节点的值小于要插入的值那么向右找else if (cur-_key key){cur cur-_right;}// 二叉搜索树不允许相同的值存在当这个值已经存在过了那么返回false即插入失败else{return false;}}if (prev-_key key){prev-_left new Node(key, value);return true;}else{prev-_right new Node(key, value);return true;}return false;} Node* 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 cur;}}// 找不到return nullptr;}// 删除非递归版本bool Erase(const K key){Node* cur _root;Node* prev nullptr;// 找到需要删除的节点while (cur){if (cur-_key key){prev cur;cur cur-_left;}else if (cur-_key key){prev cur;cur cur-_right;}else{break;}}// 当当前根节点的左树为空时那么链接右边if (cur-_left nullptr){if (cur _root){_root cur-_left;delete cur;return true;}else{if (prev-_left cur)prev-_left cur-_right;elseprev-_right cur-_right;delete cur;cur nullptr;return true;}}// 当当前根节点的右树为空时那么链接左边else if (cur-_right nullptr){if (cur _root){_root cur-_left;delete cur;return true;}else{if (prev-_left cur)prev-_left cur-_left;elseprev-_right cur-_left;delete cur;cur nullptr;return true;}}else{prev cur;Node* del cur-_right;while (del-_left ! nullptr){prev del;del del-_left;}swap(del-_key, cur-_key);if (prev-_left del)prev-_left del-_right;elseprev-_right del-_right;delete del;del nullptr;return true;}return false;}void InOrder(){_InOrder(_root);cout endl;}~BSTree(){Destory(_root);}BSTree() {}BSTree(const BSTreeK, V T){_root Copy(T._root);}BSTreeK, V operator(BSTreeK, V T){swap(_root, T._root);return *this;}private:Node* Copy(Node* Troot){if (Troot nullptr)return nullptr;Node* root new Node(Troot-_key);root-_left Copy(Troot-_left);root-_right Copy(Troot-_right);return root;}void Destory(Node* root){if (root nullptr)return;Destory(root-_left);Destory(root-_right);delete root;root nullptr;}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key)return _InsertR(root-_left, key);else if (root-_key key)return _InsertR(root-_right, key);// 出现相同的数字返回falseelsereturn false;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}Node* _root nullptr;
};void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(left, 左边);dict.Insert(string, 字符串);dict.InOrder();string str;while (cin str){auto ret dict.Find(str);if (ret){cout str : ret-_value endl;}else{cout 单词拼写错误 endl;}}string strs[] { 苹果, 西瓜, 苹果, 樱桃, 苹果, 樱桃, 苹果, 樱桃, 苹果 };// 统计水果出现的次BSTreestring, int countTree;for (auto str : strs){auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();
}2.5 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为logN(log以2为底N的对数)
最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N
问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插 入关键码二叉搜索树的性能都能达到最优那么我们后续章节学习的AVL树和红黑树就可以上场了。 结尾
如果有什么建议和疑问或是有什么错误希望大家可以在评论区提一下。 希望大家以后也能和我一起进步 如果这篇文章对你有用的话请大家给一个三连支持一下
谢谢大家收看
