1.什么是数据结构

简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带结构的数据元素的集合。"结构"就是数据元素之间存在的关系，分为逻辑结构和存储结构。

2.数据结构分类

数据结构分为逻辑结构和物理结果
2.1 逻辑结构：指数据元素之间逻辑关系的数据结构，这里的逻辑关系是指数据元素之间的前后间关系，与数据在计算机中的存储位置无关。
2.2 物理结构：指数据的逻辑结构在计算机存储空间中存放形式称为数据的物理结构，也叫做存储结构

3.数据的逻辑结构主要分为线性结构和非线性结构。

3.1 线性结构：数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前驱结点和一个直接后继结点。常见的有数组，队列，链表，栈。

3.2 非线性结构：各个结点之间具有多个对应关系，一个结点可能有多个直接前驱结点和多个直接后继结点。常见的有多维数组，广义表，树结构和图结构等。

一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有：
1.顺序存储：存储顺序是连续的，内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。
2.链式存储：在内存中存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。
3.索引存储:除建立存储节点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。
4.散列存储：又称Hash存储，由节点的关键码值来决定节点的存储地址。

4.常用的数据结构

数组
队列
链表
栈
树
散列表
堆
图

数组，队列，链表，栈这些我们都很熟悉了。在此就不多说了。

树(Tree)

树形结构是一种层级式的数据结构，由节点和连接他们的边组成。
树的数据结构是：

每个节点有零个或多个子节点
没有父节点的节点称为根节点
每一个非根节点有且只有一个父节点
除了根节点外，每个子节点可以分为多个不相交的子树
我们平时用到最多的就是二叉树，我们以二叉树来示列，先看一下树结构：

image.png

二叉树有几下特点：
每个节点最多有两颗子树，节点的度最大为2
左子树和右子树是有顺序的，次序不能颠倒
即使某节点只有一个子树，也要区分左右子树
每个节点的值均大于其左子树上任意一个节点的值。比如，节点100大于其左子树上30,18,16
每个节点的值均小于其右子树上任意一个节点的值。比如节点100小于其右子树上的120,130,135.

堆(Heap)

堆比较特殊，是一种图的树形结构。被用于实现优先队列，优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为节点，数据就存储在这些节点中。
只要满足下面两个特点的树形结构就是堆：

堆是一个完全二叉树(所谓完全二叉树就是除了最后一层其他层的节点个数都是满的)
堆中每一个节点的值都必须大于等于或者小于其子树中每一个节点的值
下面我们看一下堆的结构：

image.png

上面其实叫大顶堆，如果每一个节点小于子树中每个节点的值，那就叫小顶堆。

5.树的高度和深度的理解

5.1高度

对于高度的理解，拿楼房来说，假如一个人提问：楼房的高度有好高?我们会下意识的从底层开始往上数，假如楼有6层，则我们会说，这个楼有6层楼那么高，则提问者就会大概知道楼有多高了。所以高度就是以从下往上对比，这是我们的习惯。而在树中，树的高度也是从下往上数的，如图所示

image.png

K节点在树的底层，是一个叶子节点，则一般定义为K的高度在最低为1，以此类推，O的高度也是1，P的高度也是1.M节点是叶子节点O的父节点，从下往上数，M节点高度为2.那么G节点的高度是多少呢？从G-L的高度为2，从G-M-O节点高度为3，到底G节点高度为多少呢？正确答案是3，请看定义：
高度的定义为:从节点向下到某个叶子节点最长简单路径中边的条数