二叉树

1. 树结构

树(tree)是n$(n≥0)$个节点的有限集；当n=0时，称为空数；在任意一个非空树中有如下特点：

1. 有且仅有一个特定的称为根的节点。
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每个集合本身又是一个树，并称为根的子树。

上图就是一个标准的树结构。其中节点1是根节点(root)，节点5、6、7、8、9是树的末端，称为叶子节点(leaf)。节点4的上一级节点，是节点4的父节点(parent)；从节点4衍生出来的节点，是节点4的孩子节点(child)；与节点4同级的，由同一个父节点衍生出来的节点例如5、6是节点4的兄弟节点(sibling)。树的最大层级，被称为树的高度或深度，如上图的树高度就是4。

2. 二叉树

二叉树(binary tree)是树的一种特殊形式，这种树每个节点最多有2个孩子节点。二叉树节点的两个孩子节点，一个被称为左孩子(left child)，一个被称为右孩子(right child)。

2.1 满二叉树

一个二叉树的所有非叶子节点都存在左右孩子，且所有叶子节点都在用一层级上，那么这个树就是满二叉树。

简单说就是满二叉树的每一个分支都是满的。

2.2 完全二叉树

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号从1到n的节点位置相同，则这个二叉树为完全二叉树。

就是保证1到n之间的节点齐全。

2.3 二叉树在内存中的存储

二叉树属于逻辑结构，可以通过多种物理结构来表达。二叉树可以使用链式储结构和数组进行存储。

• 链式存储结构

链式存储是二叉树最直观的存储方式，一个二叉树的链表节点包含3部分：存储数据的data变量，指向左孩子的left指针，指向右孩子的right指针。

• 数组

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置。假设一个父节点的下标是parent，那么它的左孩子节点下标就是2xparent+1；右孩子节点下标是2xparent+2。

反之，如果一个左孩子节点的下标是leftChild，那么它父节点下标就是(leftChild-1)/2；右孩子rightChild计算父节点下标是(rightChild-2)/2。

假如节点5在数组中的下标是4，节点5是节点2的右孩子，故节点2的下标可以通过(4-2)/2=1计算得出。

2.4 二叉树的应用

二叉树包含许多特殊的形式，每种形式都有其作用；但最主要的应用还是在于进行查找操作和维持相对顺序这两方面

2.4.1 查找

二叉树的树形结构使它非常适合做索引。二叉查找树(binary search tree)就是一种专门用于查找操作的二叉树。二叉查找树在二叉树的基础上增加了以下几个条件：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也都是二叉查找树

上图就是一个标准的二叉查找树。对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是$O(logn)$，和树的深度是一样的。

2.4.2 维持相对顺序

二叉查找树要求左子树小于父节点，右子树大于父节点，这样保证了二叉树的有序性。因此二叉查找树还有另一个名字，二叉排序树(binary sort tree)。

2.5 二叉树的遍历

二叉树的遍历分为4种：

• 前序遍历：输出顺序根节点、左子树、右子树
• 中序遍历：输出顺序左子树，根节点、右子树
• 后序遍历：输出顺序左子树、右子树、根节点
• 层序遍历：输出顺序从左到右逐层输出

宏观角度看，遍历可归结为两大类：

1. 深度优先遍历(前、中、后序遍历)
2. 广度优先遍历(层序遍历)

2.5.1 深度优先遍历

深度优先遍历的三种遍历方式，代码实现如下：

public class binaryTree {

    /**
     * 构建二叉树
     * @param inputList 输入序列
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 二叉树前序遍历
     * @param node 二叉树节点
     */
    public static void preOrderTraversal(TreeNode node){
        if (node == null){return;}
        System.out.println(node.data);
        preOrderTraversal(node.leftChild);
        preOrderTraversal(node.rightChild);
    }

    /**
     * 二叉树中序遍历
     * @param node 二叉树节点
     */
    public static void inOrderTraversal(TreeNode node){
        if (node == null){return;}
        inOrderTraversal(node.leftChild);
        System.out.println(node.data);
        inOrderTraversal(node.rightChild);
    }

    /**
     * 后序遍历
     * @param node 二叉树节点
     */
    public static void postOrderTraversal(TreeNode node){
        if (node == null){return;}
        postOrderTraversal(node.leftChild);
        postOrderTraversal(node.rightChild);
        System.out.println(node.data);
    }

    /**
     * 二叉树节点
     */
    private static class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode(int data){
            this.data = data;
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4}));
        TreeNode treeNode = createBinaryTree(inputList);
        System.out.println("前序遍历：");
        preOrderTraversal(treeNode);
        System.out.println("中序遍历");
        inOrderTraversal(treeNode);
        System.out.println("后序遍历");
        postOrderTraversal(treeNode);
    }
}

2.5.2 广度优先遍历

广度优先的层序遍历就是按照二叉树从根节点到叶子节点的层次关系，一层一层横向遍历各个节点，需要使用到队列数据结构来实现。

/**
     * 层序遍历
     * @param root 节点
     */
public static void levelOrderTraversal(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        TreeNode node = queue.poll();
        System.out.println(node.data);
        if (node.leftChild != null){
            queue.offer(node.leftChild);
        }
        if (node.rightChild != null){
            queue.offer(node.rightChild);
        }
    }
}

3. 二叉堆

二叉堆本质上是一种完全二叉树，分为两个类型：最大堆和最小堆。

• 最大堆：任何一个父节点的值，都大于等于其子节点值。
• 最小堆：任何一个父节点的值，都小于等于其子节点值。

二叉堆的根节点叫做堆顶。由它们的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。

3.1 二叉堆的自我调整

二叉堆有以下几种操作：

1. 插入节点
2. 删除节点
3. 构建二叉堆

上述操作都基于堆的自我调整；堆的自我调整就是把一个不符合堆性质的完全二叉树，调整成一个堆。

以下以最小堆为例，看二叉堆是如何进行自我调整的。

3.1.1 插入节点

当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，例如插入一个新节点，值为0；

此时，新节点的父节点5比0大，不符合最小堆性质，于是让新节点“上浮”，和父节点交互位置。

继续用节点0和父节点3做比较，父节点3大于0，则让新节点继续“上浮”。

继续比较，最终新节点0上浮到了堆顶位置。

3.1.2 删除节点

二叉堆删除节点的过程首先删除的是处于堆顶的节点，例如下述栗子删除最小堆的堆顶节点1；

此时，为了继续维持完全二叉树的结果，会把堆最后一个节点10临时补到原本堆顶的位置。

接下来，让暂处于堆顶位置的节点10和它的左、右孩子进行比价，找到最小的一个节点，让节点10进行“下沉”；

继续继续最小节点查找和下沉操作，如上最小节点是7，则让10下沉到7的位置；

如此便完成了二叉堆的调整。

简言之：最小堆的自我调整就是小的上浮和大的下沉。

3.1.3 构建二叉堆

构建二叉堆就是把无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点依次进行多次下沉操作。

3.1.4 堆的时间复杂度

堆的插入操作是单一节点的上浮，删除操作是单一节点的下沉，这两个操作的平均交换次数都是堆高度的一半，所以时间复杂度是O(logn)；构建堆的时间复杂度是O(n)。

3.2 二叉堆的代码实现

二叉堆虽然是一个完全二叉树，但存储方式并不是链式存储，而是顺序存储，就是所有节点都存储在数组中。

二叉树使用数组结构来存储节点信息，那么节点计算方式就是：假设父节点下标为parent，那么它的左孩子下标就是2xparent+1，右孩子下标就是2xparent+2。如上栗子中，节点6包含9和10两个孩子节点，节点6在数组中的下标是3，那么根据公式就可计算出，左孩子节点9下标为7(3x2+1)，右孩子节点10下标为8(3x2+2)。

• 最小堆代码实现如下：

package tree;

import java.util.ArrayList;

/**
 * @Author: zero
 * @Description: 最小堆
 * Date: Create in 2020/4/30 8:56
 * Modified By:
 */

public class MinHeap<T extends Comparable<T>> {
    public ArrayList<T> mHeap;

    public MinHeap(){
        this.mHeap = new ArrayList<T>();
    }

    /**
     * 上浮调整
     * @param start
     */
    public void upAdjust(int start){
        int current = start;
        int father = (current - 1) / 2;
        T cData = this.mHeap.get(current);
        while (current > 0){
            int cmp = this.mHeap.get(father).compareTo(cData);
            if (cmp <= 0){
                break;
            }else {
                this.mHeap.set(current,this.mHeap.get(father));
                current = father;
                father = (father - 1) / 2;
            }
        }
        this.mHeap.set(current,cData);
    }

    /**
     * 下沉调整
     * @param start
     * @param end
     */
    public void downAdjust(int start,int end){
        int current = start;
        int left = (current * 2) + 1;
        T cData = this.mHeap.get(current);
        while (left <= end){
            int tmp = this.mHeap.get(left).compareTo(this.mHeap.get(left + 1));
            if (left < end && tmp > 0){
                left++;
            }
            tmp = cData.compareTo(this.mHeap.get(left));

            if (tmp <= 0){
                break;
            } else {
                this.mHeap.set(current,this.mHeap.get(left));
                current = left;
                left = 2 * left + 1;
            }
        }
        this.mHeap.set(current,cData);
    }

    /**
     * 插入数据到最小堆
     * @param data
     */
    public void insert(T data){
        int size = this.mHeap.size();
        this.mHeap.add(data);
        this.upAdjust(size);
    }

    /**
     * 删除数据
     * @param data
     * @return
     */
    public int remove(T data){
        if (this.mHeap.isEmpty() == true){
            return -1;
        }
        int index = this.mHeap.indexOf(data);
        if (index == 1){
            return -1;
        }

        int size = this.mHeap.size();
        this.mHeap.set(index,this.mHeap.get(size - 1));
        this.mHeap.remove(size - 1);
        if (this.mHeap.size() > 1){
            this.downAdjust(index,this.mHeap.size() - 1);
        }
        return 1;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < mHeap.size(); i++) {
            builder.append(mHeap.get(i)+" ");
        }
        return builder.toString();
    }


    public static void main(String[] args) {
        int i;
        int a[] = {8,4,3,6,9,7,1,5,2};
        MinHeap<Integer> heap = new MinHeap<>();
        System.out.printf("== 依次添加:");
        for (int j = 0; j < a.length; j++) {
            System.out.printf("%d ", a[j]);
            heap.insert(a[j]);
        }
        System.out.printf("\n== 最小堆:%s",heap);
        i = 15;
        heap.insert(i);
        System.out.printf("\n== 添加元素：%d",i);
        System.out.printf("\n== 最小堆：%s",heap);

        i=1;
        heap.remove(i);
        System.out.printf("\n== 删除元素：%d",i);
        System.out.printf("\n== 最小堆：%s",heap);
        System.out.printf("\n");
    }
}

参考

3.3 优先队列

队列的特点是先进先出(FIFO)，入队列新元素置于队尾，出队列队头元素先移出。

优先队列不在遵循先入先出原则，而是分为两种情况：

• 最大优先队列，无论入队顺序如何，都是当前最大元素优先出队
• 最小优先队列，无论入队顺序如何，都是当前最小元素优先出队

3.4 二叉堆的优先队列实现

回顾二叉堆：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆的最小元素。

因此可以用最大堆实现最大优先队列，最小堆实现最小优先队列。

• 二叉堆实现最大优先队列

package tree;

import java.util.Arrays;

/**
 * @Author: zero
 * @Description: 二叉堆实现最大优先队列
 * Date: Create in 2020/4/30 10:18
 * Modified By:
 */

public class PriorityQueue {
    private int[] array;
    private int size;
    public PriorityQueue(){
        // 初始化队列初始长度32
        this.array = new int[32];
    }

    /**
     * 入队
     * @param key 入队元素
     */
    public void enQueue(int key){
        if (size >= array.length){
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     * @throws Exception
     */
    public int deQueue() throws Exception{
        if (size <= 0){
            throw new Exception("The Queue is Empty!");
        }
        // 获取堆顶元素
        int head = array[0];
        // 让最后一个元素移动到堆顶
        array[0] = array[--size];
        // 进行下沉调整
        downAdjust();
        return head;
    }



    /**
     * 上浮调整
     */
    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = childIndex / 2;
        int temp = array[childIndex];
        while (childIndex > 0 && temp > array[parentIndex]){
            // 无需交换，单向赋值即可
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = parentIndex / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * 下沉调整
     */
    private void downAdjust() {
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size){
            // 如果有右孩子，且右孩子大于左孩子值，则定位到右孩子
            if (childIndex + 1 < size && array[childIndex+1] > array[childIndex]){
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，直接跳出
            if (temp >= array[childIndex]){
                break;
            }
            // 无需真正交换，单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 扩容
     */
    private void resize(){
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array,newSize);
    }

    public static void main(String[] args) throws Exception {
        PriorityQueue queue = new PriorityQueue();
        queue.enQueue(3);
        queue.enQueue(5);
        queue.enQueue(10);
        queue.enQueue(2);
        queue.enQueue(7);
        System.out.println("出队元素："+queue.deQueue());
        System.out.println("出队元素："+queue.deQueue());
        System.out.println("出队元素："+queue.deQueue());
    }
}

4. 小结

• 什么是树：树是n个节点的有限集，有且仅有一个特定的称为根的节点。当n>1时，其余节点可分为m个互不相交的有限集，每个集合本身又是一个树，称之为根的子树。
• 什么是二叉树：二叉树是树的一种特殊形式，每个节点最多有两个孩子节点，二叉树包括满二叉树和完全二叉树两种形式。
  • 满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，且所有叶子节点都在同一层级上。
  • 完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，所有节点与同样深度的满二叉树所有节点位置相同，则这个二叉树称为完全二叉树。
• 二叉树的遍历方式有几种
  • 按遍历节点之间的关系：前序遍历，中序遍历，后序遍历，层序遍历
  • 按宏观的角度划分：深度优先遍历和广度优先遍历
• 什么是二叉堆：二叉堆是一种特殊的满二叉树，分为最大堆和最小堆
  • 最大堆：任何一个父节点的值，都大于等于它左、右孩子节点的值
  • 最小堆：任何一个父节点的值，都小于等于它左、右孩子节点的值
• 什么是优先队列：优先队列分最大优先队列和最小优先队列
  • 最大优先队列：无论入队顺序如何，当前最大元素都会优先出队，基于最大堆实现
  • 最小优先队列：无论入队顺序如何，当前最小元素都会优先出队，基于最小堆实现