树、二叉树、二叉查找树（二叉搜索树）

1 树

1.1 定义

树
结合图看，可以比较直观地发现，树(Tree)是元素的集合，每棵树由多个节点（node）组成，用以储存元素。某些节点之间存在着一定的关系，用连线表示，连线称为边（edge）或者链接。边的上端点成为父节点，下端称为子节点。

每个节点可以有多个子节点，而该节点则是相应子节点的父节点。但是每个节点只能有一个父节点（只有一个例外，也就是根节点，它没有父节点），如图中第一棵树的 S 节点即为根节点。而没有子节点的节点则称为叶子节点或叶节点，如上图中第一棵树的 A、R、X 节点。E、X 的父节点是一个节点，所以它们被称为兄弟节点。

通过上面的观察和分析，这里给出一种相对严格的树的定义。

• 树是元素的集合
• 该集合可以为空。此时树中没有元素，称之为空树（empty tree）。
• 如果该集合不为空，那么该集合至少含有一个根节点以及 0 个或多个子树。根节点与它的子树的根节点用一个边（edge）或链接相连。
  
  

1.2 特征（三个特殊概念）

关于树，有三个比较相似，容易搞混的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义如下。

• 节点的高度 = 节点到叶子结点的最长路径（边数）
• 节点的深度 = 根节点到这个节点所经历的边的个数
• 节点的层数 = 节点的深度 + 1
• 树的高度 = 根节点的高度

单看定义有点抽象，结合图来看会比较好理解。我们可以结合生活中对高度、深度的概念来看，这样理解起来就很方便了。比如，对于高度，生活中我们往往是自下而上来度量，比如第 5 楼、第 10 楼，起点都是地面。对于树这种数据结构中的高度也是一样的类比，从最底层开始进行计数，并且计数的起点是 0。

深度这个概念在生活中则是自上而下度量的，比如形容水深，是从水平面开始度量的。对于树这种数据结构而言也是如此，从根节点开始度量，计数起点从 0 开始（有些书中是从 1 开始，应该都可以，看你怎么定义和使用了，问题不大）。

层数跟深度的计算类似，不过计数的起点是 1，也就是说跟节点位于第一层。

注：图来自于数据结构预算法之美

2 二叉树

2.1 定义

二叉树是一种特殊的数据结构，顾名思义，二叉树只有两个叉，也就是两个子节点：左子节点和右子节点。其中，左子节点是左子树的根节点，右子节点是右子树的根节点。当然，这并不是说，二叉树一定要求每个节点都必须有两个子节点，有的节点只有左子节点，而有的节点只有右子节点。

二叉树
还是老惯例，结合图看。在这个图里面，有两个比较特殊的二叉树，分别是编号 2 和 3 的这两个。其中，编号 2 的二叉树中，叶节点全都在最底层，除了叶节点之外，每个节点都于左右两个子节点，这种二叉树就叫满二叉树。而编号为 3 的二叉树中，叶子结点在最底下两层，其中，最后一层的节点都靠左排列，并且，除了最后一层，其他层的节点数都要达到最大，这种二叉树叫做完全二叉树。

2.2 二叉树的三种遍历方法

二叉树经典的遍历方法一共有三种，分别是前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

• 前序遍历（也叫先序遍历）：若二叉树为空，则空操作，否则，对于二叉树中的任意节点，先访问这个节点，然后再访问它的左子树，最后打印它的右子树。
• 中序遍历：若二叉树为空，则空操作，否则，对于二叉树中的任意节点，先访问它的左子树，然后再访问这个节点本身，最后访问它的右子树。
• 后序遍历：若二叉树为空，则空操作，否则，对于二叉树中的任意节点，先访问它的左子树，然后访问它的右子树，最后访问这个节点本身。

二叉查找树

遍历方式	遍历结果
前序遍历	S->E->B->A->C->P->O->R->X
中序遍历	A->B->C->E->O->P->R->S->X
后序遍历	A->C->B->O->R->P->E->X->S

2.3 树与二叉树的区别

• 二叉树的每个节点最多只能有两个节点，而树则无限制
• 二叉树中节点的子树分为左子树和右子树，即使某个节点只有一棵树，也必须要指明这棵树是左子树还是右子树，也就是说，二叉树是有序的
• 树不能为空，至少含有一个节点，而一棵二叉树可以为空
  
  

3 二叉查找树

3.1 定义

二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，一棵二叉搜索树（BST）是一棵二叉树，其中，每个节点的值都要大于其左子树中任意节点的值而小于右子树中任意节点的值。

3.2 基本操作

3.2.1 查找

如果要在二叉查找树中查找一个节点 X，我们可以分为一下几步。

image

1. 如果二叉查找树为空，则返回空操作，否则，执行一下操作；
2. 先取根节点，如果节点 X 等于根节点，则返回；
3. 如果节点小于根节点，则递归查找左子树；
4. 如果节点大于根节点，则递归查找右子树。

3.2.2 插入

在二叉树中插入一个节点，一般都是插入到叶节点上，所以只需从根结点开始，依次遍历比较要插入的数据和节点的大小关系。

二叉查找树有一个很重要的特性就是插入的实现难度和查找差不多。当查找的节点不存在于二叉查找树中并且结束于一条空链时，我们要做的就是将链接（边）指向一个含有被查找节点的新节点。说得有点拗口，其实可以细分为以下几步。

image

1. 如果树是空的，则直接将新节点插入，否则，执行下面步骤。
2. 要插入的数据比根节点数据大，则到右子树中插入新数据，如果右子树为空，则将新数据直接插入到右子节点的位置；不为空，则继续遍历右子树，查找插入位置。
3. 要插入的数据比根节点数据小，则到左子树中插入数据，如果左子树为空，则直接将新数据插入到左子节点的位置；不为空，则继续遍历左子树，查找插入的位置。

3.2.3 删除

二叉树的删除相对于查找和插入要复杂一些，针对要删除节点的子节点个数的不同，一般分为三种情况来处理。

注：图来自于极客时间《数据结构与算法之美》专栏

1. 第一种情况，如果要删除的节点没有子节点，直接将父节点指向要删除节点的指针指向 null。比如途中要删除的节点 55。
2. 第二种情况，如果要删除的节点只有一个节点，即只有左子节点或右子节点，则将父节点指向要删除节点的指针指向要删除节点的子节点即可。比如途中要删除的节点
   13。
3. 第三种情况，如果要删除的节点有两个子节点，则需要先找到这个节点右子树中的最小节点或者左子树中的最大节点，将其替换到要删除的节点上。然后删除这个右子树中的最小节点或左子树中的最大节点，这样就可以利用
   1、2 两条规则来删除了。比如图中要删除的节点 18。

3.2.4 查找最大、最小节点

查找最大、最小节点比较简单，比如要查找二叉查找树的最大节点时，如果二叉查找树为空，则返回空操作，如果不为空，则判断是否只有一个节点（即只有根节点），如果是则返回根节点，否则到右子树中递归查找。同理，查找最小节点类似，只是到左子树中查找而已。

代码

废话不多说，上代码吧，结合代码看会比较清晰。

public class BinarySearchTree {
    private Node tree;

    /**
     * 查找
     * @param data
     * @return
     */
    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) p = p.left;
            else if (data > p.data) p = p.right;
            else return p;
        }
        return null; //没有找到
    }
    
    /**
     * 插入
     * @param data
     */
    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        
        Node p = tree;
        while (p != null) {
            if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else { //data < p.data
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }
    
    /**
     * 删除
     * @param data
     */
    public void delete(int data) {
        Node p = tree; //p 指向要删除的结点，初始化指向根节点
        Node pp = null; //pp 记录的是 p 的父节点
        
        while (p != null && p.data != data) {
            pp = p;
            if (data > p.data) p = p.right;
            else p = p.left;
        }
        if (p == null) return; //没有找到
        
        //要删除的节点有两个子节点
        if (p.left != null && p.right != null) {//查找右子树中最小的节点
            Node minP = p.right;
            Node minPP = p; //minPP 表示 minP 的父节点
            while (minP.left != null) {
                minPP = minP;
                minP = p.left;
            }
            p.data = minP.data; //将 minP 的数据替换到 p 中
            p = minP; //下面就变成了删除 minP 了,要结合整个删除函数来看
            pp = minPP;
        }
        
        //删除的是叶子节点或者仅有一个子节点
        Node  child; //p 的子节点
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;
        else child = null;
        
        if (pp == null) tree = child; // 删除的是根节点
        else if (pp.left == p) pp.left = child;
        else pp.right = child;
    }
    
    /**
     * 查找最小节点
     * @return
     */
    public Node findMin() {
        if (tree == null) return null;
        Node p = tree;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    
    /**
     * 查找最大节点
     * @return
     */
    public Node findMax() {
        if (tree == null) return null;
        Node p = tree;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    
    private static class Node {
        private int data;
        private Node left;
        private Node right;
        
        public Node(int data) {
            this.data = data;
        }
    }
}

---

本文主要参考来源：
算法(第 4 版)
极客时间专栏《数据结构与算法之美》
树与二叉树
纸上谈兵：树，二叉树，二叉搜索树