集合系列(二十二) -一文到你搞懂二叉树实现

一、介绍

在前面的文章中，我们对树这种数据结构做了一些基本介绍，今天我们继续来聊聊一种非常常用的动态查找树： 二叉查找树。

二叉查找树，英文全称：Binary Search Tree，简称：BST，它是计算机科学中最早投入实际使用的一种树形结构，特性如下：

若左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值；
它的左、右子树也分别为二叉查找树；

特性定义比较粗放，所以在树形形态结构上，有着多样，例如下图：

上图 a、b、c 三个图，都满足以上特性，也被称为二叉查找树，虽然通过中序遍历可以得到一个有效的数组：[1、2、3、4、5、6、7、8]，但是就查找效率来说，有着一定的差别，例如查询目标为8的内容，从根目录开始查询，结构如下：

a图，需要5次；
b图，需要3次；
c图，需要8次；

由此可见，不同的形状，所需查找的次数是不一样的，关于这一点，后面我们在介绍平衡二叉查找树、红黑树这种数据结构的时候，会进行详细介绍。

虽然二叉查找树，在不同的形状下，查找效率不一样，但是它是学习其他树形结构的基础，了解了二叉查找树的算法，相信再了解其他二叉树结构会轻松很多。

二、算法思路

2.1、新增

新增元素表示向二叉树中添加元素，比较简单。如果二叉树为空，默认第一个元素就是根节点，如果二叉树不为空，就以上面提到的特点为判断条件，进行左、右节点的添加。

2.3、查找

查找元素表示从根节点开始查找元素，如果根节点为空，就直接返回空值，如果不为空，通过以左子树小于父节点，右子树大于父节点的特性为依据进行判断，然后以递归方式进行查找元素，直到找到目标的元素为止。

2.2、删除

删除元素表示从二叉树中移除要删除的元素，逻辑稍微复杂一些。同样，先要判断根节点是否为空，如果为空，直接返回，如果不为空，分情况考虑。

被删除的节点，右子树为空

这种场景，只需要将被删除元素的左子树的父节点移动到被删除元素的父节点，然后将被删除元素移除即可。

被删除的节点，左子树为空

这种场景，与上面类似，只需要将被删除元素的右子树的父节点移动到被删除元素的父节点，然后将被删除元素移除即可。

被删除的节点，左、右子树不为空

这种场景，稍微复杂一点，先定位到要删除的目标元素，根据左子节点内容一定小于当前节点内容特点，找到目标元素的左子树，通过递归遍历找到目标元素的左子树的右子树，找到最末端的元素之后，进行与目标元素进行替换，最后移除最末端元素。

2.4、遍历

二叉树的遍历方式，分两类：

层次遍历，从根节点开始；
深度遍历，又分为前序、中序、后序遍历三种方式；

2.4.1、层次遍历

层次遍历，算法思路比较简单，从根节点开始，分层从左到右进行遍历元素。

2.4.2、深度遍历

深度遍历，在遍历起始位置上又分三种，分别是前序遍历、中序遍历、后序遍历，每种遍历方式输出的结果不一样。

前序遍历：从树根开始 -> 左子树 -> 右子树

中序遍历：从最末端左子树开始 -> 树根 -> 右子树

后序遍历：从最末端左子树 -> 右子树 -> 最后到树根

尽管二叉树在遍历方式上有多种，但是只要我们掌握了其中的思路原理，再去实现起来，就会轻松很多。

三、代码实践

首先创建一个实体数据结构BSTNode，内容如下：

/**
 * BST全称：Binary Search Tree
 * 二叉查找树，节点数据结构
 */
public class BSTNode<E extends Comparable<E>> {

    /**节点数据*/
    E key=null;
    /**直接父节点*/
    BSTNode<E> parent = null;
    /**当前节点的左子节点*/
    BSTNode<E> lChild = null;
    /**当前节点的右子节点*/
    BSTNode<E> rChild = null;

    /**构造方法*/
    BSTNode(E key){
        this.key = key;
    }
}

然后，创建一个二叉查找树操作类BinarySearchTree，内容如下：

/**
 * 二叉查找树 Binary Search Tree(BST)
 * 算法实现
 */
public class BinarySearchTree<E extends Comparable<E>> {

    /**定义根节点*/
    private BSTNode<E> root = null;

    /**
     * 获取二叉树根节点
     * @return
     */
    public BSTNode<E> getBoot(){
        return this.root;
    }

    /**
     * BST 查询关键字
     * 快速搜索
     * @param key
     * @return
     */
    public boolean search(E key){
        System.out.println("搜索关键字key=" + key + " ");
        if(key == null || root == null){
            return false;
        }else{
            System.out.print("搜索路径[");
            //从根节点开始查询
            if(searchBST(root,key) != null){
                //搜索到目标元素
                return true;
            }
            System.out.print("\n");
            return false;
        }

    }

    private BSTNode<E> searchBST(BSTNode<E> node, E key){
        if(node == null){
            System.out.print("],搜索失败");
            return null;
        }
        //当前搜索节点
        System.out.print(node.key + " ->");
        //判断当前节点是否为需要找到元素，通过compareTo方法进行比较，如果相等，说明已经找到
        if(node.key.compareTo(key) == 0){
            System.out.print("],搜索成功\n");
            return node;
        }else if(node.key.compareTo(key) > 0){
            //左子树查询
            //当前节点比需要查询的节点大，那么向树的左边查询
            //递归查询
            return searchBST(node.lChild,key);
        }else if(node.key.compareTo(key) < 0){
            //右子树查询
            //需要查询的节点大于当前节点大，那么向树的右边查询
            //递归查询
            return searchBST(node.rChild,key);
        }
        System.out.print("],未找到对于的关键字，搜索失败");
        return null;
    }

    public boolean insert(E key){
        System.out.println("插入关键字key=" + key + " ");
        if(key == null){
            return false;
        }
        if(root == null){
            //插入根节点
            System.out.print("插入到树根节\n");
            root = new BSTNode<E>(key);
            return true;
        }else{
            //插入的时候，需要先查找需要插入的节点，然后在其节点插入
            //从根路径向下递归遍历比较元素内容，直到找到元素插入内容位置
            return insertBST(root,key);
        }
    }

    private boolean insertBST(BSTNode<E> node, E key){
        //在原树中找到相同的内容，无需插入
        if(node.key.compareTo(key)==0){
            return false;
        }else if(node.key.compareTo(key) > 0){
            //如果要插入的节点内容小于当前节点，那么搜索当前节点左子树
            //判断左子树，是否为空，如果为空，直接插入
            if(node.lChild == null){
                //创建一个新节点，插入节点
                BSTNode<E> newNode = new BSTNode<E>(key);
                node.lChild = newNode;
                newNode.parent = node;
                return true;
            }else{
                //否则，继续向左递归判断
                return insertBST(node.lChild,key);
            }
        }else if(node.key.compareTo(key) < 0){
            //如果要插入的节点内容大于当前节点，那么搜索当前节点右子树
            //判断右子树，是否为空，如果为空，直接插入
            if(node.rChild == null){
                //创建一个新节点，插入节点
                BSTNode<E> newNode = new BSTNode<E>(key);
                node.rChild = newNode;
                newNode.parent = node;
                return true;
            }else{
                //否则，继续向右递归判断
                return insertBST(node.rChild,key);
            }
        }
        return false;
    }

    public boolean delete(E key){
        System.out.println("删除关键字key=" + key + " ");
        if(key == null || root == null){
            System.out.print("删除失败");
            return false;
        }else{

            return deleteBST(root,key);
        }
    }

    private boolean deleteBST(BSTNode<E> node,E key){
        //定位到树中需要删除的节点
        System.out.print("开始搜索目标元素[");
        BSTNode<E> nodeDel = searchBST(node,key);
        if(nodeDel == null){
            return false;
        }else{
            //树的右子节点为空，只需要重新连接它的左树
            if(nodeDel.rChild == null){
                BSTNode<E> parent = nodeDel.parent;
                //判断当前需要删除的元素是父节点左子节点还是右子节点
                if(parent.lChild != null && parent.lChild.key.compareTo(nodeDel.key) == 0){
                    //如果为左子节点，那么当前节点的左子节点挂到父亲的左子节点上
                    parent.lChild = nodeDel.lChild;
                }else{
                    //如果为右子节点，那么当前节点的左子节点挂到父亲的右子节点上
                    parent.rChild = nodeDel.lChild;
                }
                if(nodeDel.lChild != null){
                    //同时将当前元素的左子节点的父亲，设置为当前节点的父亲
                    nodeDel.lChild.parent = parent;
                }
            }else if(nodeDel.lChild == null){
                //树的左子节点为空，只需要重新连接它的右树
                BSTNode<E> parent = nodeDel.parent;
                if(parent.lChild != null && parent.lChild.key.compareTo(nodeDel.key) == 0){
                    //如果为左子节点，那么当前节点的左子节点挂到父亲的左子节点上
                    parent.lChild = nodeDel.rChild;
                }else{
                    //如果为右子节点，那么当前节点的左子节点挂到父亲的右子节点上
                    parent.rChild = nodeDel.rChild;
                }
                if(nodeDel.rChild != null){
                    //同时将当前元素的右子节点的父亲，设置为当前节点的父亲
                    nodeDel.rChild.parent = parent;
                }
            }else{
                //当前节点的左、右树都不为空
                //根据二叉树特性，左子节点内容一定小于当前节点内容，右子节点一定大于当前节点内容
                //根据这个特性，对当前节点的左子节点的右子节点进行递归遍历，找到最末端的节点的内容，用来替换即将要删除的节点
                BSTNode<E> q = nodeDel;//临时变量值
                BSTNode<E> s = nodeDel.lChild;//先找到要删除节点的左子节点

                //循环遍历左子节点下右子节点元素，直到找到最末端
                while(s != null && s.rChild != null){
                    q = s;
                    s = s.rChild;
                }
                s = (s != null) ? s:q;
                //采用内容替换和位置调整法
                //将当前要删除节点左树最大的内容，替换掉要删除节点的内容
                nodeDel.key = s.key;
                //节点调整
                if(q != nodeDel){
                    //如果当前节点的左节点，有右节点那么进行位置调整
                    //将s的左节点加入到q的右节点上
                    q.rChild = s.lChild;
                }else{
                    //要删除的节点的左子节点，没有右子节点，因为内容已经替换，直接将当前元素的左子节点的左节点移动到当前节点上
                    q.lChild = s.lChild;
                }
                if(s.lChild != null){
                    //如果s的左节点不为空，将其父亲挂在q上
                    s.lChild.parent = q;
                }
            }
            return true;
        }
    }

    /**
     * 前序遍历
     * @param node
     */
    public void frontTreeIterator(BSTNode<E> node){
        if(node != null){
            System.out.println("key:" + node.key);
            frontTreeIterator(node.lChild);//遍历当前节点左子树
            frontTreeIterator(node.rChild);//遍历当前节点右子树
        }
    }

    /**
     * 中序遍历
     * @param node
     */
    public void middleTreeIterator(BSTNode<E> node){
        if(node != null){
            middleTreeIterator(node.lChild);//遍历当前节点左子树
            System.out.println("key:" + node.key);
            middleTreeIterator(node.rChild);//遍历当前节点右子树
        }
    }


    /**
     * 后序遍历
     * @param node
     */
    public void backTreeIterator(BSTNode<E> node){
        if(node != null){
            backTreeIterator(node.lChild);//遍历当前节点左子树
            backTreeIterator(node.rChild);//遍历当前节点右子树
            System.out.println("key:" + node.key);
        }
    }
}

最后，我们来测试一下，代码内容如下：

public class BSTClient {

    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        //创建一个Integer型的数据结构
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();

        //插入节点
        System.out.println("========插入元素========");
        tree.insert(new Integer(5));
        tree.insert(new Integer(2));
        tree.insert(new Integer(7));
        tree.insert(new Integer(1));
        tree.insert(new Integer(6));
        tree.insert(new Integer(4));
        tree.insert(new Integer(8));
        tree.insert(new Integer(3));
        tree.insert(new Integer(9));
        tree.insert(new Integer(10));
        System.out.println("========中序遍历元素========");

        //中序遍历
        tree.middleTreeIterator(tree.getBoot());
        System.out.println("========查找key为9的元素========");

        //查询节点
        boolean searchResult = tree.search(9);
        System.out.println("查找结果：" + searchResult);
        System.out.println("========删除key为10的元素========");

        //删除节点
        boolean deleteResult = tree.delete(10);
        System.out.println("删除结果：" + deleteResult);
        System.out.println("========再次中序遍历元素========");

        //中序遍历
        tree.middleTreeIterator(tree.getBoot());
    }
}

输出结果：

========插入元素========
插入关键字key=5 
插入到树根节
插入关键字key=2 
插入关键字key=7 
插入关键字key=1 
插入关键字key=6 
插入关键字key=4 
插入关键字key=8 
插入关键字key=3 
插入关键字key=9 
插入关键字key=10 
========中序遍历元素========
key:1
key:2
key:3
key:4
key:5
key:6
key:7
key:8
key:9
key:10
========查找key为9的元素========
搜索关键字key=9 
搜索路径[5 ->7 ->8 ->9 ->],搜索成功
查找结果：true
========删除key为10的元素========
删除关键字key=10 
开始搜索目标元素[5 ->7 ->8 ->9 ->10 ->],搜索成功
删除结果：true
========再次中序遍历元素========
key:1
key:2
key:3
key:4
key:5
key:6
key:7
key:8
key:9