数据结构是指相互之间存在一种或多种关系的数据元素的集合和该集合重元素之间的关系组成。选择合适的数据机构可以提升对数据操作的效率。

数据结构大体可以分为 物理结构逻辑结构两种。

1. 数组

数组是最简单、最为常用的一种数据结构,是有限个相同类型的变量组成的有序集合。
int[] array = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};

2. 链表

链表中的元素称之为节点。链表分为单向链表和双向链表。

  • 单向链表

单向链表中的节点代码如下:

    public class Node {
        int data;
        Node next;
    }

data:节点的值
next:节点所指向的下一个节点

  • 双向链表

双向链表中的节点代码如下:

    public class Node {
        int data;
        Node pre;
        Node next;
    }

data:节点的值
pre:节点所指向的前一个节点
next:节点所指向的下一个节点

3. 散列表

散列表也称之为哈希表。Java中的HashMap就是典型的散列表结构。

4. 栈

栈是一种FILO(FIrst In Last Out)的线性结构。
栈的结构决定了栈中的数据 输入顺序输出顺序相反,使得栈在 历史回溯相关的场景得到很好的应用。如:浏览器中的“倒退”功能,部分编译软件中的“面包屑”功能。

5. 队列

与栈不同,队列是一种FIFO(First In First Out)的线性结构。
队列的结构决定了队列中的数据 输入顺序输出顺序完全相同,所以队列多应用于前后顺序一致的应用场景。

6. 二叉树

6.1 树

树的定义如下:
树是n(n >= 0)个节点的有限集。当n=0时,称之为空树。在任意一个非空树中,有如下特点。

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

6.2 二叉树

二叉树是树的一种特殊形式。二叉树的节点最多有两个子节点。一个称之为左子节点,另一个称之为右子节点

二叉树中有两种特殊的树,一种称为满二叉树,一种称为完全二叉树
满二叉树中所有非叶子节点都存在左右子节点,并且所有叶子结点都在同一层级。
完全二叉树中最后一个节点之前的所有节点都是齐全的。

6.3 二叉查找树

二叉树中有一种便于数据查找的特殊的二叉树,我们称之为二叉查找树。
二叉查找树在二叉树的基础上增加了以下几个条件。

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

由于二叉查找树的结构和特性,所以二叉查找树搜索节点的时间复杂度为O(logn)。

6.4 二叉树的遍历

从节点之间位置关系的角度来看,二叉树的遍历分为4种。

  • 前序遍历
  • 中序遍历
  • 后续遍历
  • 层序遍历

从更宏观的角度来看,二叉树的遍历归结为两大类。

  • 深度优先遍历(前序遍历、中序遍历、后序遍历)
  • 广度优先遍历(层序遍历)
6.4.1 深度优先遍历

下面将会用代码的形式来描述各种遍历方式。

    public static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
            this.data = data;
        }
    }
    /**
     * 创建二叉树
     *
     * @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) {
            // 递归设置TreeNode以及其子节点
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }
  1. 前序遍历
    二叉树的前序遍历,输出顺序是:根节点、左子树、右子树。
    /**
     * 前序遍历
     *
     * @param treeNode 二叉树
     */
    public static void preOrderTravel(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
	// 输出根节点的值
        System.out.println(treeNode.data);
	// 遍历左子树
        preOrderTravel(treeNode.leftChild);
	// 遍历右子树
        preOrderTravel(treeNode.rightChild);
    }
  1. 中序遍历
    二叉树的中序遍历,输出顺序是:左子树、根节点、右子树。
    /**
     * 中序遍历
     *
     * @param treeNode 二叉树
     */
    public static void inOrderTravel(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
	// 遍历左子树
        inOrderTravel(treeNode.leftChild);
	// 输出根节点的值
        System.out.println(treeNode.data);
	// 遍历右子树
        inOrderTravel(treeNode.rightChild);
    }
  1. 后续遍历
    二叉树的后序遍历,输出顺序是:左子树、右子树、根节点。
   /**
     * 后序遍历
     *
     * @param treeNode 二叉树
     */
    public static void postOrderTravel(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
	// 遍历左子树
        postOrderTravel(treeNode.leftChild);
	// 遍历右子树
        postOrderTravel(treeNode.rightChild);
	// 输出根节点的值
        System.out.println(treeNode.data);
    }
6.4.2 广度优先遍历
  1. 层序遍历
    二叉树的层序遍历,二叉树按照从根节点到叶子节点的层次关系,一层一层横向遍历各个节点。
    /**
     * 层序遍历
     *
     * @param treeNode 二叉树
     */
    public static void levOrderTravel(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
	// 把根节点添加至队列中
        queue.add(treeNode);
        while (!queue.isEmpty()) {
	    // 取队列中的头节点
            TreeNode node = queue.poll();
	    // 将节点的值放进列表中
            list.add(node.data);
            if (node.leftChild != null) {
		// 将当前节点的左子节点放入队列尾部
                queue.offer(node.leftChild);
            }

            if (node.rightChild != null) {
		// 将当前节点的右子节点放入队列尾部
                queue.offer(node.rightChild);
            }
        }

        list.forEach(System.out::println);
    }

7. 二叉堆

二叉堆本质上是一种完全二叉树,它分为两个类型。

  1. 最大堆
  2. 最小堆

7.1 最大堆和最小堆

最大堆的任何一个父节点的值都大于或等于左、右子节点的值。
最小堆的任何一个父节点的值都小于或等于左、右子节点的值。

7.2 构建二叉堆

二叉堆的构建是把一个无序的完全二叉树调整为二叉堆,本质就是让所有子节点依次“下沉”

/**
 * 二叉堆中的最小堆
 */
public class BinaryHeap {
    /**
     * 二叉堆的“下沉”调整
     * @param array 待调整的堆
     * @param parentIndex 父节点下标
     * @param length 堆的大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        int temp = array[parentIndex];
        // 左子节点的下标
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length)
        {
            // 由于二叉堆是一个完全二叉树,所有当childIndex + 1 的值没有超过堆的大小,说明存在右子节点
            // 通过比较获取子节点中最小的子节点
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex])
            {
                childIndex++;
            }
            // 当父节点的值小于子节点的最小值时,说明堆不用调整,直接跳出循环
            if (temp < array[childIndex])
            {
                break;
            }

            // 否则对父节点进行“下沉”调整
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 构建二叉堆
     * @param array  待调整的二叉堆
     */
    public static void buildBinaryHeap(int[] array)
    {
        // 从最后一个非叶子节点开始依次做“下沉”调整
        for (int i = (array.length - 2) /2; i >= 0 ; i--) {
            downAdjust(array, i, array.length);
        }
    }
}

7.3 插入节点

当二叉堆插入节点时,插入位置是完全二叉树的最后一个位置。为了使插入新节点后的二叉树满足二叉堆的特性,需要对新插入的节点进行“上浮”调整。

    /**
     * 二叉堆的“上浮”调整
     * @param array 待调整的堆
     */
    public static void upAdjust(int[] array)
    {
        // 获取最后一个叶子结点的下标
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;

        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex])
        {
            array[childIndex] = array[parentIndex];
            // 将子节点“上浮”至父节点下标位置
            childIndex = parentIndex;
            // 获取当前节点的父节点下标位置,进行循环比较
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

7.4 删除节点

当二叉堆删除节点时,删除的节点为堆顶的节点。为了维持完全二叉树的结构,所以把二叉堆中的最后一个节点放置堆顶位置。通过对堆顶节点的“下沉”调整变为满足条件的二叉堆。

    /**
     * 二叉堆的“下沉”调整
     * @param array 待调整的堆
     * @param parentIndex 父节点下标
     * @param length 堆的大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        int temp = array[parentIndex];
        // 左子节点的下标
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length)
        {
            // 由于二叉堆是一个完全二叉树,所有当childIndex + 1 的值没有超过堆的大小,说明存在右子节点
            // 通过比较获取子节点中最小的子节点
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex])
            {
                childIndex++;
            }
            // 当父节点的值小于子节点的最小值时,说明堆不用调整,直接跳出循环
            if (temp < array[childIndex])
            {
                break;
            }

            // 否则对父节点进行“下沉”调整
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

8.优先队列

优先队列与队列不同,它不再遵循FIFO原则,而是分为两种情况。

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

通过优先队列的特性可以发现,最大优先队列的出列元素与二叉堆的最大堆的堆顶元素一致最小优先队列的出列元素与二叉堆的最小堆的堆顶元素一致

/**
 * 优先队列
 */
public class PriorityQueue {
    // 初始容量设为32
    private int[] array = new int[32];

    // 二叉堆的有效大小
    private int size;

    /**
     * “入队”操作
     *
     * @param value 入队的值
     */
    public void enQueue(int value) {
        if (size >= array.length) {
            // 进行扩容
            resize();
        }
        array[size++] = value;
        // 使用二叉堆的“上浮”调整进行调整
        upAdjust();
    }

    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;

        int temp = array[childIndex];
        while (childIndex > 0 && array[parentIndex] > temp) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * “出队”操作
     */
    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("queue is empty or queue has no elements!");
        }
        // 堆顶的元素为最小的元素
        int top = array[0];
        // 将最后一个元素移动到堆顶
        array[0] = array[--size];
        array[size] = 0;
        // 使用二叉堆的“下沉”调整进行调整
        downAdjust();

        return top;
    }

    /**
     * “下沉”调整
     */
    private void downAdjust() throws Exception {
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < size - 1) {
            // 存在左子节点
            if (childIndex + 1 < size - 1 && array[childIndex + 1] < array[childIndex]) {
                // 存在右子节点,且右子节点的值小于左子节点, 取最小值
                childIndex++;
            }
            if (temp <= array[childIndex]) {
                // 父节点值小于其所有子节点的值,跳出循环
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 对数组进行扩容
     */
    private void resize() {
        this.array = Arrays.copyOf(array, 2 * array.length);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            builder.append(array[i]);
            if (i < size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    public static void main(String[] args) throws Exception {
        PriorityQueue queue = new PriorityQueue();
        queue.enQueue(1);
        queue.enQueue(3);
        queue.enQueue(2);
        queue.enQueue(6);
        queue.enQueue(5);
        queue.enQueue(7);
        queue.enQueue(8);
        queue.enQueue(9);
        queue.enQueue(10);
        queue.enQueue(0);
        System.out.println("原始array: " + queue);

        System.out.println("出队元素: " + queue.deQueue());
        System.out.println("出队一次后的array: " + queue);
        System.out.println("出队元素: " + queue.deQueue());
        System.out.println("出队两次后的array: " + queue);

    }
}

image.png


关于作者:NekoChips
本文地址:https://chenyangjie.com.cn/articles/2020/02/04/1580810021942.html
版权声明:本篇所有文章仅用于学习和技术交流,本作品采用 BY-NC-SA 4.0 许可协议,如需转载请注明出处!
许可协议:知识共享许可协议