数据结构与算法:二叉搜索树

亦凉 2024-04-21 08:02 160阅读 0赞

> #### ✨数据结构与算法:二叉搜索树 ####
> 
>  *  ?1. 二叉搜索树的概念
>  *  ?2.二叉搜索树中的查找
>  *  ?3.二叉搜索树的插入
>  *  ?4.删除二叉搜索树中的一个节点(较复杂)
>  *  ?5.判断是不是二叉搜索树(易错)
>  *  ?结束语
> 
>   
> ? **个人主页**: [不断前进的皮卡丘][Link 1]  
> **?博客描述:梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记**  
> **?网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备**\----- [牛客网刷题神器][Link 2]

## ?1. 二叉搜索树的概念 ##

![在这里插入图片描述][78232898d720495ca2495da1149349fd.png]

> ?**二叉搜索树又叫做二叉排序树，它具有下面的几个性质:**  
> 1️⃣**若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；**  
> 2️⃣**若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
> 3️⃣它的左、右子树也分别为二叉排序树**

## ?2.二叉搜索树中的查找 ##

> **给定一棵二叉搜索树，以及一个值val,如果二叉搜索树中存在值和val相同的节点，则返回这个节点，否则返回null**  
> ![在这里插入图片描述][00eeae0b6c714d52866ffbfc744bfc23.png]

public TreeNode searchBST(TreeNode root, int val) {
        
            if(root==null) return null;
            TreeNode curr=root;
            while(curr!=null){
        
                if(curr.val==val){
        
                    return curr;
                }else if(curr.val<val){
        
                    curr=curr.right;
                }else{
        
                    curr=curr.left;
                }
            }
            //循环外面说明没有找到
            return null;
        }

## ?3.二叉搜索树的插入 ##

[NC372 插入二叉搜索树][NC372]

> **二叉搜索树的插入需要考虑下面几种情况**
> 
> 1️⃣**根节点为空，那么待插入的节点就作为二叉搜索树的根节点**  
> 2️⃣**根节点非空，则找到待插入的位置**
> 
> ![在这里插入图片描述][d6e152c25143471b86d2ace5e988283f.png]

public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @param val int整型 
         * @return TreeNode类
         */
        public TreeNode insertToBST (TreeNode root, int val) {
        
            // write code here
            if(root==null) return new TreeNode(val);
            TreeNode curr=root;
            TreeNode parent=null;
            while(curr!=null){
        
                if(curr.val==val){
        
                    break;
                }else if(curr.val<val){
        
                    parent=curr;
                    curr=curr.right;
                }else{
        
                    parent=curr;
                    curr=curr.left;
                }
            }
            if(curr==parent.left){
        
                parent.left=new TreeNode(val);
            }else{
        
                parent.right=new TreeNode(val);
            }
             
            return root;
        }
    }

## ?4.删除二叉搜索树中的一个节点(较复杂) ##

[NC297 删除一个二叉搜索树中的节点][NC297]  
![在这里插入图片描述][3daded9a0f0349308731780ce492dc02.png]

public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @param key int整型 
         * @return TreeNode类
         */
         public TreeNode deleteNode(TreeNode root, int key) {
        
            root = delete(root,key);
            return root;
        }
    
        private TreeNode delete(TreeNode root, int key) {
        
            if (root == null) return null;
    
            if (root.val > key) {
        
                root.left = delete(root.left,key);
            } else if (root.val < key) {
        
                root.right = delete(root.right,key);
            } else {
        
                if (root.left == null) return root.right;
                if (root.right == null) return root.left;
                TreeNode tmp = root.right;
                while (tmp.left != null) {
        
                    tmp = tmp.left;
                }
                root.val = tmp.val;
                root.right = delete(root.right,tmp.val);
            }
            return root;
        }
    }

## ?5.判断是不是二叉搜索树(易错) ##

[NC184 判断是不是二叉搜索树][NC184]

> **判断是不是二叉搜索树，就是看这棵二叉树是否满足二叉搜索树的性质，当二叉搜索树进行中序遍历的时候，它们的节点的值是按照从小到大排序的，我们可以利用这个性质来解答。**![在这里插入图片描述][82e3d7f5266a4b4bbcc3e7da938f75de.png]

public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @return bool布尔型
         */
          long pre = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            // 访问左子树
            if (!isValidBST(root.left)) {
        
                return false;
            }
            // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
            if (root.val <= pre) {
        
                return false;
            }
            pre = root.val;
            // 访问右子树
            return isValidBST(root.right);
        }
    }

## ?结束语 ##

> 希望大家可以自己动手练习一下，算法光看是不行的，必须亲自动手敲代码，有时候你会发现自己有思路，但是又写不出来，这就是缺乏练习的原因。大家平时在做题的时候，可以多思考，多总结。  
> 刚开始的时候，我们可能遇到一种新的题型，完全没有思路的时候，其实可以先去看看别人的思路，还有题解，把它理解下来，然后把代码敲出来(不要复制粘贴,我们根据自己的理解敲出代码这样才有效果，如果中途卡住了，也可以再回过头去看看)  
> 另外，为了检测一下我们是否真正的掌握，我们可以去做几道相似的题目巩固一下，顺便检验一下自己的成果。  
> [点此跳转去练习][Link 2]![在这里插入图片描述][5e96aa56fa7445e49d327faa99883c79.png]

[Link 1]: https://blog.csdn.net/qq_52797170?spm=1010.2135.3001.5343
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_pkq_sf
[78232898d720495ca2495da1149349fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/9a9ca75e041140f9be22764ae94fb5da.png
[00eeae0b6c714d52866ffbfc744bfc23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/7e02596af3ad4879a8882503f45b334c.png
[NC372]: https://www.nowcoder.com/practice/4900db9ddfbd43a7a9841c6a408bacf2?tpId=196&tqId=40503&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E6%2590%259C%25E7%25B4%25A2&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E6%90%9C%E7%B4%A2
[d6e152c25143471b86d2ace5e988283f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/e12dc7ea578d4462b0347705e7d84760.png
[NC297]: https://www.nowcoder.com/practice/c1c2970c7a3e442b8e41423e88d099fb?tpId=196&tqId=39788&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E6%2590%259C%25E7%25B4%25A2&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E6%90%9C%E7%B4%A2
[3daded9a0f0349308731780ce492dc02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/a2a6aba53d66405085cf3bd44fedf2b0.png
[NC184]: https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=196&tqId=39342&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E6%2590%259C%25E7%25B4%25A2&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E6%90%9C%E7%B4%A2
[82e3d7f5266a4b4bbcc3e7da938f75de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/0ea248b1075e490f948b266f3d7d0fe3.png
[5e96aa56fa7445e49d327faa99883c79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/1f32e4a1207349ba93462aacc63a8174.png