最近准备面试，复习一下数据结构，顺便总结下概念，加深印象，算法什么的以后慢慢补充～

树

树(Tree)是(n>=0)个节点的有限集。当n>0,其余节点可分为m(m>0)个互不相交的有限集的集合(e.g. 有限集T1,T2…)，其中每个集合又是一棵树，称为根的__子树(SubTree)。节点拥有的子树的个数称为__节点的度(Degree)。 度为0的节点称为__叶子节点(Leaf)或__终端节点。不为0的称为__非终端节点__或__分支节点__。节点的子树的根称为该节点的__孩子(Child)，相应的，该节点称为孩子的__双亲(Parent)。

如果将树中节点的各子树堪称从左至右是有次序的(即不能互换)，则称该树为__有序树__，否则为__无序树__。森林(Forest)是m(m>0)棵互不相交的树的集合。

二叉树

__二叉树(Binary Tree)__中每个节点至多只有两颗子树(即二叉树中不存在度大于2的节点)，二叉树的子树有左右之分，其次序不能任意颠倒。

深度为k且有2^k-1个节点的二叉树称为__满二叉树__

二叉树的性质：

1. 在二叉树的第i层上至多有2ⁱ⁻¹个节点(i>1)。
2. 深度为k的二叉树至多有2ᵏ⁻¹个节点(k>=1)。
3. 对任何一棵二叉树T，如果其终端节点树为n₀,度为2的节点数为n₂,则n₀=n₂+1。
4. 具有n个节点的完全二叉树的深度为Log₂n+1。

AVL树

AVL树是一种自平衡的二叉查找树，详见: AVL树学习笔记

遍历二叉树

遍历二叉树(Traversing Binary Tree)：按照某条搜索路径巡访树中每个节点，使得每个节点均被访问一次，而且仅被访问一次。

二叉树的遍历方法总共有六种，但是一般限定为先左后右，因此只剩下三种方式，分别是__先序遍历(DLR)__，中序遍历(LDR)，后序遍历(LRD)。

具体算法：

线索二叉树

LTag包括：0 lchild域所指节点的左孩子;1 lchild域所指节点的前驱

RTag包括：0 rchild域所指节点的右孩子;1 rchild域所指节点的后继

这种节点结构构成的额二叉链表作为二叉树的存储结构，称为__线索链表__。其中指向节点前驱和后继的指针，叫做__线索__。加上线索的二叉树称为__线索二叉树__。

赫夫曼树

__赫夫曼树__又称最优二叉树，即带权路径长度最短的树。

从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径，路径上的分支数目称为__路径长度__。从树根到每个节点的路径长度之和称为__树的路径长度__。__树的带权路径长度__为树中所有叶子节点的带权路径长度之和，通常记作WPL=

赫夫曼编码

查找

静态查找表

为记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的__平均查找长度__。对于有n个记录的表，查找成功的平均查找长度为：ASL=

动态查找表

二叉排序树性质：

1. 若它的左子树不空，则左子树上所有节点的值均小于它根节点的值
2. 若它的右子树不空，则右子树上所有节点的值均大于它根节点的值
3. 它的左右子树也分别为二叉排序树

哈希表

排序方式

排序方式分为__内部排序__和__外部排序__，以下排序我会一一复习一遍并加入一些看法，篇幅可能会比较长。因此我会另开文章，专门进行讨论学习。先开个坑，慢慢写。

内部排序

1. 插入排序:直接插入排序, 二分插入排序, 希尔排序
2. 交换排序:冒泡排序, 快速排序
3. 选择排序:直接选择排序, 堆排序
4. 归并排序
5. 基数排序

插入排序

1. 直接插入排序

2. 二分插入排序

3. 希尔排序

交换排序

1. 冒泡排序

2. 快速排序

选择排序

1. 直接选择排序

2. 堆排序

归并排序

基数排序

外部排序

外部排序于我个人而言不常用，因此以后用到在补吧。

复杂度比较