数据结构--队列，栈，线性表，树

数据结构是什么？

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

一，队列

特点：先进先出（FIFO: first in first out）

比如：排队买票，会有队列头，队列尾，队列头的人先买到票，先离开，队列尾的人后买票，后离开。

队列分为：普通队列，环形队列 

慕课网 慕课网

内存使用上是十分高效的，可以充分用到每个空间的

慕课网

二，栈

特点：后进先出（LIFO: last in first out）

比如；坐电梯时，后进电梯的人先出去，先进去的人后出去

慕课网

三，线性表

1. 线性表是n个数据元素的有限序列

慕课网

2. 应用场景：手机通讯录，一元多项式

3. 需要了解的名词：

前驱：指定元素的前面的元素

后继：指定元素的后面的元素

4. 链表分为：单向链表，双向链表，循环链表，静态链表

慕课网 慕课网 慕课网 慕课网

四，树

1. 树是节点的有限集合

2. 需要了解的名词：

孩子：BCD之于A

双亲：A

度：A的度为3，B的度为2，C的度为0，D的度为2

叶子（终端节点）：CEFGH

根（非终端节点）：ABD

祖先：A

子孙：BCDEFG

深度

森林：多个树组成森林

慕课网 慕课网

二叉树

1. 所有结点的度都小于等于2. 右边的树为二叉树。

慕课网

2. 二叉树的遍历

前中后是相对于二叉树的根来说的

前序遍历：先访问根，再访问左右结点。根左右

中序遍历：把根放在第2位。先访问左结点，再访问根，再访问右结点。左根右

后序遍历：将访问根的放在最后完成。先访问左结点，再访问右结点，最后访问根。左右根

慕课网

3. 树的用途

压缩软件-赫夫曼树

搜索-人机对战