前言：

在《数据结构 01》一文中，说到了数组、链表、栈以及队列这几种基本的线性结构，接下来就一起来看看剩下的内容。

---

欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。

---

一、树形结构

1. 什么是树形结构？
树形结构是一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构，表示的是一对多的关系。它和链表一样，也是一种动态的数据结构。

树形结构
2. 为什么要有树形结构？
其实很多现实中存在的东西就是树形结构的，最典型的就是计算机中的文件夹。文件夹与文件夹之间有层次关系，一个文件夹下可以有若干个文件或者文件夹，这就是树形结构。

3. 二分搜索树：

3.1. 二叉树：
在说二分搜索树之前先说说二叉树。二叉树是一种特殊的树形结构，特殊在：

• 每个节点最多有两棵子树。
• 子树也有左右之分。

二叉树

树也是用节点来存储元素，和链表不同的是，二叉树的节点类属性有三个，一个是泛型的e用来存储数据，一个是Node类型的left表示左节点，Node类型的right表示右节点。

class Node{
    E e;
    Node left;
    Node right;
}

二叉树具有天然的递归结构。因为二叉树的每个节点，都可以看成是子树的根节点。

3.2. 二分搜索树：
二分搜索树首先是一棵二叉树，同时具备以下特点：

• 二分搜索树每个节点的值，都大于左子树的所有节点的值。
• 二分搜索树每个节点的值，都小于右子树的所有节点的值。

• 二分搜索树的每一棵子树也都是二分搜索树。

  
  二分搜索树
  

  这棵就是二分搜索树，每一个节点的值都大于左子树所有节点的值且小于右子树的所有节点的值。所以，二分搜索树存储的元素必须有可比较性。如果存储的是引用类型的数据，那么就应该用比较器指定某个属性进行比较。

3.2.1 实现二分搜索树：

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;
    }
}

根据上面的分析，可得上述代码。一棵二分搜索树用一个内部节点类来存储元素，同时有三个属性，左孩子、右孩子以及表示存储的元素个数的size。

3.2.2 二分搜索树的操作：

• 基本操作：获取存储的元素个数以及判断是否为空

 /** 获取二分搜索树中元素的个数 */
 public int size(){
     return size;
 }
 /** 判断二分搜索树是否为空 */
 public boolean isEmpty(){
     return size == 0;
 }

这两个方法比较简单，就不多说了。

• 添加元素：

根据二分搜索树的性质，向其中添加元素，就需要从根节点开始判断添加的元素应该是在左边还是右边。假如比根节点元素更小，那就再与根节点的左孩子为根节点，再次进行判断。所以可以用递归来实现。

 /** 向二分搜索树中添加元素(改进版) */
 public void add(E e){
     root = add(root,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;
 }

给用户提供的是public的add方法，真正执行递归添加操作的是private的这个方法。从宏观上来讲，首先把root根节点传给这个方法，如果根节点为空，直接将元素添加到根节点；如果根节点不为空，且要添加的元素比该节点元素小，那么就在左边执行添加操作，更大就在右边执行添加操作，相等的话就不添加。那么从微观角度来讲，代码具体是怎么运行的呢？比如现有如下二分搜索树：

二分搜索树

现要把“16”这个元素添加到该树中。看看代码的运行过程：

递归添加元素过程
首先看上图红色文字以及红色连线。在给用户提供的add方法中，传入root(14)，e(16)，16大于14，所以再次调用add方法，传入的当前node的右节点，14的右节点就是20；传入节点20，再次判断，发现16比20小，再次调用add并且传入20的左节点；到了图三，发现传入的20的左节点是null，所以new一个节点存储16(开始看紫色文字和紫色连线)，并且把这个节点返回给图二的add方法处，并用节点20的left接收，这样新添加的节点16就成了节点20的左孩子；同时把节点20 return给图一的add方法处，并用节点14(root)的right接收，同时返回root，这样就完成了添加操作。添加完成后二分搜索树就变成：
二分搜索树

• 遍历二分搜索树(深度优先）：

/** 二分搜索树的前序遍历 */
public void preOrder(){
    preOrder(root);
}
private void preOrder(Node node){
    if (node == null)
        return;
    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}
/** 二分搜索树中序遍历(遍历出来的就是排好序的) */
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);
}
/** 二分搜索树后序遍历 */
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 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);
      }
}

这里层序遍历借助了队列来实现，相对也比较好理解。

• 删除操作：

首先来看两个简单的删除操作，即删除最小值和最大值。根据二分搜索树的性值，最小值一定是往左走的最后一个元素，最大值一定是往右走的最后一个元素。

    /** 寻找二分搜索树的最小值 */
    public E minele(){
        if (size == 0)
            throw new IllegalArgumentException("二分搜索树为空");
        return minele(root).e;
    }
    private Node minele(Node node){
        if (node.left == null)
            return node;
        return minele(node.left);
    }

    /** 寻找二分搜索树的最大值 */
    public E maxele(){
        if (size == 0)
            throw new IllegalArgumentException("二分搜索树为空");
        return maxele(root).e;
    }
    private Node maxele(Node node){
        if (node.right == null)
            return node;
        return maxele(node.right);
    }

    /** 从二分搜索树中删除最小元素，并返回该元素 */
    public E removeMin(){
        E temp = minele();//最小元素
        root = removeMin(root);//删除最小元素
        return temp;//返回最小元素
    }
    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;
    }

    /** 从二分搜索树中删除最大元素，并返回该元素 */
    public E removeMax(){
        E temp = minele();//最小元素
        root = removeMax(root);//删除最小元素
        return temp;//返回最小元素
    }
    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;
    }

这就是删除最小值和最大值的代码，逻辑还是比较简单的。接下来看看删除任意一个元素。删除任意一个元素的话，如果这个元素有左子树和右子树，首先找到这个元素右子树中的最小值，用这个值取待被删除的元素，然后用这个元素左侧和右侧都连接上原来的子树就可以了。比如现在有如下二分搜索树，要删除元素58。

二分搜索树

那么首先找到58的右子树中的最小值，即59，找到59后就把59从这个右子树中删除，同时用59取待58。就变成了这样：

二分搜索树
这样就删除完成了。下面用代码来实现一下。

/** 删除二分搜索树中的元素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);
        return node;
    }else if (e.compareTo(node.e) > 0){
        node.right = remove(node.right,e);
        return node;
    }else {
        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 = minele(node.right);
        successor.right = removeMin(node.right);
        successor.left = node.left;
        node.left = node.right = null;
        return successor;
    }
}

这段代码就对应了上面所分析的逻辑。

二、堆

1. 什么是堆？
堆其实也是一种基于树实现的数据结构。基于二叉树实现的堆叫做二叉堆。

2. 二叉堆：
上面说了基于二叉树实现的堆叫二叉堆，有如下特点：

• 二叉堆是一棵完全二叉树。
• 所有节点的父节点的值都比自己大。

我们可以使用数组来存储二叉堆，如下图。

数组存储二叉堆

左孩子的索引就等于父节点索引的两倍再加1，右孩子索引就是父节点索引的两倍再加2。

3. 堆的实现：
根据上面的分析，写出堆的基本结构。

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;//存储数据的动态数组
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        data = new Array<>();
    }
    /** 返回堆中元素个数 */
    public int size(){
        return data.getSize();
    }
    /** 判断堆是否为空 */
    public boolean isEmpty(){
        return data.isEmpty();
    }
    /** 计算指定索引节点的父节点的索引 */
    private int parent(int index){
        if (index == 0)
            throw new IllegalArgumentException("最顶层节点无父节点");
        return (index -1) / 2;
    }
    /** 计算指定索引的左孩子的索引 */
    private int leftChild(int index){
        return index * 2 + 1;
    }
    /** 计算指定索引的右孩子的索引 */
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

这里还是使用到了前一篇文章中自己实现的动态数组。接下来看看对堆的一些操作。

• 向堆中添加元素：

添加元素直接使用动态数组的addLast方法把元素添加到最后即可，但是还要看看添加后是否还满足二叉堆的性质，看看自己是不是比自己父节点更小。如果比自己父节点更大，就需要上浮，也就是自己和父节点交换位置。那么先在动态数组添加一个交换连个元素位置的方法：

/** 交换两个元素的位置 */
public void swap(int x,int y){
     if (x<0 || x>=size || y<0 || y>=size )
         throw new IllegalArgumentException("传入的索引不合法");
     E temp = data[x];
     data[x] = data[y];
     data[y] = temp;
}

接下来就可以执行添加操作：

/** 向堆中添加元素 */
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}
/** 若添加的元素比父节点元素更大，就不符合完全二叉树性质，需要上浮。
 * 所谓上浮就是该元素和父节点元素交换位置。
 */
private void siftUp(int k){
    while (k>0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
        data.swap(k,parent(k));
         k = parent(k);
    }
}

添加元素

• 删除元素：

限定只能从根节点取出元素，所以取出的元素也是最大的，因此也叫最大堆。但是删除了根节点，这棵树就变成两棵子树了，我们就把最后一个元素放到根节点的位置，让它成为根节点。但是为了满足完全二叉树的性质，就要判断这个新的根节点是否比自己的孩子更大，如果不是，就需要下沉。下沉的时候就跟它的左右孩子中较大的那个交换位置即可。

/** 查看堆中最大元素 */
    public E findMax(){
        if (data.getSize() == 0)
            throw new IllegalArgumentException("堆为空");
        return data.get(0);
    }
    /** 取出堆中最大元素 */
    public E extractMax(){
        E temp = findMax();
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return temp;
    }
    /** 下沉操作 */
    private void siftDown(int k){
        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);//左孩子索引
            //k节点的右孩子比左孩子大
            if (j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){
                j = rightChild(k);//
            }
            if (data.get(k).compareTo(data.get(j)) >= 0)
                break;
            data.swap(k,j);
            k = j;
        }
    }

在上图添加元素的基础上删除62，就变成了这样：

删除元素

• 取出堆中最大元素后放入一个新的元素：

/** 将最大元素替换成新元素 */
    public E replace(E e){
        E temp = findMax();
        data.update(0,e);
        siftDown(0);
        return temp;
    }

这个操作比较简单，直接将索引为0处的元素更新，然后再下沉即可。

• 将任意数组整理成堆的形状(heapify)：

找到最后一个非叶子节点，从它开始做下沉操作。最后一个元素的索引的父节点索引就是最后一个非叶子节点的索引。

heapify前

比如在此图中，最后一个非叶子节点是“22”，那么就是利用“62”的索引去计算“22”的索引。“22”的索引为4，那么需要做下沉操作的就是索引为4、3、2、1、0的这5个元素。上图做完下沉操作后变成：

heapify后
下面看代码实现。首先在上篇文章讲的动态数组中添加一个构造函数，即传入一个数组的构造函数。

public Array(E[] arr){
        data = (E[]) new Object[arr.length];
        for (int i=0;i<arr.length;i++){
            data[i] = arr[i];
            size = arr.length;
        }
    }

然后heapify操作也写成一个构造函数。

 /** heapify */
 public MaxHeap(E[] arr){
     data = new Array<>(arr);
     for (int i=parent(arr.length-1);i>=0;i--){
         siftDown(i);
     }
 }

这样就完成了heapify操作。

三、优先队列

1. 什么是优先队列？
前面讲到了队列，特点是先进先出，优先队列就是出队顺序跟入队顺序无关，与元素的优先级相关。计算机可以同时执行多任务，它在给这些应用分配内存时，其实就是使用优先队列，优先级高的任务优先使用内存，以保证带给用户最好的体验。

2. 优先队列的实现：
有了上面实现的最大堆，实现优先队列就非常简单了。因为最大堆的根节点就是优先级最高的元素，每次从最大堆中取出的也就是根节点。所以使用最大堆来实现优先队列，直接调用最大堆对应的方法就行了。

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> maxHeap;
    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }
    @Override
    public int getSize() {
        return maxHeap.size();
    }
    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }
    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }
    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }
    @Override
    public E getFront() {
        return maxHeap.findMax();
    }
}

其实Java也给我们提供了一个优先队列，在java.util包中有一个PriorityQueue，就是优先队列。这个PriorityQueue是一个最小堆，也就是说，每次取出是优先级最小的元素。还有就是一些方法名不同，比如入队操作是add。更多的不同请在使用过程中体会。

四、哈希表

1. 什么是哈希表？
所谓哈希表，就是将我们关心的key通过哈希函数转化成数组对应的索引，从而可以直接通过索引访问到元素。

2. 哈希函数的设计：

• 整形：

小范围的整形key可以直接当作索引。若有负数，就进行偏移。若是大整数，比如身份证号，可以进行取模(模一个素数)，所谓取模就是求余。有一个网站给出了对于指定范围内的数到底对多少取模更合适，给出该网站的网址：

https://planetmath.org/goodhashtableprimes

• 字符串：

可以自己定义一些转换规则，将字符串转成整形来处理。

• 引用类型：

依然可以通过自己指定的转换规则转换为整形来处理。

设计函数要遵循以下三个原则：

• 一致性：如果 a == b，则 hash(a) == hash(b)。
• 高效性：计算哈希函数高效简便。
• 均匀性：哈希值均匀分布。

3. Java提供的hashCode方法：
Java的Object类中有一个hashCode方法，这个方法是根据对象在内存中地址值来计算哈希值的。基本类型需要使用其对应的包装类调用，引用类型可直接调用，也可以重写该方法，根据自己定义的规则来计算哈希值。java中HashSet和HashMap集合底层使用的就是哈希表。

4. 解决哈希冲突：
所谓哈希冲突，就是通过不同的对象通过哈希函数计算出来的哈希值可能是一样的。但是我们需要使用哈希值充当数组索引，那就不能有重复的哈希值。解决办法就是，数组每个索引位置存储的不是某一个元素，而是一个链表或者是一棵红黑树。java8中就是这样解决哈希冲突的，首先是存储链表，当哈希冲突达到一定程度时，就存储红黑树。

总结：

本文主要介绍了树、堆以及优先队列。树主要说了二分搜索树，要理解二分搜索树的操作，就要理解递归。后面说的堆其实也就是一棵树，这里说的是基于二叉树实现的最大堆。而后面说的优先队列，又是基于堆来实现的。包括《数据结构01》的源码，点此即可下载。