二叉排序树
1、二叉排序树定义
二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。
实例
二叉树实例
2、二叉排序树的创建
当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的左孩子是不是空，如果是空则将要插入的值作为当前节点的左孩子，不是空则将当前节点的左孩子作为当前节点继续查找；当要插入的值比当前节点的值大时，判断当前节点的右孩子是不是空，如果是空则将要插入的值作为当前节点的右孩子，不是空则把当前节点的右孩子作为当前节点继续查找
节点定义
public static class Node {
public int value;
public Node left;
public Node right;
}
递归实现
private static Node create(Node root, int value) {
if (root == null) {
Node node = new Node();
node.value = value;
return node;
}
if (value < root.value) {
root.left = create(root.left, value);
} else if (value > root.value) {
root.right = create(root.right, value);
}
return root;
}
非递归实现
private static Node create2(Node root, int value) {
Node node = new Node();
node.value = value;
if (root == null) {
return node;
}
Node temp = root;
while (true) {
if (value < temp.value) {
if (temp.left == null) {
temp.left = node;
return root;
} else {
temp = temp.left;
}
} else if (value > temp.value) {
if (temp.right == null) {
temp.right = node;
return root;
} else {
temp = temp.right;
}
} else {
return root;
}
}
}
3、二叉排序树的遍历
使用中序遍历，遍历出来的结构刚好是一个升序排列的数列
递归写法
private static void traverseMide(StringBuilder builder, Node root) {
if (root == null) {
return;
}
traverseMide(builder, root.left);//遍历左孩子
builder.append(root.value + ",");//打印更节点
traverseMide(builder, root.right);//遍历有孩子
}
非递归写法
private static void traverseMide2(StringBuilder builder, Node root) {
Stack<Node> stack = new Stack<>();//缓存要回溯的节点
Node temp = root;
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (!stack.isEmpty()) {
temp = stack.pop();
builder.append(temp.value + ",");//打印节点
if (temp.right != null) {
temp = temp.right;
} else {
temp = null;
}
}
}
}
4、二叉排序树的搜索
搜索二叉排序树的时候，从根节点开始搜索，将根节点作为当前节点，如果当前节点的值和搜索的值相等，则搜索结束，返回成功；如果当前节点的值小于搜索值，则判断当前节点的左孩子是不是空，如果是空，则搜索的值不在树中，搜索结束返回失败，如果不为空，则将当前节点的左孩子作为当前节点，继续搜索；如果当前节点的值大于搜索值，则判断当前节点的右子树是不是空，如果是空，则搜索的值不在树中，搜索结束，返回失败，如果不为空，则将当前节点的右孩子作为当前节点，继续搜索。
private static boolean search(Node root, int value) {
if (root == null) {
return false;
}
if (root.value == value) {
return true;
} else if (value < root.value) {
return search(root.left, value);
} else {
return search(root.right, value);
}
}
5、二叉树的删除
二叉排序树的删除分为如下三种基本的情况
- 要删除的节点就是叶子节点
- 要删除的节点只有一个孩子
- 要删除的节点有两个孩子
5.1 要删除的节点就是叶子节点
直接删除节点即可
删除节点3000
节点删除之后
5.2 要删除的节点只有一个孩子
将要删除的节点的孩子节点替换当前节点即可
删除节点2500
节点删除之后
5.3 要删除的节点有两个孩子
在要删除的节点的右子树中找一个最小的值来替换掉要删除的节点，同时将这个最小的节点删除掉（也可以从左子树中找一个最大的节点）
具体情况
-
右子树没有孩子
删除节点2000，右子树没有孩子，右子树直接替代节点2000
节点2000被替代之后
-
右子树只有右孩子
删除节点2000，右孩子只有右节点，右孩子直接替代节点2000
节点2000被替代之后
-
右子树有左孩子
删减节点2000，右子树有左孩子，从右子树中找到最左的节点替换节点2000
节点2000被替代之后
算法实现：
- 先找出右子树中的值最小的节点；
- 用最小节点的值替代掉要删除的节点的地址；
- 然后子从右子树中删除这个最小节点
删除的源码
private static Node delete(Node root, int value) {
if (root == null) {
return null;
}
if (value < root.value) {
root.left = delete(root.left, value);
} else if (value > root.value) {
root.right = delete(root.right, value);
} else {
if (root.left == null && root.right == null) {//叶子节点
root = null;
} else if (root.left == null || root.right == null) {//一个节点
if (root.left == null) {
root = root.right;
} else if (root.right == null) {
root = root.left;
}
} else {//有两个节点：
//找到右边最小的节点，替换要删除的节点，然后删除最小的节点
Node temp = root.right;
while (temp.left != null) {
temp = temp.left;
}
root.value = temp.value;
root.right = delete(root.right, temp.value);
}
}
return root;
}
6、时间复杂度
二叉排序树的查找时间与二叉树的高度有关，高度越高需要的查找时间就越多。
二叉排序树的高度有两种极端的情况，一种是完全二叉树，一种是每层只有一个节点的情况，变成了一个链表。
完全二叉树
链表
当是完全二叉树的时候：这种情况下的时间复杂为O(log2N)
当每一层只有一个节点时，也就是链表的时候：这种情况下的时间复杂度为O(n)
所以二叉排序树的搜索时间复杂度在：O(log2N)O(n)之间。它的插入，删除复杂度也在O(log2N)O(n)之间
