目录
题外话
正题
二叉搜索树
底层实现
二叉搜索树查找操作
查找操作思路
查找代码实现详解
二叉搜索树插入操作
插入操作思路
插入代码详解
二叉搜索树删除操作
删除操作思路
删除代码详解
小结
题外话
我的一切都是党给的,都是人民给的,都是家人们给的!!
十分感谢家人们的大力支持,没有你们就没有我的今天(作者磕头三响!!!)
正题
今天来复习一下二叉搜索树正好完成一下底层实现
二叉搜索树
二叉搜索树概念:如果一颗二叉搜索树的任一结点的左子树不为空,那么左子树一定比该结点值小
如果一颗二叉搜索树的任一结点的右子树不为空,那么右子树一定比该结点值大
如下图,就是一颗二叉搜索树
任一一颗二叉搜索树中序遍历一定是有序的
底层实现
我们先将搜索二叉树的结点和结点值,还有左右子树创建出来
static class TreeNode
{
//创建结点元素值val
public int val;
//创建搜索二叉树的左右子树
public TreeNode left;
public TreeNode right;
//通过TreeNode的构造方法赋值val
public TreeNode(int val)
{
this.val=val;
}
}
//创建搜索二叉树的根
public TreeNode root;
二叉搜索树查找操作
查找操作思路
我们通过搜索二叉树的概念,让key和根结点值比较
如果比根结点大,就和根结点右子树比较
如果比根结点小就和根结点左子树比较
例如上图,key等于9的时候在图中能找到9的结点
而当key等于10的时候,走到结点值为9的位置后左右结点为空,所以找不到等于10的结点返回flase
所以可以很容易写出以下代码
查找代码实现详解
public boolean search(int key)
{
//将根结点赋值给cur,防止遍历完成找不到搜索二叉树的根节点
TreeNode cur=root;
//当cur不为空
while (cur!=null)
{
//如果cur的val值小于key说明key在cur的右边
if (cur.val<key)
{
//cur等于cur的右子树
cur=cur.right;
}
//如果cur的val值比key大,说明key在cur的左边
else if (cur.val>key)
{
//cur等于cur的左子树
cur=cur.left;
}
//如果cur的val值等于key,说明找到了,则返回true
else {
return true;
}
}
//如果cur为空还没有找到key说明key在搜索二叉树中不存在返回false
return false;
}
二叉搜索树插入操作
插入操作思路
1.如果根结点为空,直接让插入元素val插入到根结点位置
2.如果根结点不为空
如果val大于根结点则继续判断root右子树和val大小关系
如果val小于根结点则继续判断root左子树和val大小关系
3.如下图所示,当我们走到结点值为9的位置发现val=10仍然大于9
然后继续往9的右子树走,发现为空
我们将val=10插入9的右子树,但是我们没有记录9这个结点,无法向9这个结点的右子树插入val
所以我们需要记录最近一次到达的上一个结点,以便可以将结点连接在一起
4.如果val是二叉搜索树中的结点值其中之一
比如val=5,这无法插入
因为二叉搜索树中的元素一定是没有重复的
要么比任意结点小,要么比任意结点大
不可能出现两个结点相同的情况
所以当出现插入元素和二叉搜索树中元素相同时,我们选择返回false
插入代码详解
public boolean insert(int val)
{
//如果根结点为空则将插入结点作为根结点
if (root==null)
{
root=new TreeNode(val);
return true;
}
//如果根结点不为空,将root赋值给cur
TreeNode cur=root;
//创建prent记录cur到达的上一个结点
TreeNode parent=null;
//当cur不为空
while (cur!=null) {
//如果cur的val值比插入值小,则让parent记录当前cur结点,并且cur等于cur的右子树
if (cur.val < val) {
parent=cur;
cur = cur.right;
}
//如果cur的val值比插入值大,则让parent记录当前cur结点,并且cur等于cur的左子树
else if (cur.val > val) {
parent=cur;
cur = cur.left;
}
//如果cur的val值等于插入值,则无法插入,返回false
else {
return false;
}
}
//当cur==null说明cur已经到达了要插入的位置
TreeNode node=new TreeNode(val);
//如果插入值比cur到达的上一个结点值大,则插入在上一个结点值的右边
if (val> parent.val)
{
parent.right=node;
}
//如果插入值比cur到达的上一个结点值小,则插入在上一个结点值的左边
else {
parent.left=node;
}
//最后插入完成返回true
return true;
}
接下来讲解一下搜索二叉树删除操作(有点难)
大家跟紧我的思维!
二叉搜索树删除操作
删除操作思路
首先咱们思考一下,删除搜索二叉树结点元素我们需要考虑什么问题
1.首先要遍历搜索二叉树找到要删除的结点
2.考虑搜索二叉树为空,没有结点的情况,无法删除
3.考虑搜索二叉树删除结点的左子树为空的情况如下图,cur为要删除结点
4.考虑搜索二叉树删除结点的右子树为空的情况,这里就不展示了,和上面情况差不多
5.考虑搜索二叉树删除结点的左子树右子树都不为空的情况(认真理解)
这里统一采用找到删除结点的右子树最深左结点的方法
找到get分两种情况下图是第一种
下图是第二种
以上内容我最开始也想不出来,但是做多了关于二叉树的题之后,也渐渐找到了这类型题的规律
基本上任何二叉树的题都和遍历二叉树有关系,也就是在遍历二叉树的基础上
无非是比较结点大小,或者结点是否存在等等变化,大家可以试着体会一下
删除代码详解
这里用了两个方法
1.第一个方法是找到要删除的结点
2.第二个方法是接收要删除的结点,以及遍历的上一个结点值
//这个方法是用来找到要删除的结点,并调用删除结点方法
public boolean remove(int val)
{
//当二叉搜索树为空树,则返回false
if (root==null)
{
return false;
}
//让root赋值给cur去遍历二叉搜索树
TreeNode cur=root;
//设置parent记录上一个遍历的结点
TreeNode parent=null;
//当cur不等于空就继续找删除结点
while (cur!=null) {
//如果cur的val值比删除值小,则让parent记录当前cur结点,并且cur等于cur的右子树
if (cur.val < val) {
parent=cur;
cur = cur.right;
}
//如果cur的val值比删除值大,则让parent记录当前cur结点,并且cur等于cur的左子树
else if (cur.val > val) {
parent=cur;
cur = cur.left;
}
//如果cur的val值等于删除值,则说明cur所在就是要删除的结点
// 则调用remoNode方法,传入删除结点cur和parent
else {
removeNode(cur,parent);
return true;
}
}
//当cur等于空就说明二叉搜索树中不存在删除结点,返回false
return false;
}
//这个方法负责接收要删除的结点和上一个到达的结点,并删除结点值
private void removeNode(TreeNode cur,TreeNode parent)
{
//一.如果要删除结点的左子树为空(三种情况)
if (cur.left==null)
{
//1.如果根结点等于要删除结点cur
if (root==cur)
{
//让root指向root的右子树
root=root.right;
}
//2.如果cur为parent的左子树
else if (cur==parent.left)
{
//则让parent的左子树指向cur.right的右子树
parent.left=cur.right;
}
//3.如果cur为parent的右子树
else {
//则让parent的右子树指向cur的右子树
parent.right=cur.right;
}
}
//二.当要删除结点cur的右子树为空时(三种情况)
else if (cur.right==null)
{
//1.如果cur等于根结点
if (cur==root)
{
//让根结点指向cur的左子树
root=cur.left;
}
//2.如果cur等于parent的左子树
else if(cur==parent.left)
{
//则让parent的左子树指向cur的左子树
parent.left=cur.left;
}
//3.如果cur等于parent的右子树
else {
//则让parent的右子树指向cur的左子树
parent.right=cur.left;
}
}
//三.如果左子树右子树都不为空
else {
//设置getParent指向cur,设置get指向cur的右子树
TreeNode getParent=cur;
TreeNode get=cur.right;
//如果get的左子树不为空,就去找到cur.right的最深左结点,并让getPatent记录上一个到达的结点
while (get.left!=null)
{
getParent=get;
get=get.left;
}
//当get左子树为空,说明找到了最深左结点,让get的val覆盖cur的val
cur.val=get.val;
//如果cur.right有左子树,getParent的左子树一定会等于get结点
if (getParent.left==get)
{
//get不可能有左子树了,所以直接让getParent左子树指向get的右子树,图中第一种情况
getParent.left=get.right;
}
//如果cur.right没有左子树,直接让getParent的右子树指向get的右子树即可,图中第二种情况
else {
getParent.right=get.right;
}
}
}
小结
今天是真的超级努力
早上从10点多起床,洗漱然后吃饭,从十一点半学到了现在,七个多小时,晚上还有课三个小时
最热爱的一集!!
麻烦喜欢的家人们给个三连好嘛!!!(点赞关注收藏!!!)
