数据结构篇|二分搜索树
1.简介
二分搜索树（英语：Binary Search Tree）是指一棵空树或者具有下列性质的二叉树
- 二分搜索树每个节点最多有两个孩子
- 二分搜索树每个节点只能有一个父亲
- 二分搜索树每一个节点的值大于左子树的所有节点
- 二分搜索树每一个节点的值小于右子树的所有节点
- 每一棵子树也是二分搜索树
注意：二叉树不一定是满的，一个节点也是二叉树，NULL也是一个二叉树
2.二分搜索树的设计
- BST的内部类的设计
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left;
public Node right;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
}
首先创建一个类BST它是E类型，并且二分搜索树具有比较大小的能力，所以需要继承Comparable接口。接下来设计内部类，私有的是因为我不想让外部访问到Node类，Node类内部有3个属性，其中包括E类型的元素e，还有两个指向不同方向的Node，这里叫做left和right。再设计一个构造方法当用户传入一个e时，将e设置为用户传入的e，将left和right初始化为空。
- BST属性的设计
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
BST类内部有两个属性，一个时Node类型的节点root，它代表根节点，另一个就是size，用来记录树中的元素个数。构造方法只需要在用户进行使用时将root初始化为null，size初始化为0即可。
- size()、isEmpty()方法
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
这两个方法看字面意思也能知道，第一个是获取元素个数的，所以直接将size进行返回即可，第二个是判断树是否为空，所以之间判断size是否等于0即可。
- add()方法
public void add(E e){
if (root == null){
root = new Node(e);
size++;
}else {
add(root,e);
}
}
//向以node为根的二分搜索树中插入元素e，递归算法
private void add(Node node,E e){
if (e.equals(node.e)){
return;
}else if (e.compareTo(node.e) < 0 && node.left == null){
//插入到左子树
node.left = new Node(e);
size++;
return;
}else if (e.compareTo(node.e) > 0 && node.left == null){
//插入到右子树
node.right = new Node(e);
size++;
return;
}
if (e.compareTo(node.e) < 0){
add(node.left,e);
}else { //e.compareTo(node.e) > 0
add(node.right,e);
}
}
add()方法在传入元素e时需要判断根是否为空，如果为空就将二分搜索树进行初始化，并将元素添加，当然也不要忘记维护size，如果不为空就将add方法重载，参数列表中还需要指出插入的位置node。在重载的方法中首先需要判断用户传入的e和当前节点上的e是否相同，如果相同在这里就不进行添加了，如果传入的e小于node的e并且node的左子树为空，这种情况下就直接添加元素好了，将e插入到node的左子树位置，然后维护size。如果e大于node的e并且node的右子树为空，这时将e添加到node的右子树，然后维护size。如果上面的情况都不满足时就进行递归调用重载的add()方法，如果e小于node的e就向node的左子树进行递归直到满足添加条件为止，如果不是向左子树添加就是向右子树添加了，此时只需要调用add方法，向node的右子树进行递归即可。
- add()方法的改进版
public void add(E e){
root = add(root,e);
}
//向以node为根的二分搜索树中插入元素e，递归算法
//返回插入节点后二分搜索树的根
private Node add(Node node,E e){
if (node == null){
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0){
node.left = add(node.left,e);
}else if (e.compareTo(node.e) > 0){ //e.compareTo(node.e) > 0
node.right = add(node.right,e);
}
return node;
}
改进版中在公有的add()中只需要调用重载的add()方法，在这里向根节点添加元素e。然后再看重载的add()方法，当node为空时，直接将node进行返回，这样就添加在了root的位置。如果不为空的话就进行比较，如果e比node的e小的话就向node的左子树进行递归调用然后使用node.left接住。如果e比node的e大的话，就向node的右子树进行递归，同时也使用node.right接住。最后将插入后的二分搜索树的根进行返回。
- contains()方法
public boolean contains(E e){
return contains(root,e);
}
private boolean contains(Node node,E e){
if (node == null){
return false;
}
if (e.compareTo(node.e) == 0){
return true;
}else if (e.compareTo(node.e) < 0){
return contains(node.left,e);
}else{
return contains(node.right,e);
}
}
contains方法时在树中查看是否包含某个元素，首先在contains方法中调用重载的contains方法，在root（根节点）的位置添加元素e。重载的方法中判断node是否为空，如果为空说明在整个树中没有找到元素e，此时返回false。如果e和node中的e相等就说明找到了，此时返回true。如果e小于node的e就向node的左子树递归调用contains方法，如果大于的话就向node的右子树调用contains方法。
- 二叉树的遍历方式
- 1.前序遍历
//二分搜索树的前序遍历
public void preOrder(){
preOrder(root);
}
//前序遍历以node为根的二分搜索树，递归算法
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
创建两个方法preOrder，意思为前序遍历，在有参的方法中需要传入一个Node节点，如果node为空，就进行返回。如果不为空将node中的e进行输出，然后分别向node.left和node.right进行遍历。
- 2.中序遍历
public void inOrder(){
inOrder(root);
}
private void inOrder(Node node){
if (node == null){
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
中序遍历与前序遍历类似只需要将输出语句写在向左子树遍历完之后的位置即可
- 3.后序遍历
public void postOrder(){
postOrder(root);
}
private void postOrder(Node node){
if (node == null){
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
后序遍历和前序遍历、中序遍历都是类似的，需要改变的只是输出语句的位置
- 前序遍历的非递归写法
public void preOrderNR(){
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.e);
if (cur.right != null){
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
创建方法preOrderNR，NR是Not Recursive的缩写，意思就是非递归，非递归方式在这里依赖另一个数据结构——栈，首先将栈进行初始化然后将根节点放入栈中。如果栈不是空的的话就让栈顶的元素出栈，然后进行输出。因为栈是先进后出的，所以先要将cur的右子树进行入栈操作，再将cur的左子树进行入栈操作，然后将栈顶元素出栈，此时出栈的是cur的左子树节点。然后将cur的右节点和左节点添加进栈中，然后进行出栈，先出栈的依然是左节点然后才是右节点，直到左右节点为空时，再将栈中剩下的节点进行出栈，然后再添加右节点和左节点，直到栈中为空，循环结束。
- 二叉树的层序遍历
public void levelOrder(){
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
Node cur = queue.remove();
System.out.println(cur.e);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null){
queue.add(cur.right);
}
}
}
层序遍历顾名思义，就是按照二叉树的层进行元素的遍历，这里我使用队列，首先声明Queue然后使用LinkedList进行初始化。首先将根节点进行入队操作，如果队列中不为空，将队首元素进行出队操作，然后将cur的e输出，如果cur.left和cur.right进行入队操作，然后再进行判断和输出，直至循环结束。
- 寻找二分搜索树中的最小元素
//寻找二分搜索树的最小元素
public E minimum(){
if (size == 0){
throw new IllegalArgumentException("BST is empty.");
}
return minimum(root).e;
}
private Node minimum(Node node) {
if (node.left == null){
return node;
}
return minimum(node.left);
}
寻找二分搜索树中的最小元素，一下就能想到肯定是一直向二分搜索树的左子树进行递归，直到为空时将节点进行返回即可。那么就需要创建两个方法minimum，其中一个需要传入节点node。在公有方法中首先判断size是否等于0，如果为0说明二分搜索树中不存在元素，所有抛出异常，否则从根节点进行递归调用，在递归的方法中判断如果node.left为null时说明已经找到了最小的元素，所以将node返回，否则就一直向node.left递归,.最后不要忘记将共有方法中将节点的值进行返回。
- 寻找二分搜索树中的最大元素
public E maximum(){
if (size == 0){
throw new IllegalArgumentException("BST is empty.");
}
return maximum(root).e;
}
private Node maximum(Node node) {
if (node.right == null){
return node;
}
return maximum(node.right);
}
寻找二分搜索树中的最大元素和寻找最小元素的思路是类似的，不同的是要向右子树进行递归调用然后将值进行返回，如果理解了寻找最小值，那理解寻找最大值肯定也很轻松了，这里就不进行讲解了。
- 从二分搜索树中删除最小元素
// 从二分搜索树中删除最小值所在节点, 返回最小值
public E removeMin(){
E ret = minimum();
root = removeMin(root);
return ret;
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node) {
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
在删除最小元素之前首先将最小节点的值进行保存，然后将其返回，然后从根节点进行递归调用，如果node.left为空说明已经到达了最小值，此时就将node.right进行保存，然后将node.right设置为空，然后将rightNode进行返回，当然也不要忘记对size的维护。如果node.left不为空就一直向左子树递归调用即可，因为函数需要将删除节点后的二分搜索树的根进行返回所以返回node，在公共方法中将删除后的根节点赋值给root。
- 删除二分搜索树中的最大元素
// 从二分搜索树中删除最大值所在节点
public E removeMax(){
E ret = maximum();
root = removeMax(root);
return ret;
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private Node removeMax(Node node) {
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
删除最大元素的思路和删除最小元素的思路是类似的，这里也就不再进行介绍了。
- 删除二分搜索树中的任意节点
//从二分搜索树中删除元素为e的节点
public void remove(E e){
root = remove(root,e);
}
private Node remove(Node node, E e) {
if (node == null){
return null;
}
if (e.compareTo(node.e) < 0){
node.left = remove(node.left,e);
}else if (e.compareTo(node.e) > 0){
node.right = remove(node.right,e);
}else { //e == node.e
//待删除的节点的左子树为空
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
//待删除的节点的右子树为空
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
//待删除的节点的左右子树都不为空
//找到比待删除节点大的最小节点，即待删除节点的右子树的最小节点
//用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = null;
node.right = null;
return successor;
}
return node;
}
删除任意元素首先需要将待删除的元素传入，然后递归调用一个方法，传入的参数是从root开始删除元素e。在递归的方法中需要判断传入的node是否为空，如果为空进行返回，如果不为空将传入的元素与node中的值进行比较，如果比node中的值小则向左子树进行递归，否则向右进行递归，如果两种情况都不符合就说明这就是需要删除的节点，找到待删除节点后还要判断node的左子树是否为空，如果为空将node.right进行保存，再将node.right设置为null，维护size，将保存的右子树节点进行返回，如果e比node中的值大的话就将node.left进行保存，然后将node.left设置为null，维护size，然后将保存的左子树节点进行返回。如果两个条件都不符合，就将node的右子树中的最小节点进行保存，这里叫做successor，然后将刚刚保存的元素从原位置进行删除，再让successor的right指向删除后的树的根节点，然后需要将successor的left指向node.left，此时successor已经与node的左右子树相连了，这时就可以将node进行删除，删除操作只需要将node的左右子树设置为空即可，然后将successor进行返回，最终将node进行返回。
