简介

树是相似于链表的数据结构，和链表的线性构造不同的是，树是具备层次结构的非线性的数据结构。

树是由很多个节点组成的，每个节点能够指向很多个节点。

如果一个树中的每个节点都只有0，1，2个子节点的话，这颗树就被称为二叉树，如果咱们对二叉树进行肯定的排序。

比方，对于二叉树中的每个节点，如果左子树节点的元素都小于根节点，而右子树的节点的元素都大于根节点，那么这样的树被叫做二叉搜寻树（Binary Search Tree）简称BST。

明天咱们来探讨一下BST的性质和对BST的基本操作。

BST的根本性质

刚刚咱们曾经讲过BST的基本特征了，当初咱们再来总结一下：

BST中任意节点的左子树肯定要比该节点的值要小
BST中任意节点的右子树肯定要比该节点的值要大
BST中任意节点的左右子树肯定要是一个BST。

看一张图直观的感受一下BST：

BST的构建

怎么用代码来构建一个BST呢？

首先，BST是由一个一个的节点Node组成的，Node节点除了保留节点的数据之外，还须要指向左右两个子节点，这样咱们的BST齐全能够由Node连贯而成。

另外咱们还须要一个root节点来示意BST的根节点。

相应的代码如下：

public class BinarySearchTree {    //根节点    Node root;    class Node {        int data;        Node left;        Node right;        public Node(int data) {            this.data = data;            left = right = null;        }    }}

BST的搜寻

先看下BST的搜寻，如果是下面的BST，咱们想搜寻32这个节点应该是什么样的步骤呢？

先上图：

搜寻的根本步骤是：

从根节点41登程，比拟根节点和搜寻值的大小
如果搜寻值小于节点值，那么递归搜寻左侧树
如果搜寻值大于节点值，那么递归搜寻右侧树
如果节点匹配，则间接返回即可。

相应的java代码如下：

//搜寻办法，默认从根节点搜寻    public Node search(int data){        return search(root,data);    }    //递归搜寻节点    private Node search(Node node, int data)    {        // 如果节点匹配，则返回节点        if (node==null || node.data==data)            return node;        // 节点数据大于要搜寻的数据，则持续搜寻右边节点        if (node.data > data)            return search(node.left, data);        // 如果节点数据小于要搜素的数据，则持续搜寻左边节点        return search(node.right, data);    }

BST的插入

搜寻讲完了，咱们再讲BST的插入。

先看一个动画：

上的例子中，咱们向BST中插入两个节点30和55。

插入的逻辑是这样的：

从根节点登程，比拟节点数据和要插入的数据
如果要插入的数据小于节点数据，则递归左子树插入
如果要插入的数据大于节点数据，则递归右子树插入
如果根节点为空，则插入以后数据作为根节点

相应的java代码如下：

// 插入新节点，从根节点开始插入    public void insert(int data) {        root = insert(root, data);    }    //递归插入新节点    private Node insert(Node node, int data) {        //如果节点为空，则创立新的节点        if (node == null) {            node = new Node(data);            return node;        }        //节点不为空，则进行比拟，从而递归进行左侧插入或者右侧插入        if (data < node.data)            node.left = insert(node.left, data);        else if (data > node.data)            node.right = insert(node.right, data);        //返回插入后的节点        return node;    }

BST的删除

BST的删除要比插入简单一点，因为插入总是插入到叶子节点，而删除可能删除的是非叶子节点。

咱们先看一个删除叶子节点的例子：

下面的例子中，咱们删除了30和55这两个节点。

能够看到，删除叶子节点是绝对简略的，找到之后删除即可。

咱们再来看一个比较复杂的例子，比方咱们要删除65这个节点：

能够看到须要找到65这个节点的右子树中最小的那个，替换掉65这个节点即可（当然也能够找到左子树中最大的那个）。

所以删除逻辑是这样的：

从根节点开始，比拟要删除节点和根节点的大小
如果要删除节点比根节点小，则递归删除左子树
如果要删除节点比根节点大，则递归删除右子树
如果节点匹配，又有两种状况
如果是单边节点，间接返回节点的另外一边
如果是双边节点，则先找出左边最小的值，作为根节点，而后将删除最小值过后的左边的节点，作为根节点的右节点

看下代码的实现：

 // 删除新节点，从根节点开始删除    void delete(int data)    {        root = delete(root, data);    }    //递归删除节点    Node delete(Node node, int data)    {        //如果节点为空，间接返回        if (node == null)  return node;        //遍历左右两边的节点        if (data < node.data)            node.left = delete(node.left, data);        else if (data > root.data)            node.right = delete(node.right, data);        //如果节点匹配        else        {            //如果是单边节点，间接返回其上面的节点            if (node.left == null)                return node.right;            else if (node.right == null)                return node.left;            //如果是双边节点，则先找出左边最小的值，作为根节点，而后将删除最小值过后的左边的节点，作为根节点的右节点            node.data = minValue(node.right);            // 从左边删除最小的节点            node.right = delete(node.right, node.data);        }        return node;    }

这里咱们应用递归来实现的删除双边节点，大家能够考虑一下有没有其余的形式来删除呢？

本文的代码地址：

learn-algorithm

本文收录于 www.flydean.com
最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！
欢送关注我的公众号:「程序那些事」,懂技术，更懂你！