# 数据结构
# 数据结构分类
# 按逻辑结构分类
- 集合(无逻辑关系)
- 线性结构(线性表)
- 一维数组
- 队列
- 栈
- 非线性结构
- 树
- 图
- 多维数组
# 按存储结构分类
- 顺序存储结构
class Node {
let data;
let left;
let right;
}
1
2
3
4
5
2
3
4
5
- 链式存储结构
class linkNode{
let data;
let next;
}
1
2
3
4
2
3
4
- 索引存储结构
- 散列存储结构
# 线性表
线性表是具有相同数据类型的n个数据元素的有限序列
- 物理结构为顺序表和链表
# 特点
- 表中元素个数有限
- 表中元素具有逻辑上的顺序性，在序列中各个元素排列有其先后次序
- 表中元素都是数据元素，每个元素都是单个元素
- 表中元素的数据类型都相同，意味着每个元素占有相同大小的存储空间
- 表中元素具有抽象性
- 线性表是一种逻辑结构 ，表示元素之间一对一相邻的关系
# 栈
- 只允许在一端进行插入或删除操作的线性表
- 先进后出
# 队列
只允许在表的一端进行插入，表的另一端进行删除操作的线性表
先进先出
# 树
树是由若干个有限节点组成的一个具有层次关系的集合
# 基本术语
度：树中一个结点的子结点的个数称为该结点的度
- 树中最大度数称为树的度
- 分支结点：度>0
- 叶子结点：度=0
结点的层次：根节点为第一层 依次向下增加
结点的高度：最底层结点高度为1 依次向上增加
结点的深度：根节点深度为1 依次向下增加
树的高度(深度)是树种结点的最大层数
路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，不包括边（因为树中的分支是有向的，即从双亲结点指向孩子结点，所以路径一定是自上而下的）
路径长度：路径上所经历的边的个数
森林：m棵互不相交的树的集合
# 树的性质
- 一棵树中每两个点之间有且只有一条路
- 一棵具有N个点的树有N-1条边
- 树中的结点数等于所有结点的度数+1
- 度为m的树中第i层上至多有m^(i-1)个结点
- 高度为h的m叉树至多有(m^h - 1)/(m-1)个结点
# 树的遍历
按照某种规则，不重复地访问某种树的所有节点
- 先序遍历(深度优先)
- 中序遍历(深度优先)
- 后序遍历(深度优先)
- 层次遍历(广度优先)
# 树的衍生
无序树：树中任意结点的子结点之间没有顺序关系，这种树称为无序树，也称为自由树
有序树：树中任意结点的子结点之间有顺序关系
二叉树：每个节点最多含有两个子树的树称为二叉树
完全二叉树：除了最后一层，其他各层节点数都达到最大
满二叉树：每一层上的结点数都是最大结点数
霍夫曼树：带权路径最短的二叉树，也叫最优二叉树