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

• 🍊1. 二叉搜索树的概念
• 🍊2.二叉搜索树中的查找
• 🍊3.二叉搜索树的插入
• 🍊4.删除二叉搜索树中的一个节点(较复杂)
• 🍊5.判断是不是二叉搜索树(易错)
• 🍊结束语

📃 个人主页: 不断前进的皮卡丘
🌞博客描述:梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记
🔥网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备----- 牛客网刷题神器

🍊1. 二叉搜索树的概念

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

🍊2.二叉搜索树中的查找

给定一棵二叉搜索树，以及一个值val,如果二叉搜索树中存在值和val相同的节点，则返回这个节点，否则返回null

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 插入二叉搜索树

二叉搜索树的插入需要考虑下面几种情况

1️⃣根节点为空，那么待插入的节点就作为二叉搜索树的根节点
2️⃣根节点非空，则找到待插入的位置

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 删除一个二叉搜索树中的节点

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 判断是不是二叉搜索树

判断是不是二叉搜索树，就是看这棵二叉树是否满足二叉搜索树的性质，当二叉搜索树进行中序遍历的时候，它们的节点的值是按照从小到大排序的，我们可以利用这个性质来解答。

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);    }}

🍊结束语

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

科普知事网