二叉排序树
定义
又称二叉查找树
一个空树或者满足以下性质的二叉树
- 若它的左子树不为空，则左子树上所有的结点的值均小于它的根结点的值；
- 若它的右子树不为空，则左子树上所有的结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
核心过程
查找过程
用给定值从根结点的关键字进行比较，
-
若相等，则查找成功，
-
若给定值比根结点关键字大，则从根结点的右子树中继续比较查询
-
若给定值比根结点关键字小，则从根结点的左子树中继续比较查询
查询出则返回， 查询不到则返回NULL。
插入过程
在查询给的值的时候，最后的位置结点是树的叶子结点，那么包含给定值的新结点根据大小作为叶子结点的左子结点或右子结点。
通过使用二叉排序树对动态查找表做查找和插入的操作，同时在中序遍历二叉排序树时，可以得到有关所有关键字的一个有序的序列。
删除过程
在查找过程中，如果在使用二叉排序树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉排序树。
假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：
-
结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可；
比如上图中删除结点52：
-
结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的右子树；
比如删除结点4：
-
结点 p 左右子树都有，用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作。
比如删除结点30：
结点的前驱：该结点左子树中拥有最大值的结点，亦或采用中序遍历树，在当前结点之前的结点即是当前结点的前驱。
结点的后继：该结点右子树中拥有最小值的结点，亦或采用中序遍历树，在当前结点之后的结点即是当前结点的后继。
存储结构
二叉链表
| leftchild | data | rightchild |
|---|
package tree;
public class TreeNode {
/**
* 结点上的值
*/
private int value;
/**
* 左节点
*/
private TreeNode left;
/**
* 右节点
*/
private TreeNode right;
public TreeNode() {
}
public TreeNode(TreeNode left, TreeNode right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
public TreeNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
JAVA实现
package tree;
import org.apache.commons.lang.StringUtils;
public class BinarySearchTree {
public static final StringBuilder VALUES = new StringBuilder();
public static final String SEPARATOR = "->";
public static final int SEPARATOR_LENGTH = SEPARATOR.length();
public TreeNode root;
public void insertBinarySearchTree(int key) {
TreeNode p = root;
// 新增节点的父节点
TreeNode prev = null;
// 找到新增节点的父节点
while (p != null) {
prev = p;
if (key < p.getValue()) {
p = p.getLeft();
} else if (key > p.getValue()) {
p = p.getRight();
} else {
return;
}
}
if (root == null) {
root = new TreeNode(key);
} else if (key < prev.getValue()) {
prev.setLeft(new TreeNode(key));
} else {
prev.setRight(new TreeNode(key));
}
}
public void deleteBST(int key) {
deleteBST(root, key);
}
private boolean deleteBST(TreeNode treeNode, int key) {
if (treeNode == null) {
return false;
} else {
if (key == treeNode.getValue()) {
return delete(treeNode);
} else if (key < treeNode.getValue()) {
return deleteBST(treeNode.getLeft(), key);
} else {
return deleteBST(treeNode.getRight(), key);
}
}
}
private boolean delete(TreeNode treeNode) {
TreeNode temp = null;
// 只有左子树 或者是叶子节点 将其左子树上的节点接到要删除的节点上
if (treeNode.getRight() == null) {
temp = treeNode;
treeNode = treeNode.getLeft();
}
// 只有右子树 将其左子树接到要删除的节点上
else if (treeNode.getLeft() == null) {
temp = treeNode;
treeNode = treeNode.getRight();
}
// 同时拥有左右子树 找到左子树上最大的节点(treeNode的前驱)
else {
temp = treeNode;
TreeNode s = treeNode;
// 找到要删除节点的左节点
s = s.getLeft();
// 找到左子树上最大的节点
while (s.getRight() != null) {
temp = s;
s = s.getRight();
}
// 将要删除节点左子树上最大的值取出来 更新节点（也就实现了节点的删除）
treeNode.setValue(s.getValue());
// 如果要删除节点与要删除节点的左子树上的最大值不一样，则左子树中最大节点的左节点作为 删除节点的左节点的右节点
if (temp != treeNode) {
temp.setRight(s.getLeft());
}
// temp与treeNode指向同一个结点，目前s没有右子树，直接将s的左子树作为temp的左子树
else {
temp.setLeft(s.getLeft());
}
}
return true;
}
public boolean searchBST(int key) {
TreeNode current = root;
while (current != null) {
if (key == current.getValue()) {
return true;
} else if (key < current.getValue()) {
current = current.getLeft();
} else {
current = current.getRight();
}
}
return false;
}
/**
* 中序输出
*/
public String orderPrint(TreeNode treeNode) {
String result = "";
if (treeNode != null) {
orderPrint(treeNode.getLeft());
VALUES.append(treeNode.getValue()).append(SEPARATOR);
orderPrint(treeNode.getRight());
}
if (StringUtils.isNotBlank(VALUES.toString())) {
result = VALUES.substring(0, VALUES.toString().length() - SEPARATOR_LENGTH);
}
return result;
}
public static void main(String[] args) {
BinarySearchTree binarySearchTree = init();
System.out.println("search result:" + binarySearchTree.searchBST(45));
System.out.println("inorder:" + binarySearchTree.orderPrint(binarySearchTree.root));
binarySearchTree.deleteBST(binarySearchTree.root, 45);
VALUES.delete(0, VALUES.length());
/**
* 45 27
* / \ / \
* 24 90 >>>>>> 24 90
* / \ / \ / / \
* 3 27 62 100 3 62 100
*/
System.out.println("inorder:" + binarySearchTree.orderPrint(binarySearchTree.root));
}
/**
* 构建如下的二叉树，同时是个满二叉树
* 45
* / \
* 24 90
* / \ / \
* 3 27 62 100
*/
public static BinarySearchTree init() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
int[] ints = {45, 24, 90, 3, 27, 100, 62};
for (int a : ints) {
binarySearchTree.insertBinarySearchTree(a);
}
return binarySearchTree;
}
}
