一文应对面试中数据结构相关的基本概念

1.二叉树的遍历

先序遍历：根，左，右

中序遍历：左，根，右

后序遍历：左，右，根

2.hashmap 的底层实现

哈希表结构：结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构

HashMap 底层是哈希表结构（数组+链表）

3.大 O 是什么意思：

时间复杂度，又称"渐进式时间复杂度"，表示 代码执行时间 与 数据规模 之间的增长关系。

4.快速排序的原理：

快速排序是对冒泡排序的一种改进，由 C.A.R.Hoare（Charles Antony Richard Hoare，东尼·霍尔）在 1962 年提出。

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

概括来说就是双指针的思想

时间复杂度：O(nlogn)

5.数据结构中印象比较深的数据结构：

数组、链表、堆栈、队列、哈希表（字典）、树、堆（二叉树的一种）、图