夯实数据结构和算法系列（四）---二叉搜索树

1.0 二叉树

1.1 基本概念

，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

image
(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；

(3)只有左子树——如图(c)；

(4)只有右子树——如图(d)；

(5)完全二叉树——如图(e)。

（6）满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
（7）平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法）。它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

• 二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

• 树的结点（node）：包含一个数据元素及若干指向子树的分支；
• 树的深度：树中最大的结点层
• 树的度： 树中最大的结点度。
• 结点的度：结点子树的个数

• 叶子结点：也叫终端结点，是度为 0 的结点；

  
  image

注意：树的高度和深度
高度的定义为：从结点x向下到某个叶结点最长简单路径中结点的个数,从G-L的高
度为2，从G-M-O节点高度为3，到底G节点高度为多少呢，正确答案是3
树的深度：树中最大的结点层,从根节点往下,列如上图中：B的深度为2。

1.2 二叉树的性质

• 性质1 ：在二叉树中第 i 层的结点数最多为2^(i-1)（i ≥ 1）
• 性质2 ：高度为k的二叉树其结点总数最多为2^k－1（ k ≥ 1
• 性质3 ：对任意的非空二叉树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1

1.3 满二叉树的性质

• 深度为k，且有 2^k-1 个节点
• 第i层上的节点数为 2^(i-1)

2.0 二叉搜索树

2.1 二叉搜索树的基本概念

• 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）
• 二叉搜索树是二叉树
  *二叉搜索树的每个结点的值大于其左子树所有结点的值小于其右子树所有结点的值
• 每个子树也是二分搜索树
• 存储的元素必须有可比较性

2.2 二叉搜索树中添加元素代码实现

对于二叉搜索树中添加元素的实现，可以用递归（简单一点）也可以非递归（和链表很像），接下来是用递归的方式实现向二叉搜索树中添加元素。

2.2.1 定义BST类

public class BST<E extends Comparable<E>> {

    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

2.2.2 向BST 中添加元素

// 向二分搜索树中添加新的元素e
    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.right == 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);
    }

2.2.3 改进添加操作，深入理解递归终止条件

    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)
            node.right = add(node.right, e);

        return node;
    }

2.2.4 二叉搜搜树的查询操作

 // 看二分搜索树中是否包含元素e
    public boolean contains(E e){
        return contains(root, e);
    }

    // 看以node为根的二分搜索树中是否包含元素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 // e.compareTo(node.e) > 0
            return contains(node.right, e);
    }