资讯专栏INFORMATION COLUMN

数据结构 : 二叉搜索树(BST)

jsummer / 1233人阅读

摘要:待删除的节点待删除节点的父节点如果为跟节点转头行动这个循环结束后,就表明的左节点为不为根节点这里有个问题怎么判断待删除的节点是父节点的左节点还是右节点呢


?‍?

?‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍??‍?

?‍?


是一颗普普通通的二叉树

是一颗普普通通的二叉搜索树

 

 你

能发现它们两个之间有什么不同吗

不能?

你仔细一看?      哦   原来如此!

 ?二叉搜索树

1. 节点的左子树只包含 小于 当前节点的数

2. 节点的右子树只包含 大于 当前节点的数

3.所有左子树右子树自身必须也是二叉搜索树

这就是二叉搜索树

?创建二叉搜索树

?‍?在创建每个树之前,都需要先把节点定义好

public class TreeNode {    public int val;    public TreeNode left;    public TreeNode right;    public TreeNode(){}    public TreeNode(int val){        this.val = val;    }    public TreeNode(int val, TreeNode left, TreeNode right){        this.val = val;        this.left = left;        this.right = right;    }}

?‍?进行节点的插入

    public TreeNode insertIntoBST(TreeNode root, int val) {        TreeNode node = new TreeNode(val);        //root为null,表示初次进行二叉树的插入        //则root 也就等于 node 节点        if (root == null){            root = node;            return root;        }        //利用cur遍历二叉搜索树        TreeNode cur = root;        //标记父节点        TreeNode pre = null;        while(cur != null){            //更新父节点            pre = cur;            //这里利用了二叉搜索树的定义            //如果父节点的val小于插入节点的val, 则把插入的节点放到父节点的右支            //如果父节点的val大于插入节点的val, 则把插入的节点放到父节点的左支            if (cur.val > val){                cur = cur.left;            }else{                cur = cur.right;            }        }        //循环结束后,cur为空,pre此时为待插入的父节点        //比较待插入节点的val和父节点val的大小        //大则右,小则左        if (pre.val > val){            pre.left = node;        }else{            pre.right = node;        }        return root;    }

?‍?如下一颗二叉搜索树,如果要插入的一个节点为6

 

?‍? 6节点比5节点要大,使用要放在右支

 

 ?‍?这就完成了对二叉搜索树的插入

不是说创建二叉搜索树吗,怎么说的是二叉搜索树的插入?

其实创建二叉搜索树就相当于对二叉搜索树进行一个个的插入操作

?二叉搜索树查找

?‍?找到则返回该节点,找不到则返回null

如果看到递归就头疼,建议多做一些关于递归的题目

    public TreeNode searchBST(TreeNode root, int val) {        if (root == null){            return null;        }        //当前节点的val等于要查找的val,则直接返回该节点        if (root.val == val){            return root;        }        //当前节点的val大于要查找的val,则要对左子树进行查询        if (root.val > val){            return searchBST(root.left,val);        }        //当前节点的val小于要查找的val,则要对右子树进行查询        return searchBST(root.right,val);    }

?二叉搜索树删除

?‍?二叉搜索树最难的地方就在删除这一块

采用的方法为: 替罪?法

首先要明白的是:

要想删除该节点,则先要找到该节点,还有该节点的父节点

1.该怎么找到要删除的节点?

答:进行二叉树的查找 

2.该怎么找到要删除节点的父节点?

答:定义个prev节点来追踪待删除节点的父节点

3.待删除的节点情况的分类?

答:从大的方向分 该节点为跟节点,该节点不为跟节点。

    public TreeNode deleteNode(TreeNode root, int key) {        if (root == null){            return null;        }        //待删除的节点        TreeNode waitingDelete = root;        //待删除节点的父节点        TreeNode prev = null;        while(waitingDelete != null &&waitingDelete.val != key){            prev = waitingDelete;            if (waitingDelete.val > key){                waitingDelete = waitingDelete.left;            }else{                waitingDelete = waitingDelete.right;            }        }        if (waitingDelete == null){            return root;        }        //如果为跟节点        if (prev == null){            if (waitingDelete.right == null){                //转头行动                root = waitingDelete.left;            }else{                TreeNode cur = waitingDelete.right;                if (cur.left == null){                    cur.left = root.left;                    root = cur;                }else{                    TreeNode preCur = null;                    //这个循环结束后,就表明cur的左节点为null                    while(cur.left != null){                        preCur = cur;                        cur = cur.left;                    }                    preCur.left = cur.right;                    cur.left = waitingDelete.left;                    cur.right = waitingDelete.right;                    root = cur;                }            }        }else{            //不为根节点,这里有个问题:怎么判断待删除的节点是父节点的左节点还是右节点呢?            if (waitingDelete.right == null){                if (prev.left == waitingDelete){                    prev.left = waitingDelete.left;                }else{                    prev.right = waitingDelete.left;                }            }else{                TreeNode cur = waitingDelete.right;                if (cur.left == null){                    cur.left = waitingDelete.left;                    if (prev.left == waitingDelete){                        prev.left = cur;                    }else{                        prev.right = cur;                    }                }else{                    TreeNode preCur = null;                    while(cur.left != null){                        preCur = cur;                        cur = cur.left;                    }                    preCur.left = cur.right;                    cur.left = waitingDelete.left;                    cur.right = waitingDelete.right;                    if (prev.left == waitingDelete){                        prev.left = cur;                    }else{                        prev.right = cur;                    }                }            }        }

 

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/121792.html

相关文章

  • 【LeetCode 二叉专项】把二叉搜索转换为累加(538)

    摘要:解法一中序遍历分析由于给定了二叉搜索树,因此首先考虑中序遍历,使用示例,我们先来分别看一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。这里还是使用示例,我们再来观察一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。 ...

    xcold 评论0 收藏0
  • 数据结构与算法对的javaScript描述-二叉搜索

    摘要:定义树以及相关概念二叉搜索树的定义首先是二叉树最多有两个节点,分别是左右节点子节点的位置是确定的,变现为左子节点的值小于其父节点右子节点的值大于其父节点在中的描述描述的完整代码传送门可视化传送门节点类树是由节点组成的,要实现树那么先要实现节 定义 树以及相关概念 showImg(https://segmentfault.com/img/remote/1460000012578627?w...

    forrest23 评论0 收藏0
  • 每周一练 之 数据结构与算法(Tree)

    摘要:假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。代码实现二叉树节点定义来源验证二叉搜索树解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 ...

    zhonghanwen 评论0 收藏0
  • 每周一练 之 数据结构与算法(Tree)

    摘要:假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。代码实现二叉树节点定义来源验证二叉搜索树解析这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据结构与算法(LinkedList) 3...

    fizz 评论0 收藏0
  • [Leetcode] Kth Smallest Element in a BST 二叉搜索第k小节

    摘要:中序遍历复杂度时间空间思路因为左节点小于根节点小于右节点,二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。这里采用迭代形式,我们就可以在找到第小节点时马上退出。这样我们就可以用二叉树搜索的方法来解决这个问题了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

    Dean 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<