什么是二叉排序树
二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
public class BinarySearchTree<T extends Comparable> {
private Node<T> root;
public Node<T> getRoot() {
return root;
}
public void setRoot(Node<T> root) {
this.root = root;
}
//...
}
查找
在排序树b中查找x的过程为：
若b是空树，则搜索失败，否则：
若x等于b的根节点的数据域之值，则查找成功；否则：
若x小于b的根节点的数据域之值，则搜索左子树；否则：
查找右子树。
/**
* 查找
* @param root
* @param data
* @return
*/
public Node<T> searchBST(Node root, T data) {
if (root == null) {
return root;
} else {
if (root.getValue().compareTo(data) == 0) {
return root;
} else if (root.getValue().compareTo(data) < 0) {
return searchBST(root.getLeft(), data);
} else {
return searchBST(root.getRight(), data);
}
}
}
删除
/**
* 删除二叉查找树上的某一个节点
* 1. 若是叶子节点，对此节点删除不影响整体树的结构，只需修改双亲节点即可
* 2. 若是只有左子树或只有右子树的节点
* 3. 若是左子树和右子树都在的节点
*/
public boolean deleteBST(T data) {
Node currentNode = root;//所删节点
Node parentNode = root;//所删除节点的父节点
boolean isLeft = false; //是否是父节点的左子树
//查找
while (currentNode != null && currentNode.getValue() != data) {
parentNode = currentNode;
int cResult = data.compareTo(currentNode.getValue());
if (cResult > 0) {
currentNode = currentNode.getRight();
isLeft = false;
} else if (cResult < 0) {
currentNode = currentNode.getLeft();
isLeft = true;
}
}
if (currentNode == null) {
System.out.println("delete err: not found this node");
return false;
}
//假设是叶子节点
if (currentNode.getLeft() == null && currentNode.getRight() == null) {
if (currentNode == root) {
root = null;
} else if(isLeft){
parentNode.setLeft(null);
}else{
parentNode.setRight(null);
}
return true;
}
if (currentNode.getRight() == null) {
if (currentNode == root) {
root = currentNode.getLeft();
} else if (isLeft) {
parentNode.setLeft(currentNode.getLeft());
} else {
parentNode.setRight(currentNode.getLeft());
}
} else if (currentNode.getLeft() == null) {
if (currentNode == root) {
root = currentNode.getRight();
} else if (isLeft) {
parentNode.setLeft(currentNode.getRight());
} else {
parentNode.setRight(currentNode.getRight());
}
} else if (currentNode.getLeft() != null && currentNode.getRight() != null) {
//都不为空的情况,找到前驱或后继(该节点左子树的最大数、右子树的最小树)
//1.先找到前驱或后继节点 赋值 删除
//2.移动位置
Node tmpNode = currentNode.getRight();//后继
Node tmpParentNode = tmpNode;
while (tmpNode.getLeft() != null) {
tmpParentNode = tmpNode;
tmpNode = tmpNode.getLeft();
}
if(tmpNode != currentNode.getRight()){
tmpParentNode.setLeft(tmpNode.getRight());
}else{
currentNode.setRight(tmpNode.getRight());
}
currentNode.setValue(tmpParentNode.getValue());
}
return true;
}
