五大算法
- 贪心算法：局部最优解法
- 分治算法：分成多个小模块，与原问题性质相同
- 动态规划：每个状态都是过去历史的一个总结
- 回溯法：发现原先选择不优时，退回重新选择
- 分支限界法：按广度优先策略搜索问题的解空间树，适合求解最优化问题
数据树
二叉树: 最多只有两个子节点
- 完全二叉树
- 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边
- 满二叉树
- 深度为 h, 有 n 个节点，且满足 n = 2^h - 1
- 平衡二叉树
- 它或者是一颗空树，或它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树
- 最优二叉树(哈夫曼树)
- 树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
- 完全二叉树
二叉查找树: 是一种特殊的二叉树，能有效地提高查找效率
- 小值在左，大值在右
- 节点 n 的所有左子树值小于 n，所有右子树值大于 n
- 遍历节点
- 前序遍历
- 根节点
- 访问左子节点，回到 1
- 访问右子节点，回到 1
- 中序遍历
- 先访问到最左的子节点
- 访问该节点的父节点
- 访问该父节点的右子节点， 回到 1
- 后序遍历
- 先访问到最左的子节点
- 访问相邻的右节点
- 访问父节点， 回到 1
- 前序遍历
DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）
- 插入与删除节点