做瑞士网站,可以为自己的小说建设网站,学生个人网页优秀模板,杭州公司注册虚拟地址一、二叉搜索树基本概念
1、定义
二叉搜索树#xff0c;又称为二叉排序树#xff0c;二叉查找树#xff0c;它满足如下四点性质#xff1a;
1#xff09;空树是二叉搜索树#xff1b; 2#xff09;若它的左子树不为空#xff0c;则左子树上所有结点的值均小于它根结…一、二叉搜索树基本概念
1、定义
二叉搜索树又称为二叉排序树二叉查找树它满足如下四点性质
1空树是二叉搜索树 2若它的左子树不为空则左子树上所有结点的值均小于它根结点的值 3若它的右子树不为空则右子树上所有结点的值均大于它根结点的值 4它的左右子树均为二叉搜索树 如上图所示二叉搜索树的任何一棵子树它的根结点的值一定大于左子树所有结点的值且一定小于右子树所有结点的值。如果对二叉搜索树进行中序遍历我们可以发现得到的序列是一个递增序列上述的遍历结果为[1,2,3,4,5,6,7,8]。
如果要查找4只需要从根结点比较查找3次就能找到可以显著提高搜索的速度。 二、二叉搜索树基础操作
1、查找算法
1查找原理
在二叉搜索树中查找某个数是否存在存在返回 true不存在返回 false。
对于要查找的数 val 从根结点出发总共四种情况依次判断
1若二叉搜索树为空树直接返回 false
2 val 的值 等于 树根结点的值则直接返回 true
3 val 的值 小于 树根结点的值说明 val 对应的结点不在根结点也不在右子树上需要在左子树上查找递归返回左子树的查找结果
4 val 的值 大于 树根结点的值说明 val 对应的结点不在根结点也不在左子树上需要在右子树上查找递归返回右子树的查找结果
2查找算法源码
① 结点源码
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};
② 查找算法源码 深度优先递归查找
bool BSTFind(TreeNode* root, int val)
{if (root nullptr) {return false;}if (root-val val) {return true;}if (val root-val) {return BSTFind(root-left, val);}else {return BSTFind(root-right, val);}
}
2、插入算法
1插入原理
将给定的值 val 生成结点后插入到树上的某个位置并且保持这棵树还是二叉搜索树。对于要插入的值 val 从根结点出发总共四种情况依次判断
1若为空树则创建一个值为 val 的结点并且返回根结点
2 val 的值 等于 树根结点的值无须执行插入直接返回根结点
3 val 的值 小于 树根结点的值那么插入位置一定在 左子树递归执行插入左子树的过程并且返回插入结果作为新的左子树
4 val 的值 大于 树根结点的值那么插入位置一定在 右子树递归执行插入右子树的过程并且返回插入结果作为新的右子树
2 插入源码
TreeNode* BSTInsert(TreeNode* root, int val) {if (root nullptr) {root new TreeNode(val);return root;}if (val root-val) {return root;}if (val root-val) {root-left BSTInsert(root-left, val);}else {root-right BSTInsert(root-right, val);}return root;
}
3、删除算法
1删除原理
删除值为 val 结点从根结点出发总共四种情况依次判断
1空树不存在结点直接返回空树
2 val 的值 小于 树根结点的值则需要删除的结点一定不在右子树上递归调用删除左子树的对应结点
3 val 的值 大于 树根结点的值则需要删除的结点一定不在左子树上递归调用删除右子树的对应结点
4 val 的值 等于 树根结点的值相当于是要删除根结点这时候又要分三种情况
当前树只有左子树则直接将左子树返回并且释放当前树根结点的空间当前树只有右子树则直接将右子树返回并且释放当前树根结点的空间当左右子树都存在时需要在右子树上找到一个值最小的结点替换新的树根而其它结点组成的树作为它的子树
2删除源码
由上述删除算法原理可知删除结点之前可能还需要找最小结点所以需要定义查找最小结点接口。
TreeNode* BSTFindMin(TreeNode* root) { while (root root-left) {root root-left; } return root;
}
查找根为 root 值最小的那个结点的值根据二叉搜索树的性质如果左子树存在则必然存在更小的值递归搜索左子树且最小值结点为叶子结点如果左子树不存在则根结点的值必然最小直接返回。 删除根结点并返回新根结点
//删除根结点并返回新根结点
TreeNode* Delete(TreeNode* root) {TreeNode* delNodenullptr, * retNodenullptr;if (!root) { //空树直接返回空return nullptr;}if (root-left nullptr) { //只有右子树(包含单结点)删除根空间后返回右子树根结点delNode root;retNode root-right;delete delNode;}else if (root-right nullptr) { //只有左子树删除根空间后返回左子树根结点delNode root;retNode root-left;delete delNode;}else {retNode root;TreeNode* cur root-right;TreeNode* pcur root;while (cur-left){pcur cur;cur cur-left;}delNode cur;retNode-val cur-val;if (pcur-left cur) {//右子树的最小值在右子树的左子树上pcur-left cur-right;}else {//右子树的最小值为右子树的根pcur-right cur-right;}delete delNode;}return retNode;
}
如果左子树为空则用右子树做为新的树根如果右子树为空则用左子树作为新的树根否则当左右子树都为非空时从右子树上找出最小的结点它的值作为根的新值并删除这个最小结点。 删除指定值的结点
//删除指定结点
TreeNode* BSTDelete(TreeNode* root, int val) {if (nullptr root) {return nullptr; }if (val root-val) {return Delete(root); }else if (val root-val) {root-left BSTDelete(root-left, val); }else if (val root-val) {root-right BSTDelete(root-right, val); }return root;
}
如果为空树则直接返回空结点如果需要删除的结点的值 等于 树根结点的值则直接调用接口 Delete 如果需要删除的结点的值 小于 树根结点的值则需要删除的结点必定在左子树上递归调用左子树的删除并且将返回值作为新的左子树的根结点 如果需要删除的结点的值 大于 树根结点的值则需要删除的结点必定在右子树上递归调用右子树的删除并且将返回值作为新的右子树的根结点返回当前树的根结点
