什么是二叉查找树
二叉查找树,英文名Binary Search Tree,又叫二叉搜索树,二叉排序树
二叉查找树是一种特殊的二叉树,它在二叉树的基础上,增加了如下规定
- 树的每个节点包含一个数值,并且数值是可以比较大小的
- 树的每个节点的值不能重复
- 对于任何一个节点,其左子节点的值小于父节点,右子节点的值大于父节点
简单来说,就是数值左小右大的二叉树
二叉查找树的特点就决定了,它是用来排序和查找用的
二叉查找树插入规则
二叉查找树的插入操作特别简单,小的往左插,大的往右插,已存在的不插就行了
- 如果树为空,则直接将插入的值作为根节点
- 如果树不为空,则将插入值和根节点大小做比较,相等则不插入,小于根节点则插入左子树,大于根节点则插入右子树,如果不存在子树,则直接以当前值作为子树根节点
- 对于子树,采用和根节点一样的策略,递归寻找插入位置
二叉查找树删除规则
二叉查找树的删除操作,则要讲究一点技巧了
因为树中间的枝节点被删除后,会留下一个空洞,一定要想办法补上空位才行
我们的做法是,将被删除位置的右子节点移上来填充空位,因为右子节点的值是大于父节点的,移上来仍然可以保持左小右大的特征
右子节点移上来之后,右子节点的位置就会变成空位了,此时我们只要再按上面的方式进行递归,把右子节点的右子节点再移上来,直到没有右子节点为止
完整的删除规则如下
- 首先,得对二叉查找树进行遍历,找到要删除的节点
- 如果被删节点正好是根节点,则直接将根节点指针置空,删除结束
- 如果被删节点无子树,则直接将其从父节点移除,删除结束
- 如果被删节点只有一颗子树,则将被删节点父节点的指针,直接指向该子树的根节点
- 如果被删节点有两颗子树,则将右子树根节点的值移动到被删节点上,再以同样的方式,递归删除右子树根节点
具体流程如下图所示,红色代表待删除节点,黑色表示已被替换的节点
代码实现
二叉查找树的基本功能包括:插入、移除、遍历、查找最大值、查找最小值
public class BinaryNode{ T value; BinaryNode left; BinaryNode right; public int getChildCount() { if (left == null && right == null) return 0; if (left != null && right != null) return 2; return 1; } @Override public String toString() { return String.valueOf(value); } }
import java.util.LinkedList; import java.util.List; public class BinarySearchTree{ BinaryNode root; public boolean Empty() { return root == null; } public void Clear() { root = null; } //插入数据 public void Insert(T value) { //树为空,直接创建根节点 if (root == null) { BinaryNode node = new BinaryNode(); node.value = value; root = node; return; } //递归遍历所有节点,寻找插入位置 Insert(root, value); } //递归遍历所有节点,寻找插入位置 protected void Insert(BinaryNode node, T value) { //值等于当前节点,已存在,直接结束 if (value.compareTo(node.value) == 0) return; //值小于当前节点,插入到左子树 if (value.compareTo(node.value) < 0) { if (node.left == null) { BinaryNode newNode = new BinaryNode(); newNode.value = value; node.left = newNode; return; } Insert(node.left, value); } //值大于当前节点,插入到右子树 if (value.compareTo(node.value) > 0) { if (node.right == null) { BinaryNode newNode = new BinaryNode(); newNode.value = value; node.right = newNode; return; } Insert(node.right, value); } } //移除数据 public void Delete(T value) { //树为空,什么都不做 if (root == null) return; //被删节点正好是根节点,直接将根节点指针置空 if (value.compareTo(root.value) == 0) { root = null; return; } //递归移除数据 FindAndDelete(value, root); } //递归移除数据 //该方法主要负责找到删除节点 protected void FindAndDelete(T value, BinaryNode parent) { //查到叶节点仍然无数据,结束 if (parent.getChildCount() == 0) return; //值在左子树上 if (parent.left != null && value.compareTo(parent.value) < 0) { //不在左子树根节点上,继续递归查找 if (value.compareTo(parent.left.value) != 0) { FindAndDelete(value, parent.left); return; } //找到要删除的节点,删除之 DeleteNode(parent.left, parent, true); return; } //值在右子树上 if (parent.right != null && value.compareTo(parent.value) > 0) { //不在右子树根节点上,继续递归查找 if (value.compareTo(parent.right.value) != 0) { FindAndDelete(value, parent.right); return; } //找到要删除的节点,删除之 DeleteNode(parent.right, parent, false); return; } } //递归移除数据 //该方法负责找到节点后,执行真正的删除操作,具体规则如下 //1. 如果被删节点无子树,则直接将其从父节点移除,删除结束 //2. 如果被删节点只有一颗子树,则将被删节点父节点的指针,直接指向该子树的根节点 //3. 如果被删节点有两颗子树,则将右子树根节点的值移动到被删节点上,再以同样的方式,递归删除右子树根节点 protected void DeleteNode(BinaryNode node, BinaryNode parent, boolean isLeft) { //无子树,直接将其从父节点移除 if (node.getChildCount() == 0) { if (isLeft) parent.left = null; else parent.right = null; return; } //只有一颗子树,将被删节点父节点的指针,直接指向该子树的根节点 if (node.getChildCount() == 1) { BinaryNode newNode = node.left != null ? node.left : node.right; if (isLeft) parent.left = newNode; else parent.right = newNode; return; } //有两颗子树,将右子树根节点的值移动到被删节点上,再以同样的方式,递归删除右子树根节点 node.value = node.right.value; DeleteNode(node.right, node, false); } //查找最小值 public T FindMin() { if (root == null) return null; return FindMin(root); } //递归查找最小值 protected T FindMin(BinaryNode node) { if (node.left == null) return node.value; return FindMin(node.left); } //查找最大值 public T FindMax() { if (root == null) return null; return FindMax(root); } //递归查找最大值 protected T FindMax(BinaryNode node) { if (node.right == null) return node.value; return FindMax(node.right); } //广度遍历,用于打印数据 public List > traverse() { List > resultList = new LinkedList(); traverse(root, resultList); return resultList; } //广度遍历,用于打印数据 protected void traverse(BinaryNode parentNode, List > resultList) { if (parentNode == null) return; resultList.add(parentNode); if (parentNode.left != null) resultList.add(parentNode.left); if (parentNode.right != null) resultList.add(parentNode.right); if (parentNode.left != null) { traverse(parentNode.left.left, resultList); traverse(parentNode.left.right, resultList); } if (parentNode.right != null) { traverse(parentNode.right.left, resultList); traverse(parentNode.right.right, resultList); } } }
import java.util.List;
@SuppressWarnings("all")
public class Demo {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.Insert(90);
bst.Insert(30);
bst.Insert(99);
bst.Insert(20);
bst.Insert(50);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);
//查找最大值和最小值
Comparable min = bst.FindMin();
Comparable max = bst.FindMax();
System.out.println("Min:" + min);
System.out.println("Max:" + max);
//删除元素
bst.Delete(30);
//按广度优先算法打印结果
List list = bst.traverse();
for (Object item : list)
System.out.print(item + " ");
}
}



