数据结构队列，栈，链表，树，图的概要
2018-06-04 本文已影响0人
最美的谣言
（本文是根据网络视频做的笔记，更新）
数据结构用得少，经常学了忘，忘了学，这次干脆做个笔记。主要的目的是列个大纲，写出基本概念，便于以后快速记忆与查找。
一）数据结构之队列
- 什么队列
队列就是FIFO（first in first out）的数据结构 - 队列的种类
普通队列和环形队列（常用）
二）数据结构之栈
- 什么是栈
栈就是LIFO（last in first out）的数据结构
三）数据结构之线性表（链表）
-
什么是线性表
线性表是n个数据元素（可以很复杂）的有限序列。 -
线性表的分类
image.png
四）数据结构之树
- 什么是树
树是节点的有限集合 - 理解孩子，双亲，度，叶子（终端节点），根（非终端节点），有序树，无序树的概念。
image.png
什么是双亲？
双亲是指一个节点，表示父节点，注意叫法的问题。如B,C,D的双亲都是A。
什么是孩子？
对于B来说，E，F都是B的孩子。
什么是度？
指某以节点的直系孩子数，如A的度就是3，他有B，C，D三个孩子，再如B的度是2，H的度为0。
什么是叶子？
就是终端节点，表示没有孩子的节点。如C，E，F，G，H。
什么是根？
非终端节点，表示有孩子的节点。如A，B，D
什么是有序树，无序树？
这是相对的概念，比如E，F交换顺序而不影响逻辑，那么就是无序树，否则就是有序树。
什么是祖先？
节点的一直往上的节点，如对于E来说，B，A就是他的祖先。对于G来说，D，A就是他的祖先。
什么是子孙？
节点一直往下的节点。如对与A来说，下方所有的节点就是他的子孙。对于D来说，G，H是他的子孙。
什么是层？
本图可以看到，有3层。
什么是节点深度？
在第一层的节点的深度就是1，如A的深度是1
在第二层的节点的深度就是2，如B，C，D的深度是2
在第三层的节点的深度就是3，如E，F，G，H的深度是3
什么是树的深度？
节点的最大深度，就是层数，即3。
二叉树
- 什么是二叉树？
所有节点的度都小于等于2。
image.png
-
二叉树的遍历？
image.png
二叉搜索树（二叉查找树、有序二叉树、排序二叉树）
image.png
-
什么是二叉搜索树？
空树或者满足特性的树 -
二叉搜索树的特性？
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
平衡二叉树（AVL树）
image.png
-
什么是平衡二叉树？
即平衡二叉搜索树，也叫AVL树 -
AVL树的特性？
空树或满足
- 它的左右两个子树的高度差的绝对值不超过1
- 左右两个子树都是一棵平衡二叉树
红黑树
-
什么是红黑树？
红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色） -
红黑树的特性？
image.png
- Every node is either red or black
- The root is black
- Every leaf (NIL) is black
- If a node is red, then both its children are black
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes
翻译：
每个节点要么是红色，要么是黑色；
根节点永远是黑色的；
所有的叶节点都是黑色的，注意这里说叶子节点是指上图中的 NIL 节点；
每个红色节点的两个子节点一定都是黑色；
从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
（五）数据结构之图
（概念比较多，整理更新中。。。）
