二叉排序树
二叉排序树定义：
（1）若它的左子树不为空，则左子树上所有节点的值要均小于根节点的值；
（2）若它的右子树不为空，则右子树上所有节点的值均要大于根节点的值；
（3）左右子树也分别是排序二叉树
比如，给定一个数组
int[] num = {4, 7, 2, 20, 6, 9, 3, 8, 21, 22, -5, -10, 10, 11, 12, 13, -1, -2, -3,};
根据上面的定义，我们可以获取一个二叉排序树，如下图所示：
image.png
按照步骤，如下图：
image.png
一个二叉树排序树，如果我们按照中序排序，那么，我们将会得到一个从小到大的排列顺序：
即：
[-10 -5 -3 -2 -1 2 3 4 6 7 8 9 10 11 12 13 20 21 22]
对于二叉排序树，我们主要是弄清楚二叉排序树的插入和删除方法：
int[] num = {4, 7, 2, 20, 6, 9, 3, 8, 21, 22, -5, -10, 10, 11, 12, 13, -1, -2, -3,};
首先是根节点，按照数组下标来插入：
1.插入4；
2.插入7，比较，在4的右边；
3.插入2，比较，在4的左边；
4.插入20，与根比较，在4右边，再与7比较，在7右边
5.插入6，与根比较，在4右边，再与7比较，在7左边
6.插入9，与根比较，在4右边，再与7比较，在7右边，与20比较，在20左边
....
依次类推
/**
* 二叉排序树插入，由于二叉排序
* @param key
*/
public void insertBST(int key) {
//插入第一个数
if (root == null) {
root = new Node(key);
} else {
Node p = root;
Node parent = null;
//判断插入的key是在p的左边还是右边，依次循环，直到p为null，停止
//这里先设置一个parent的指针，当前指针为p，先判断插入的位置
while (p != null) {
parent = p;
if (key < p.getValue()) {
p = p.getLeft();
} else {
p = p.getRight();
}
}
//设置二叉排序树的插入的节点
if (key < parent.getValue()) {
parent.setLeft(new Node(key));
} else {
parent.setRight(new Node(key));
}
}
最难的是删除节点，要分为几个步骤：
image.png
我们对着图来描述，否则比较难弄明白
1.如果删除-10，-10为叶子节点，我们需要把-5的left设置为null即可
2.如果删除-5，我们需要找到-5右子树最小值，即-3，然后-3替换-5：
（1）设置-3的left为-10
（2）设置-3的right为-1，
（3）再把-2的left位置为null，
（4）最后把父节点2的left设置为-3；
3.如果删除-3，-3为叶子节点，父节点-2设置left为null
4.删除-2，-2有左子树，没有右子树，设置父节点-1的left为-3即可
5.删除-1，-1有左子树，没有右子树，设置父节点-5的right为-2即可
6.删除2，有左子树和右子树，先找到2的右子树最小值，即3，然后3替换2：
（1）设置3的left为-5，
（2）删除节点的right为最小值节点，设置3的right为null
（3）父节点4的left修改为3
7.删除3，叶子节点，父节点2设置right为null
8.删除4，有左子树和右子树，找到右子树的最小值6，然后6替换4
（1）设置6的left为4的左子树2
（2）设置6的right为4的右子树7
（3）4的父节点为null，将root节点修改为6
9.删除7，有左右子树，找到右子树最小值8，然后8替换7
（1）设置8的left为6
（2）设置8的right为20
（3）设置9的left为null
（4）再把父节点的right节点设置为8
10.删除6，叶子节点，父节点7设置left为null
11.删除20，有左右子树，找到右子树最小值，21，然后21替换20
（1）设置21的left为20的left，即为9
（2）设置21的right为22
（3）再把父节点7的right设置为21
差不多了，我们可以把算法提炼出来了
首先，遍历，查找节点位置，当前节点为删除节点，还需要一个当前节点父节点
1.当删除节点是叶子节点的时候，分为两种情况：
（1）当叶子节点是父节点的左子树的时候，删除后，父节点的左子树为null，右子树保持原样(对应上面的例子1)
（2）当叶子节点是父节点的右子树的时候，删除后，父节点的右子树为null，左子树保持原样(对应上面的例子7)
（3）当删除节点为root时，直接设置root为null
2.当删除节点有左子树，没有右子树的时候，分为两种情况：
（1）当删除节点是父节点的左子树的时候，删除后，父节点的左子树设置为删除节点的左子树(对应上面的例子4)
（2）当删除节点是父节点的右子树的时候，删除后，父节点的右子树设置为删除节点的左子树(对应上面的例子5)
（3）当删除节点为root时，直接设置root为null
3.当删除节点有右子树，没有左子树的时候，分为两种情况：
（1）当删除节点是父节点的左子树的时候，删除后，父节点的左子树设置为删除节点的右子树（比如删除）
（2）当删除节点是父节点的右子树的时候，删除后，父节点的右子树设置为删除节点的右子树 （比如删除10， 11）
（3）当删除节点为root时，直接设置root为null
4.当删除节点有左右子树的时候，我们分为几种情况：
（1）用右子树中最小的值来替换删除节点，即右子树中最左边的节点(可能为叶子节点，也可能不是，如上面删除20后，21为最左边的节点)
（2）用找到的这个节点，设置left为删除点的left
当删除点的right等于右子树最小值点
（3.1）用找到的这个节点，设置right为删除点的right的right
当删除点的right不等于右子树最小值，即一般为叶子节点
（3.2）用找到的这个节点，设置right为删除点的right
（4）找到的这个节点的父节点不等于删除点时候，设置父节点left设置为null
（5）设置父节点的left或者right，
（6）如果删除的是root节点，纠正一下root即可
private void deleteBST(Node node, int key) {
Node p = node;
Node parent = null;
//遍历要删除的节点，找到当前删除节点和当前节点的父节点
while (p.getValue() != key) {
parent = p;
if (p.getValue() > key) {
p = p.getLeft();
} else if (p.getValue() < key) {
p = p.getRight();
}
}
//当为叶子节点的时候
if (p.getLeft() == null && p.getRight() == null) {
if (p == root) {
root = null;
} else {
//叶子节点为左子树的时候，直接把父节点左子树设置为null，相当于去掉叶子节点
//否则，叶子节点为右子树的时候，直接把父节点右指数设置为null
if (p == parent.getLeft()) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
}
//当删除节点有左子树没有右子树的时候
} else if (p.getLeft() != null && p.getRight() == null) {
if (p == root) {
root = p.getLeft();
} else {
if (p == parent.getLeft()) {
parent.setLeft(p.getLeft());
} else {
parent.setRight(p.getLeft());
}
}
//当删除节点有右子树没有左子树的时候
} else if (p.getLeft() == null && p.getRight() != null) {
if (p == root) {
root = p.getRight();
} else {
if (p == parent.getLeft()) {
parent.setLeft(p.getRight());
} else {
parent.setRight(p.getRight());
}
}
//当删除节点有左子树和右子树的时候
} else {
//我们通过获取右子树的最小值，即右子树的最左边的叶子节点来替换删除节点
//先把删除的目标节点的右子树设置为右子树最小值，然后我们循环遍历，找到右子树最左边的节点和右子树最左边节点的父节点
Node minRightNode = p.getRight();
Node tempParent = p;
while(minRightNode.getLeft() != null) {
tempParent = minRightNode;
minRightNode = minRightNode.getLeft();
}
//准备替换删除节点
//1.把删除节点的左子树设置为右子树最左边节点的left
minRightNode.setLeft(p.getLeft());
//2.如果删除节点的right就是右子树最小节点，那么先设置右节点
if (p.getRight() == minRightNode) {
minRightNode.setRight(p.getRight().getRight());
//2.当删除节点的right不是minRightNode，即这两个节点有一段距离，则设置右节点
} else {
minRightNode.setRight(p.getRight());
}
//3.如果右子树最左边的叶子节点替换删除节点后，再来修改右目标节点的父节点，设置为null
if (tempParent != p) {
tempParent.setLeft(null);
}
//4.设置父节点的左右子树
if (parent != null) {
if (p == parent.getLeft()) {
parent.setLeft(minRightNode);
} else {
parent.setRight(minRightNode);
}
} else {
root = minRightNode;
}
}
}
最后完整看看这个类
import java.util.Stack;
public class BinarySortTree {
private Node root = null;
public void printCurrentNode(Node node) {
System.out.print(node.getValue() + " ");
}
/**
* 判断二叉排序树是包含key
* @param key
* @return
*/
public boolean searchBST(int key) {
Node 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;
}
/**
* 二叉排序树插入，由于二叉排序
* @param key
*/
public void insertBST(int key) {
//插入第一个数
if (root == null) {
root = new Node(key);
} else {
Node p = root;
Node parent = null;
//判断插入的key是在p的左边还是右边，依次循环，直到p为null，停止
//这里先设置一个parent的指针，当前指针为p，先判断插入的位置
while (p != null) {
parent = p;
if (key < p.getValue()) {
p = p.getLeft();
} else {
p = p.getRight();
}
}
//设置二叉排序树的插入的节点
if (key < parent.getValue()) {
parent.setLeft(new Node(key));
} else {
parent.setRight(new Node(key));
}
}
}
/**
* 删除二叉排序树中的结点 分为三种情况：（删除结点为*p ，其父结点为*f） （1）要删除的*p结点是叶子结点，只需要修改它的双亲结点的指针为空
* （2）若*p只有左子树或者只有右子树，直接让左子树/右子树代替*p （3）若*p既有左子树，又有右子树
* 用p左子树中最大的那个值（即最右端S）代替P，删除s，重接其左子树
* */
public void deleteBST(int key) {
deleteBST(root, key);
}
private void deleteBST(Node node, int key) {
Node p = node;
Node parent = null;
//遍历要删除的节点，找到当前删除节点和当前节点的父节点
while (p.getValue() != key) {
parent = p;
if (p.getValue() > key) {
p = p.getLeft();
} else if (p.getValue() < key) {
p = p.getRight();
}
}
//当为叶子节点的时候
if (p.getLeft() == null && p.getRight() == null) {
if (p == root) {
root = null;
} else {
//叶子节点为左子树的时候，直接把父节点左子树设置为null，相当于去掉叶子节点
//否则，叶子节点为右子树的时候，直接把父节点右指数设置为null
if (p == parent.getLeft()) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
}
//当删除节点有左子树没有右子树的时候
} else if (p.getLeft() != null && p.getRight() == null) {
if (p == root) {
root = p.getLeft();
} else {
if (p == parent.getLeft()) {
parent.setLeft(p.getLeft());
} else {
parent.setRight(p.getLeft());
}
}
//当删除节点有右子树没有左子树的时候
} else if (p.getLeft() == null && p.getRight() != null) {
if (p == root) {
root = p.getRight();
} else {
if (p == parent.getLeft()) {
parent.setLeft(p.getRight());
} else {
parent.setRight(p.getRight());
}
}
//当删除节点有左子树和右子树的时候
} else {
//我们通过获取右子树的最小值，即右子树的最左边的叶子节点来替换删除节点
//先把删除的目标节点的右子树设置为右子树最小值，然后我们循环遍历，找到右子树最左边的节点和右子树最左边节点的父节点
Node minRightNode = p.getRight();
Node tempParent = p;
while(minRightNode.getLeft() != null) {
tempParent = minRightNode;
minRightNode = minRightNode.getLeft();
}
//准备替换删除节点
//1.把删除节点的左子树设置为右子树最左边节点的left
minRightNode.setLeft(p.getLeft());
//2.如果删除节点的right就是右子树最小节点，那么先设置右节点
if (p.getRight() == minRightNode) {
minRightNode.setRight(p.getRight().getRight());
//2.当删除节点的right不是minRightNode，即这两个节点有一段距离，则设置右节点
} else {
minRightNode.setRight(p.getRight());
}
//3.如果右子树最左边的叶子节点替换删除节点后，再来修改右目标节点的父节点，设置为null
if (tempParent != p) {
tempParent.setLeft(null);
}
//4.设置父节点的左右子树
if (parent != null) {
if (p == parent.getLeft()) {
parent.setLeft(minRightNode);
} else {
parent.setRight(minRightNode);
}
} else {
root = minRightNode;
}
}
}
/**
* 中序非递归遍历二叉树 获得有序序列
* */
public void inOrderTraverseLoop() {
Stack<Node> stack = new Stack<Node>();
Node node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.getLeft();
} else {
node = stack.pop();
printCurrentNode(node);
node = node.getRight();
}
}
}
}
