前言
二叉搜索树的定义：
若左子树不为空，则左子树上所有节点的值都小于根节点的值；
若右子树不为空，则右子树上所有节点的值都大于根节点的值。
树中不会有重复的元素。
二叉搜索树最左侧结点一定是最小的，最右侧一定是最大的；
对二叉搜索树进行中序遍历，一定能够得到一个有序序列。
目录
一、查找
以查找数据23为例。
从根节点往下遍历，遇到比23大的数据，往其左子树遍历，如果比23小的数据，往其右子树遍历，直到当前结点是我们需要查找的结点或为空结点为止。
代码：
public TreeNode search(int key) { TreeNode tmp = root; while(tmp != null){ if(tmp.key > key){ tmp = tmp.left; }else if(tmp.key < key){ tmp = tmp.right; }else{ return tmp; } } return null; }
二、插入
不能插入树中已有的元素！！！
以插入数据18为例。
从根节点往下遍历，遇到比18大的数据，往其左子树遍历，如果比18小的数据，往其右子树遍历，直到当前结点为空，插入数据18。
代码：
public boolean insert(int key) { if(root == null){ root = new TreeNode(key); return true; } TreeNode p = root; TreeNode c = root; while(c != null){ p = c; if(c.key < key){ c = c.right; }else if(c.key > key){ c = c.left; }else{ return false; } } if(p.key < key){ p.right = new TreeNode(key); }else{ p.left = new TreeNode(key); } return true; }
三、删除
设待删除的结点为tmp,其父母亲结点为parent
（一）tmp为左子树结点，有如下情况：
（二）tmp为右子树结点，有如下情况：
（三）tmp为根结点，有如下情况：
代码：
public boolean remove(int key) { TreeNode tmp = root; TreeNode parent = root;//标记父母亲结点 while(tmp != null){ if(tmp.key > key){ parent = tmp; tmp = tmp.left; }else if(tmp.key < key){ parent = tmp; tmp = tmp.right; }else{ break; } } if(tmp == null) return false; //删除操作 //为左孩子 if(tmp == parent.left){ if(tmp.left == null){ parent.left = tmp.right; }else if(tmp.right == null){ parent.left = tmp.left; }else{ //tmp左右孩子都不为空情况 func(tmp); } } else if(tmp == parent.right){ //右孩子 if(tmp.left == null){ parent.right = tmp.right; }else if(tmp.right == null){ parent.right = tmp.left; }else { //tmp左右孩子都不为空情况 func(tmp); } }else { //根节点 if(root.left == null){ root = root.right; }else if(root.right == null){ root = root.left; }else{ //tmp左右孩子都不为空情况 func(root); } } return true; } public void func(TreeNode tmp){ if(tmp == null) return; TreeNode ret = find(tmp); int key = ret.key; remove(ret.key); tmp.key = key; } //找到tmp结点右孩子的最左边 public TreeNode find(TreeNode tmp){ TreeNode tmp1 = tmp; tmp = tmp.right; while(tmp != null){ tmp1 = tmp; tmp = tmp.left; } return tmp1; }
最优情况下：二叉搜索树为完全二叉树，其平均比较次数为：log2 (n)
最坏情况下：二叉搜索树退化为单支树，其平均比较次数为：n/2
四、完整代码
public class BinarySearchTree { static class TreeNode { public int key; public TreeNode left; public TreeNode right; TreeNode(int key) { this.key = key; } } public TreeNode root; /** * 插入一个元素 * 不能插入二叉搜索树当中已有的数据， * 否则返回false * @param key */ public boolean insert(int key) { if(root == null){ root = new TreeNode(key); return true; } TreeNode p = root; TreeNode c = root; while(c != null){ p = c; if(c.key < key){ c = c.right; }else if(c.key > key){ c = c.left; }else{ return false; } } if(p.key < key){ p.right = new TreeNode(key); }else{ p.left = new TreeNode(key); } return true; } //查找key是否存在 public TreeNode search(int key) { TreeNode tmp = root; while(tmp != null){ if(tmp.key > key){ tmp = tmp.left; }else if(tmp.key < key){ tmp = tmp.right; }else{ return tmp; } } return null; } //删除key的值 public boolean remove(int key) { TreeNode tmp = root; TreeNode parent = root;//标记父母亲结点 while(tmp != null){ if(tmp.key > key){ parent = tmp; tmp = tmp.left; }else if(tmp.key < key){ parent = tmp; tmp = tmp.right; }else{ break; } } if(tmp == null) return false; //删除操作 //为左孩子 if(tmp == parent.left){ if(tmp.left == null){ parent.left = tmp.right; }else if(tmp.right == null){ parent.left = tmp.left; }else{ //tmp左右孩子都不为空情况 func(tmp); } } else if(tmp == parent.right){ //右孩子 if(tmp.left == null){ parent.right = tmp.right; }else if(tmp.right == null){ parent.right = tmp.left; }else { //tmp左右孩子都不为空情况 func(tmp); } }else { //根节点 if(root.left == null){ root = root.right; }else if(root.right == null){ root = root.left; }else{ //tmp左右孩子都不为空情况 func(root); } } return true; } public void func(TreeNode tmp){ if(tmp == null) return; TreeNode ret = find(tmp); int key = ret.key; remove(ret.key); tmp.key = key; } //找到tmp结点右孩子的最左边 public TreeNode find(TreeNode tmp){ TreeNode tmp1 = tmp; tmp = tmp.right; while(tmp != null){ tmp1 = tmp; tmp = tmp.left; } return tmp1; } }
结语
代码链接在这里哦~
二叉搜索树 · Yjun6/DataStructrue@4f9a2c1 (github.com)
这篇博客如果对你有帮助，给博主一个免费的点赞以示鼓励，欢迎各位🔎点赞👍评论收藏⭐，谢谢！！！
