一、搜索树
1.1 概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
它的左右子树也分别为二叉搜索树。
如：
1.2 查找
若根节点不为空：
如果根节点==查找key 返回当前节点；
如果根节点 >查找key在其左子树查找；
如果根节点<查找key在其右子树查找；否则就是没有找到，返回null；
class Node{
public int val;
public Node left;
public Node right;
public Node（int val）{
this.val = val;
}
}
//二叉搜索树
public class BinarySearchTree {
public Node root = null;
//查找
public Node search（int key）{
Node 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;
}
1.3 插入
用cur和parent来找到val需要存储的位置。
parent.val 和val比较大小，确定是在左边还是在右边进行插入。
public boolean insert（int val） {
if（root == null） {
root = new Node（val）;
return true;
}
Node cur = root;
Node parent = null;
while （cur != null） {
if（cur.val < val） {
parent = cur;
cur = cur.right;
}else if（cur.val == val） {
return false;//不能有相同的数据
}else {
parent = cur;
cur = cur.left;
}
}
Node node = new Node（val）;
if（parent.val < val） {
parent.right = node;
}else {
parent.left = node;
}
return true;
}
1.4 删除
设待删除结点为 cur, 待删除结点的双亲结点为 parent；
cur.left == null
cur 是 root，则 root = cur.right
cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
cur.right == null
cur 是 root，则 root = cur.left
cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
cur.left != null && cur.right != null
需要使用替换法进行删除：
在cur的左树当中找最大值或者在cur的右树中找最小值
用它的值填补到被删除节点中，再来处理该结点的删除问题。
/**
* Created With IntelliJ IDEA
* Description:
* Users: yyyyy
* Date: 2022-02-19
* Time: 16:43
*
*/
class Node{
public int val;
public Node left;
public Node right;
public Node（int val）{
this.val = val;
}
}
//二叉搜索树
public class BinarySearchTree {
public Node root = null;
//查找
public Node search（int key）{
Node 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;
}
//插入
public boolean insert（int val） {
if（root == null） {
root = new Node（val）;
return true;
}
Node cur = root;
Node parent = null;
while （cur != null） {
if（cur.val < val） {
parent = cur;
cur = cur.right;
}else if（cur.val == val） {
return false;//不能有相同的数据
}else {
parent = cur;
cur = cur.left;
}
}
Node node = new Node（val）;
if（parent.val < val） {
parent.right = node;
}else {
parent.left = node;
}
return true;
}
public void remove（int key）{
Node cur = root;
Node parent = null;
while （cur != null）{
if （cur.val == key）{
removeNode（cur,parent）;
break;
}else if（cur.val < key）{
parent = cur;
cur = cur.right;
}else{
parent = cur;
cur = cur.left;
}
}
}
//cur代表要删除的节点
public void removeNode（Node cur,Node parent）{
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 = cur.left;
}
}else{//cur的左和右都不为空的情况
//找到cur的右子树的最小值然后进行替换
Node targetParent = cur;
Node target = cur.right;
while （target.left != null）{
targetParent = target;
target = target.left;
}
cur.val = target.val;
if （target == targetParent.left）{
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
public void inOrder（Node root）{
if（root == null）return;
inOrder（root.left）;
System.out.print（root.val + " "）;
inOrder（root.right）;
}
public static void main（String[] args） {
int[] arr = {2,45,19,12,3,8};
BinarySearchTree binarySearchTree = new BinarySearchTree（）;
for （int i = 0; i < arr.length; i++） {
binarySearchTree.insert（arr[i]）;
}
binarySearchTree.inOrder（binarySearchTree.root）;
System.out.println（）;
System.out.println（"插入重复的数"）;
System.out.println（binarySearchTree.insert（2））;
System.out.println（"删除数据"）;
binarySearchTree.remove（2）;
binarySearchTree.inOrder（binarySearchTree.root）;
}
}
如需转载，请注明文章出处和来源网址：http://www.divcss5.com/html/h65233.shtml
