二叉搜索树（Java）
二叉搜索树具有如下性质： 1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小 2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大 3）左右子树都为二叉树
二叉搜索树利用二分的思想，在构建树时，就对节点的值进行了一定的排序，缩短了查找时间
/**
* 搜索树
*/
public static class SearchBinaryTree<T> {
//根节点
TreeNode<T> root;
//比较函数
CompareInterface<T> compareInterface;
public SearchBinaryTree() {
}
public SearchBinaryTree(CompareInterface<T> compareInterface) {
this.compareInterface = compareInterface;
}
public void setCompareInterface(CompareInterface<T> compareInterface) {
this.compareInterface = compareInterface;
}
/**
* 放入一个元素
*
* @param value
*/
public void put(T value) {
if (value == null) return;
//空树，创建根节点
if (root == null) {
root = new TreeNode(value, null, null, null);
return;
}
TreeNode<T> node = root;
//遍历树，存放节点
while (node != null) {
if (compareInterface.compare(value, node.value) == 0) {//相同，不存入
return;
} else if (compareInterface.compare(value, node.value) > 0) {// value>node.value,查询右树
if (node.rightChild != null) {
node = node.rightChild;
} else {//放入当前节点的右孩子
saveChild(node, value, false);
break;
}
} else if (compareInterface.compare(value, node.value) < 0) {// value<node.value,查询左树
if (node.leftChild != null) {
node = node.leftChild;
} else {//放入当前节点的左孩子
saveChild(node, value, true);
break;
}
}
}
}
private void saveChild(TreeNode<T> node, T value, boolean isLeft) {
TreeNode<T> child = new TreeNode(value, node);
if (isLeft) {
node.leftChild = child;
} else {
node.rightChild = child;
}
}
/**
* 判读元素是否存在
*
* @param value
* @return
*/
public boolean containsValue(T value) {
TreeNode<T> node = root;
//遍历树
while (node != null) {
if (value == node.value || compareInterface.compare(value, node.value) == 0) {//相同
return true;
} else if (compareInterface.compare(value, node.value) > 0) {// value>node.value,查询右树
if (node.rightChild != null) {
node = node.rightChild;
} else {//没有找到
return false;
}
} else if (compareInterface.compare(value, node.value) < 0) {// value<node.value,查询左树
if (node.leftChild != null) {
node = node.leftChild;
} else {//没有找到
return false;
}
}
}
return false;
}
//节点
class TreeNode<T> {
T value;
//左孩子
TreeNode leftChild;
//右孩子
TreeNode rightChild;
//父节点
TreeNode parent;
public TreeNode(T value, TreeNode parent) {
this.value = value;
this.parent = parent;
}
public TreeNode(T value, TreeNode leftChild, TreeNode rightChild, TreeNode parent) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}
}
//比较函数
interface CompareInterface<T> {
//>0:a>b =0:a=b <0:a<b
int compare(T a, T b);
}
}以Int型变量为例：
SearchBinaryTree<Integer> searchBinaryTree = new SearchBinaryTree();
searchBinaryTree.setCompareInterface(new SearchBinaryTree.CompareInterface<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a - b;
}
});
searchBinaryTree.put(5);
searchBinaryTree.put(1);
searchBinaryTree.put(8);
searchBinaryTree.put(7);
searchBinaryTree.put(10);
searchBinaryTree.put(2);
searchBinaryTree.put(4);
System.out.println(searchBinaryTree.containsValue(10));构建后的存储结构如下： 5 1 8 n 2 7 10 n n n 4 n n n n
二叉搜索树的删除比较复杂，考虑4种情况 一.没有左右孩子 二.右孩子不为空，左孩子为空 三.左孩子不为空，右孩子为空 四.左孩子不为空，右孩子不为空
其中又可以细分: 第一种情况： 1.删除的是根节点，直接删除
// 1 <-删除2.删除的不是根节点，直接删除
// 2
//1 3 <-删除第二种情况: 1.删除的是根节点，将3替换1的位置
// 1 <-删除
//N 3 2.删除的不是根节点，将4替换3的位置
// 2
// 1 3 <-删除
//N N N 4第三种情况： 1.删除的是根节点，将1替换2的位置
// 2 <-删除
//1 N 2.删除的不是根节点，将3替换4的位置
// 2
// 1 4 <-删除
//N N 3 N第四种情况 1.删除的是根节点，并且右孩子的左孩子不为空，将60替换50的位置，将63替换60的位置
// 50 <-删除
// 21 66
//N N 60 78
//N.... 632.删除的是根节点，并且右孩子的左孩子为空，将66替换50的位置
// 50 <-删除
// 21 66
//N N N 783.删除的不是根节点，并且右孩子的左孩子不为空，将71替换66的位置，将74替换71的位置
// 50
// 21 66 <-删除
// N N 60 78
//N N N N 55 62 71 80
//N ............. 744.删除的不是根节点，并且右孩子的左孩子为空，将78替换66的位置
// 50
// 21 66 <-删除
// N N 60 78
//N N N N 55 62 N 80代码如下：
/**
* 删除节点
*/
public void deleteNode(TreeNode<T> node) {
//1.没有左右孩子，直接删除
if (node.rightChild == null && node.leftChild == null) {
if (node.parent == null) {//删除的是根节点
// 1 <-删除
root = null;
} else {//指针清空
// 2
//1 3 <-删除
if (node.parent.leftChild == node) {//判断是父节点的左孩子
node.parent.leftChild = null;
} else {
node.parent.rightChild = null;
}
}
//断开指向父节点
node.parent = null;
} else if (node.leftChild == null) {//2.右孩子不为空，左孩子为空
TreeNode<T> parent = node.parent;
if (parent == null) {//删除的是根节点
// 1 <-删除
//N 3
//将右孩子变为根节点
root = node.rightChild;
} else {
// 2
// 1 3 <-删除
//N N N 4
if (parent.rightChild == node) {//判断删除是父节点的右孩子
//将当前节点右孩子替换当前节点的位置
parent.rightChild = node.rightChild;
} else {//判断删除是父节点的左孩子
//将当前节点右孩子替换当前节点的位置
parent.leftChild = node.rightChild;
}
}
//右孩子父节点指向删除节点父节点
node.rightChild.parent = parent;
//断开右孩子指针
node.rightChild = null;
//断开指向父节点
node.parent = null;
} else if (node.rightChild == null) {//3.左孩子不为空，右孩子为空
TreeNode<T> parent = node.parent;
if (parent == null) {//删除的是根节点
// 2 <-删除
//1 N
//将左孩子变为根节点
root = node.leftChild;
} else {
// 2
// 1 4 <-删除
//N N 3 N
if (parent.rightChild == node) {//判断删除是父节点的右孩子
//将当前节点左孩子替换当前节点的位置
parent.rightChild = node.leftChild;
} else {//判断删除是父节点的左孩子
//将当前节点左孩子替换当前节点的位置
parent.leftChild = node.leftChild;
}
}
//左孩子父节点指向删除节点父节点
node.leftChild.parent = parent;
//断开左孩子指针
node.leftChild = null;
//断开指向父节点
node.parent = null;
} else {//4.左孩子不为空，右孩子不为空
TreeNode<T> parent = node.parent;
if (parent == null) {
// 50 <-删除
// 21 66
//N N 60 78
//获取离删除节点值最近的节点60
if (node.rightChild.leftChild != null) {
TreeNode<T> last = getLastLeftNode(node.rightChild.leftChild);
//将60替换50位置
root = last;
//断开60指针,独立出来
//60的右子树连接到60父节点的左子树
last.parent.leftChild = last.rightChild;
if (last.rightChild != null) {
last.rightChild.parent = last.parent;
}
//66父节点指向60
node.rightChild.parent = last;
//21父节点指向60
node.leftChild.parent = last;
//66左右孩子指向21和66
last.leftChild = node.leftChild;
last.rightChild = node.rightChild;
last.parent = parent;
} else {//66节点没有左孩子，直接将66替换50
root = node.rightChild;
//断开指针
node.rightChild.parent = parent;
node.leftChild.parent = node.rightChild;
node.rightChild = null;
node.leftChild = null;
}
} else {
// 50
// 21 66 <-删除
// N N 60 78
//N N N N 55 62 71 80
//N ............. 74
//获取离删除节点值最近的节点71
if (node.rightChild.leftChild != null) {
TreeNode<T> last = getLastLeftNode(node.rightChild.leftChild);
//将71替换66位置
if (parent.rightChild == node) {//如果删除节点为50的右孩子
//50的右孩子指向71
parent.rightChild = last;
} else {
parent.leftChild = last;
}
//断开71指针,独立出来
//71的右子树连接到71父节点的左子树
last.parent.leftChild = last.rightChild;
if (last.rightChild != null) {
last.rightChild.parent = last.parent;
}
//78父节点指向71
node.rightChild.parent = last;
//60父节点指向71
node.leftChild.parent = last;
//71左右孩子指向60和78
last.leftChild = node.leftChild;
last.rightChild = node.rightChild;
last.parent = parent;
} else {//78节点没有左孩子，直接将78替换66
// 50
// 21 66 <-删除
// N N 60 78
//N N N N 55 62 N 80
//将78替换66位置
if (parent.rightChild == node) {//如果删除节点为50的右孩子
//50的右孩子指向78
parent.rightChild = node.rightChild;
} else {
parent.leftChild = node.rightChild;
}
//断开指针
node.rightChild.parent = parent;
node.leftChild.parent = node.rightChild;
node.rightChild = null;
node.leftChild = null;
}
}
}
}完整代码：
/**
* 搜索树
*
* @param <T>
*/
public static class SearchBinaryTree<T> {
//根节点
TreeNode<T> root;
//比较函数
CompareInterface<T> compareInterface;
public SearchBinaryTree() {
}
public SearchBinaryTree(CompareInterface<T> compareInterface) {
this.compareInterface = compareInterface;
}
public void setCompareInterface(CompareInterface<T> compareInterface) {
this.compareInterface = compareInterface;
}
/**
* 放入一个元素
*
* @param value
*/
public void put(T value) {
if (value == null) return;
//空树，创建根节点
if (root == null) {
root = new TreeNode(value, null, null, null);
return;
}
TreeNode<T> node = root;
//遍历树，存放节点
while (node != null) {
if (compareInterface.compare(value, node.value) == 0) {//相同，不存入
return;
} else if (compareInterface.compare(value, node.value) > 0) {// value>node.value,查询右树
if (node.rightChild != null) {
node = node.rightChild;
} else {//放入当前节点的右孩子
saveChild(node, value, false);
break;
}
} else if (compareInterface.compare(value, node.value) < 0) {// value<node.value,查询左树
if (node.leftChild != null) {
node = node.leftChild;
} else {//放入当前节点的左孩子
saveChild(node, value, true);
break;
}
}
}
}
private void saveChild(TreeNode<T> node, T value, boolean isLeft) {
TreeNode<T> child = new TreeNode(value, node);
if (isLeft) {
node.leftChild = child;
} else {
node.rightChild = child;
}
}
/**
* 判读元素是否存在
*
* @param value
* @return
*/
public boolean containsValue(T value) {
return getNodeByValue(value) != null;
}
/**
* 根据value获取node
*
* @param value
* @return
*/
public TreeNode<T> getNodeByValue(T value) {
TreeNode<T> node = root;
//遍历树
while (node != null) {
if (value == node.value || compareInterface.compare(value, node.value) == 0) {//相同
return node;
} else if (compareInterface.compare(value, node.value) > 0) {// value>node.value,查询右树
if (node.rightChild != null) {
node = node.rightChild;
} else {//没有找到
return null;
}
} else if (compareInterface.compare(value, node.value) < 0) {// value<node.value,查询左树
if (node.leftChild != null) {
node = node.leftChild;
} else {//没有找到
return null;
}
}
}
return null;
}
/**
* 删除节点
*/
public void deleteNode(TreeNode<T> node) {
//1.没有左右孩子，直接删除
if (node.rightChild == null && node.leftChild == null) {
if (node.parent == null) {//删除的是根节点
// 1 <-删除
root = null;
} else {//指针清空
// 2
//1 3 <-删除
if (node.parent.leftChild == node) {//判断是父节点的左孩子
node.parent.leftChild = null;
} else {
node.parent.rightChild = null;
}
}
//断开指向父节点
node.parent = null;
} else if (node.leftChild == null) {//2.右孩子不为空，左孩子为空
TreeNode<T> parent = node.parent;
if (parent == null) {//删除的是根节点
// 1 <-删除
//N 3
//将右孩子变为根节点
root = node.rightChild;
} else {
// 2
// 1 3 <-删除
//N N N 4
if (parent.rightChild == node) {//判断删除是父节点的右孩子
//将当前节点右孩子替换当前节点的位置
parent.rightChild = node.rightChild;
} else {//判断删除是父节点的左孩子
//将当前节点右孩子替换当前节点的位置
parent.leftChild = node.rightChild;
}
}
//右孩子父节点指向删除节点父节点
node.rightChild.parent = parent;
//断开右孩子指针
node.rightChild = null;
//断开指向父节点
node.parent = null;
} else if (node.rightChild == null) {//3.左孩子不为空，右孩子为空
TreeNode<T> parent = node.parent;
if (parent == null) {//删除的是根节点
// 2 <-删除
//1 N
//将左孩子变为根节点
root = node.leftChild;
} else {
// 2
// 1 4 <-删除
//N N 3 N
if (parent.rightChild == node) {//判断删除是父节点的右孩子
//将当前节点左孩子替换当前节点的位置
parent.rightChild = node.leftChild;
} else {//判断删除是父节点的左孩子
//将当前节点左孩子替换当前节点的位置
parent.leftChild = node.leftChild;
}
}
//左孩子父节点指向删除节点父节点
node.leftChild.parent = parent;
//断开左孩子指针
node.leftChild = null;
//断开指向父节点
node.parent = null;
} else {//4.左孩子不为空，右孩子不为空
TreeNode<T> parent = node.parent;
// 50
// 21 66 <-删除
// N N 60 78
//N N N N 55 62 71 80
//N ............. 74
//获取离删除节点值最近的节点71
if (node.rightChild.leftChild != null) {
TreeNode<T> last = getLastLeftNode(node.rightChild.leftChild);
if (parent == null) {//删除的是根节点
// 50 <-删除
// 21 66
//N N 60 78
//将60替换50位置
root = last;
} else if (parent.rightChild == node) {//将71替换66位置，如果删除节点为50的右孩子
//50的右孩子指向71
parent.rightChild = last;
} else {
parent.leftChild = last;
}
//断开71指针,独立出来
//71的右子树连接到71父节点的左子树
last.parent.leftChild = last.rightChild;
if (last.rightChild != null) {
last.rightChild.parent = last.parent;
}
//78父节点指向71
node.rightChild.parent = last;
//60父节点指向71
node.leftChild.parent = last;
//71左右孩子指向60和78
last.leftChild = node.leftChild;
last.rightChild = node.rightChild;
last.parent = parent;
} else {//78节点没有左孩子，直接将78替换66
// 50
// 21 66 <-删除
// N N 60 78
//N N N N 55 62 N 80
if (parent == null) {//删除的是根节点，66节点没有左孩子，直接将66替换50
// 50 <-删除
// 21 66
//N N N 78
root = node.rightChild;
} else if (parent.rightChild == node) {//将78替换66位置 如果删除节点为50的右孩子
//50的右孩子指向78
parent.rightChild = node.rightChild;
} else {
parent.leftChild = node.rightChild;
}
//断开指针
node.rightChild.parent = parent;
node.leftChild.parent = node.rightChild;
node.rightChild = null;
node.leftChild = null;
}
}
}
private TreeNode<T> getLastLeftNode(TreeNode<T> node) {
if (node == null) return null;
TreeNode<T> head = node;
while (head.leftChild != null) {
head = head.leftChild;
}
return head;
}
//节点
class TreeNode<T> {
T value;
//左孩子
TreeNode leftChild;
//右孩子
TreeNode rightChild;
//父节点
TreeNode parent;
public TreeNode(T value, TreeNode parent) {
this.value = value;
this.parent = parent;
}
public TreeNode(T value, TreeNode leftChild, TreeNode rightChild, TreeNode parent) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}
}
//比较函数
interface CompareInterface<T> {
//>0:a>b =0:a=b <0:a<b
int compare(T a, T b);
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/8/16 上，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
