学习笔记

哈希表（Hash Table）

也叫散列表，是根据关键码值（key, value）而直接进行访问的数据结构

二叉树的遍历

前序(preorder): 根 - 左 - 右

中序(inorder): 左 - 根 - 右

后序(postorder): 左 - 右 - 根

二叉搜索树

也称二叉排序树、有序二叉树、排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1、左子树上所有节点的值均小于它的根节点的值

2、右子树上所有节点的值均大于它的根节点的值

3、以此类推：左右子树也都是二叉搜索树

中序遍历： 升序排列

树的面试题一般都是递归，为什么？

1、树的定义没有循环这样的结构，而是左节点、右节点

2、重复性（自相似性）

递归思维要点

1、不要人肉进行递归（最大误区）

2、找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）

3、数学归纳法思维

堆 Heap

可以迅速找到一堆数中的最大或最小值的数据结构

根节点最大的堆叫做大顶堆或大根堆

根节点最小的堆叫做小顶堆或小根堆

二叉堆

通过完全二叉树实现

二叉堆一般都通过数组实现

假设第一个元素在数组中的索引为0的话，则父节点和子节点的位置关系如下

1、索引为i的左孩子的索引为：2 * i + 1;

2、索引为i的右孩子的索引为：2 * i + 2;

3、索引为i的父节点的索引为：floor((i - 1) / 2);

插入操作

1、新元素一律插入到堆尾

2、依次向上调整整个堆的结构（直到根即可）

删除堆顶操作

1、将堆尾元素替换到堆顶

2、依次从根向下调整堆的结构（直到堆尾）

图

1、Graph(V,E)

2、V - vertex: 点

度： 入度和出度

点与点之间：是否联通

3、E - edge: 边

• 有向和无向

• 权重（边长）

无向无权图

有向无权图

无向有权图