学习笔记 本周学习的数据结构主要有：哈希表、树、二叉树、二叉搜索树、堆和二叉堆、以及图

###二叉树的遍历：

1. 前序遍历：根-左-右

2. 中序遍历：左-根-右

3. 后序遍历：左-右-根

###二叉搜索树

• 左子树上所有结点的值均小于它的根结点的值

• 右子树上所有结点的值均大于它的根结点的值

• 以此类推：它的左右结点也分别式二叉查找树

• 中序遍历是一个升序排列

• 所有的操作平均时间复杂度都是O(logN),最坏时间复杂度是O(N)

• 可以迅速在一堆数中找到最大值或者最小值的数据结构
• 根节点最大的堆叫做大顶堆
• 根节点最小的堆叫做小根堆
• 常见的堆：二叉堆、斐波那契堆
• 常见操作的时间复杂度：
  • Find-max/min: O(1)
  • Delete-max/min:O(logN)
  • Insert:O(logN)/O(1)

• 通过完全二叉树(除了最底层的叶子结点之外，其余所有的结点都是满状态)实现
• 性质：
  • 是一棵完全树
  • 树中任意结点的值总是 >= 其子节点的值
• 实现细节：
  • 一般通过数组实现
  • 假设第一个元素在数组中的索引为0，则父节点和子节点的位置关系如下：
    • 索引为 i 的左孩子的索引是：2 * i+ 1
    • 索引为 i 的右孩子的索引是：2 * i + 2
    • 索引为 i 的父节点的所以是：floor((i - 1) / 2)
• 插入操作：
  • 新元素先插入到堆的尾部
  • 依次向上调整整个堆的结构，直到满足二叉堆的性质
• 删除最大元素操作：
  • 将堆尾元素替换到顶部
  • 一次从根部向下调整整个堆的结构，直到满足二叉堆的性质

• 表示方法：Grap(V, E)
• V - vertex：点
  • 度：入度和出度
  • 点与点之间：连通与否
• E - edge：边
  • 有向和无向
  • 权重
• 主要考点：
  • 广度优先遍历
  • 深度优先遍历