沈阳整站优化,产品销售网站模块如何设计,wordpress的中英文,网站开发设计二叉搜索树的概念 二叉搜索树 (BST#xff0c;Binary Search Tree)#xff0c;也称二叉排序树或二叉查找树。它要么是一颗空树#xff0c;要么是满足以下性质的二叉树#xff1a; 若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值。若它的右子树不为…二叉搜索树的概念 二叉搜索树 (BSTBinary Search Tree)也称二叉排序树或二叉查找树。它要么是一颗空树要么是满足以下性质的二叉树 若它的左子树不为空则左子树上所有节点的值都小于根节点的值。若它的右子树不为空则右子树上所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树。 如上图左侧的二叉树不是一颗二叉搜索树右侧的二叉树是一颗二叉搜索树。
**为什么叫二叉搜索树(二叉查找树)呢**因为二叉搜索树擅长搜索和查找。如下图的二叉搜索树我们要查找 10首先与根节点比较10 大于 9那么就去他的右子树查找。右子树的根节点为 13 大于 10那么就去他的左子树查找。左子树的根节点为 10 刚好等于 10查找成功如果节点不存在那么就是查找到树的叶节点还没有找到目标节点。 理想状态下二叉搜索树查找的时间复杂度为O(logN)。但是理想很丰满现实很骨干。有一种情况能使得二叉搜索树变成链表从而使得查找的时间复杂度变为 O(N)。
如下图当依次向一颗空的二叉搜索树中插入有序的节点。那么这颗二叉搜索树就会变成链表。 **为什么叫二叉排序树呢**那是因为一颗二叉搜索树的中序遍历的结果是有序的中序遍历就是在递归遍历二叉树的时候先访问左子树在访问根节点最后才是右子树。不会中序遍历不要紧等我们实现了一颗二叉搜索树中序遍历一次你就知道他为啥叫二叉排序树了
二叉搜索树的实现
二叉搜索树的基本结构
定义二叉搜索树的基本结构
首先我们需要定义一个节点的类表示二叉树的一个节点成员变量就是左子树的节点指针右子树的节点指针以及当前节点存储的值。构造函数的话就是传入一个 key 用来初始化节点的 _key 就行啦指针全部初始化为 nullptr。然后就要定义二叉搜索树的类啦里面会封装各种操作的函数。至于成员变量当然就是根节点的指针啦至于构造函数一开始是一颗空的二叉搜索树嘛将根节点的指针初始化为 nullptr 就行啦
templateclass K
struct BSTNode
{BSTNodeK* _left;BSTNodeK* _right;K _key;BSTNode(const K key):_key(key),_left(nullptr),_right(nullptr){}
};templateclass K
class BSTree
{typedef BSTNodeK Node;
public:BSTree():_root(nullptr){}private:Node* _root;
};bool insert(const K key)
在我们实现的二叉搜索树中一颗树中是没有相同节点的。
插入的过程其实很简单呢将待插入的节点 key 与根节点的 _key 作比较
如果待插入节点的 key 大于根节点的 _key那么继续与右子树根节点的 _key 比较。如果带插入节点的 key 小于根节点的 _key那么继续与左子树根节点的 _key 比较。如果遇到根节点为 nullptr那么直接插入这个节点从而完成二叉搜索树的插入操作。 bool insert(const K key)
{Node* newNode new Node(key); //构造新插入的节点if(_root nullptr) //如果是一颗空的二叉搜索树修改根节点就行了{_root newNode;}else{Node* cur _root; //新插入的节点每次都与 cur 比较判断其插入位置Node* parent nullptr; //记录上父节点方便最后的插入while(cur){if(key cur-_key) //key 大于 cur-_key 去右子树{parent cur;cur cur-_right;}else if(key cur-_key) //key 小于 cur-_key 去左子树子树{parent cur;cur cur-_left;}else //相等的情况不存在我们规定二叉搜索树中不存在 _key 值相同的节点插入失败{return false; }}//确定插入的位置if(key parent-_key)parent-_right newNode;elseparent-_left newNode;}//插入成功return true;
}为了方便测试插入的结果是否正确我们需要写一个中序遍历的函数中序遍历在 C 语言阶段都是写过了的忘记了的 uu 可以去复习复习。
C语言数据结构初阶(10)----二叉树的实现-CSDN博客
写成成员函数通过类的对象调用我们需要传参根节点的指针但是这个成员变量是私有的外面拿不到你可以写一个函数获取根节点的指针但是这里会有一个更加优雅的写法
void inorder()
{_inorder(_root);cout endl;
}void _inorder(Node* root)
{if(root nullptr)return;_inorder(root-_left);cout root-_key ;_inorder(root-_right);
}中序遍历写好了就方便我们测试一颗二叉树是不是二叉搜索树啦二叉搜索树的中序遍历是有序的中序遍历有序的树也是二叉搜索树。
#includeiostream
using namespace std;
#includeBSTree.hint main()
{BSTreeint bst;int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};for(auto e : a)bst.insert(e);bst.inorder();return 0;
}我们看到中序遍历的结果的确是有序的呢那我们的插入函数就是没有问题的
bool find(const K key)
find 写起来比 insert 还简单哈
如果待查找的 key 比根节点的 _key 大那么就去右子树查找。如果待查找的 key 比根节点的 _key 小那么就去左子树查找。如果待查找的 key 与根节点的 _key 相等那么查找成功。如果根节点为 nullptr 还没有查找成功那么查找失败。
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;
}void erase(const K key)
erase 接口是二叉搜索树中最难实现的接口呢
删除二叉搜索树中的节点可以分为以下情况 如果删除节点的度为 0即删除的节点没有左右孩子。那么直接删除这个节点然后改变父节点指针的指向就可以啦 如果删除节点的度为 1即删除的节点有一个孩子。那么删除这个节点之后令父节点相应的指针指向该删除节点的孩子即可。 什么是父节点的相应指针 如果待删除的节点是其父节点的右孩子那么删除这个节点之后令父节点的 _right 指针指向该删除节点的孩子即可。如果待删除的节点是其父节点的左孩子那么删除这个节点之后令父节点的 _left 指针指向该删除节点的孩子即可。 如果待删除节点的度为 2即待删除的节点有两个孩子。此时我们选择使用替换法即选择待删除节点的左右子树中的某一个节点来替代待删除节点的位置最后删除那个被选择用来替代删除节点的节点即可 选择哪一个节点来替代待删除的节点呢选择的依据就是替代之后的树应满足二叉搜索树嘛因此就会有两种选择的方式 选择待删除节点的左子树中最大的那个节点。 选择待删除节点的右子树中最小的那个节点。 例如如上图我们要删除 3 这个节点可以选择左子树中最大的节点 1 来代替 3或者选择右子树中最小的节点 4 来代替 3。这两种选法均可使得删除后的二叉树满足二叉搜索树的性质。 替换之后呢要删除的节点的特性要么满足情况 1要么满足情况 2。就很好办啦 怎么找到二叉搜索树中的最大节点与最小节点呢 二叉搜索树的最大节点位于整棵树的最右侧。二叉搜索树的最小节点位于整棵树的最左侧。
其实经过仔细的观察我们发现第一种情况和第二种情况是可以合并的第一种情况是删除后父节点指针置空第二种情况是删除后父节点指向不为空的那个节点
那么合并之后就是如果待删除的节点的左孩子为空那么令父节点指向右孩子就可以啦否则令父节点指向左孩子。或者如果待删除的节点的右孩子为空那么令父节点指向左孩子否者指向右孩子。
一定要看代码中的注释哦还有一部分的细节在注释里面提到了。
bool erase(const K key)
{Node* prev nullptr;Node* cur _root;//找到要被删除的那个节点while(cur){if(key cur-_key){prev cur;cur cur-_right;}else if(key cur-_key){prev cur;cur cur-_left;}else //找到了那个要被删除的节点{ //左子树为空链接右子树if(cur-_left nullptr){//这里是删除根节点的特殊情况if(cur _root)_root cur-_right;else{//确定删除的节点位于其父节点的哪个位置if(prev-_right cur)prev-_right cur-_right;elseprev-_left cur-_right;}}else if(cur-_right nullptr) //右子树为空链接左子树{//处理删除根节点的特殊情况if(cur _root)_root cur-_left;else{//确定删除的节点位于其父节点的哪个位置if(prev-_right cur)prev-_right cur-_left;elseprev-_left cur-_left;}}else{//找到左子树中较大的那个节点作为替换的节点Node* leftMax cur-_left;Node* parent cur;while(leftMax-_right){parent leftMax;leftMax leftMax-_right;}//交换swap(leftMax-_key, cur-_key);//处理特殊情况左子树的最大节点不一定是其父节点的右孩子//当删除的节点的左孩子就是左子树的最大值这就是那个特殊情况if(parent-_left leftMax){parent-_left leftMax-_left;}else{parent-_right leftMax-_left;}cur leftMax;}//删除节点delete cur;return true;} }return false;
}
