二叉搜索树
前言
二叉搜索树的定义： 若左子树不为空，则左子树上所有节点的值都小于根节点的值； 若右子树不为空，则右子树上所有节点的值都大于根节点的值。 树中不会有重复的元素。
二叉搜索树最左侧结点一定是最小的，最右侧一定是最大的； 对二叉搜索树进行中序遍历，一定能够得到一个有序序列。
目录
一、查找
以查找数据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)
这篇博客如果对你有帮助，给博主一个免费的点赞以示鼓励，欢迎各位🔎点赞👍评论收藏⭐，谢谢！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-07-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
