网站开发及设计,网站建设的风格,网站建设最便宜,什么是网站程序这是关于一个普通双非本科大一学生的C的学习记录贴
在此前#xff0c;我学了一点点C语言还有简单的数据结构#xff0c;如果有小伙伴想和我一起学习的#xff0c;可以私信我交流分享学习资料
那么开启正题
今天分享的是关于二叉搜索树的知识点
1.二叉搜索树概念
二叉搜…这是关于一个普通双非本科大一学生的C的学习记录贴
在此前我学了一点点C语言还有简单的数据结构如果有小伙伴想和我一起学习的可以私信我交流分享学习资料
那么开启正题
今天分享的是关于二叉搜索树的知识点
1.二叉搜索树概念
二叉搜索树又叫做二叉排序树有以下性质或为空树
1.左子树结点所有结点的值都小于根节点的值
2.右子树结点所有结点的值都大于根节点的值
3.它的左右子树也都是二叉搜索树
2.二叉搜索树操作
1.查找
a.从根开始比较查找如果比跟大往右走比跟小则往左走
b.最多查找高度次走到为空还没找到则这个值不存在
2.插入
a.树为空直接新增结点赋值给给_root
b.树不为空类似查找根据性质找到插入位置插入新结点
3.删除
首先查找元素是否在二叉搜索树中如果不存在返回false存在分为以下几种情况
a.要删除的结点没有左结点
b.要删除的结点没有右结点
c.要删除的结点有左右孩子结点
d.要删除的结点无孩子结点
其中d可以按照a或者b办法解决
情况a删除该结点且使删除结点的父亲结点指向删除结点的孩子结点——直接删除
情况b类似于a
情况c在右子树中找到最小结点或者在左子树中找到最大节点用他的值填补到被删除的结点上再删除此结点——替换法删除
3.二叉搜索树模拟实现
下面给出了模拟实现代码以及测试代码
namespace wkl
{templateclass Kstruct BSTreeNode{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;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;elseparent-_left cur;return true;}void _InOrder(Node* root){if (!root)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}void InOrder(){_InOrder(_root);cout endl;}bool Find(const K key){Node* cur _root;while (cur){if (key cur-_key)cur cur-_right;else if (key cur-_key)cur cur-_left;elsereturn true;}return false;}bool Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (key cur-_key){parent cur;cur cur-_right;}else if (key cur-_key){parent cur;cur cur-_left;}else{//开始删除//1.左为空//2.右为空//3.左右均不为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}else{Node* rightMinParent cur;Node* rightMin cur-_right; //右子树最小值最左while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;//改为删除rightMinif (rightMinParent-_left rightMin)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}private:Node* _root nullptr;};void BSTree_Test1(){BSTreeint BST;int a[] { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){BST.Insert(e);}BST.InOrder();int i 0;for (i 0; i 20; i 2){cout i ::;if (BST.Find(i))cout Yes;elsecout No;cout endl;}}void BSTree_Test2(){BSTreeint BST;int a[] { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){BST.Insert(e);}BST.InOrder();/*BST.Erase(7);BST.InOrder();*/for (auto e : a){BST.Erase(e);BST.InOrder();}}
}
4.二叉搜索树的应用
1.K值模型
K值模型只有key作为关键码结构中只存储key关键码即为需要搜索到的值
2.KV模型
每一个关键码都有与之对应的多个Value即KeyValue的键值对
5.二叉搜索树的性能分析
插入和删除都必须先查找查找效率代表了二叉搜索树的各个操作的性能
最好情况下二叉树平衡查找时间复杂度为O(lgN)
最坏情况下二叉树插入数据接近有序树长而不平衡查找时间复杂度为O(N) 新手写博客有不对的位置希望大佬们能够指出也谢谢大家能看到这里让我们一起学习进步吧
