1.二叉搜索树(Binary Search Tree):
(又:二叉查找树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
2.建二叉树
static class TreeNode {
public int val;//值
public TreeNode left;//左边
public TreeNode right;//右边
public TreeNode(int val) {//构造方法,用于赋值
this.val = val;
}
}
3.搜索操作
//搜索操作
public TreeNode search(int key) {//查找key
TreeNode cur = root;
while(cur != null) {
if(cur.val == key) {
return cur;
} else if(cur.val < key) {
cur = cur.right;
}else {
cur = cur.left;
}
}
return null;
}
4.插入操作
//插入操作
public void insertTree(int val) {
//如果二叉搜索树为空,直接插入值
if(root == null) {
root = new TreeNode(val);
return;
}
TreeNode cur = root;
TreeNode parent = null;
while(cur != null) {
if(cur.val < val) {
parent = cur;
cur = cur.right;
} else {
parent = cur;
cur = cur.left;
}
}
TreeNode node = new TreeNode(val);
if(parent.val < val) {
parent.right = node;
} else {
parent.left = node;
}
}
5.删除操作
5.1:cur.lelf == null 左子树为空
cur 是root,则root = cur.right
cur不是root,cur是parent.left,则parent.left=cur.right
cur不是root,cur是parent.right,则parent.right=cur.right
5.2:cur.right == null 右子树为空
右子树为空与左子树为空大致相同,可以自行推理。
5.3:cur.lelf != null&&cur.right != null 左右子树都不为空
思路:
- 左树找最大数据
- 右树找最小数据
这里演示右树找最小数据
top1:找的树在左边
**top2:**找的树在右边
//删除操作
public void remove(int key) {
TreeNode cur = root;
TreeNode parent = null;//查找相应结点然后删除
while(cur != null) {
if(cur.val == key) {
removeNode(parent,cur);//删除函数
return ;
} else if(cur.val < key) {
parent = cur;
cur = cur.right;
} else {
parent = cur;
cur = cur.left;
}
}
}
//通过removeNode函数进行删除
public void removeNode(TreeNode parent,TreeNode cur) {
if(cur.left == null) {//左子树为空
if(cur == root) {
root = cur.right;
} else if(cur == parent.left) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
} else if(cur.right == null) {
if(cur == root) {//右子树为空
root = cur.left;
} else if(cur == parent.left) {
parent.left = cur.left;
} else {
parent.right = parent.left;
}
} else {//替罪羊的删除*//左边找最大,右边找最小
TreeNode targetparent = cur;
TreeNode target = cur.right;
while(target.left != null) {
targetparent = target;
target = target.left;
}
cur.val = target.val;
if(targetparent.left == target) {
targetparent.left = target.right;
} else {
targetparent.right = target.right;
}
}
}
二叉搜索树测试及完整代码:
https://gitee.com/btyyt/growing-xbt/commit/d2976f8036a9ef757cb9f00e3f42ac460096d90a