数据结构笔记
二叉树遍历方式：
- 前序遍历：打印 - 左 - 右
- 中序遍历：左 - 打印 - 右
- 后序遍历：左 - 右 - 打印
Pair
头文件：#include
pair<类型1,类型2>变量名；
pair<int,int> a(100,23),b;
b=make_pair(500,236);
if(a<b) cout<<a.second<<endl;//大小比较，先比较第一个再比较第二个
树
- 一个节点指向多个节点,链表是特殊化的树,二叉树是最常见的树
- 树大量使用递归,方便代码
二叉树
- 以一定的规律将值按比根节点大或小插入树中,维持每个根节点的子节点数不多于两个
堆
- 用数组实现的完全二叉树,但与二叉树不同的是,堆只维持父子节点之间的大小关系,左右不关心
- 小顶堆: 5
\(~~~~~~~~~~\)/\(~~~~\)\
$~\(10\)\(76 \)\(\\\)\(\\ \)$65$~\(15\)
内存表达:5|10|76|65|15|80|86 - 插入方式(小顶堆):先将当前数据放到最后然后依次和父节点比较,如果小于父节点,用父节点覆盖当前位置,再和父父节点比较,知道到顶部或者大于父节点
- 输出方式(小顶堆):输出顶部数据,再从数组最后取一个数从顶部开始向下比较,取左右孩子最小的节点交换位置(覆盖),依次比较
平衡二叉树
- 特点,高度平衡,查找快速,但维护耗时
- 通过设置高度,从子节点向上计算,在插入过程中通过旋转维护高度
- 插入:
- 一般情况正常插入,更新高度,如果高度差超过一:
- 情况一:右旋(2的右节点变成1新的左节点)
\(~~~~~~~~~~\)①\(~~~~~~~~~~~~~~~~~~~~\)②
\(~~~~~~~~~\)/\(~~~~~~~~~~~~~~~~~~~~~\)/\(~~~~~~~\)\
\(~~~~~~\)②\(~~~~~~~~~~~~~~~~~~~\)③\(~~~~~~~~\)①
\(~~~~~\)/
\(~~\)③ - 情况二:右左旋(先对2进行左旋,3的左节点变成2的右节点,变成情况一;再对1右旋,3的右节点变成1的左节点)
\(~~~~~~~~~~\)①\(~~~~~~~~~~~~~~~~~~\)①\(~~~~~~~~~~~~~~~~~~\)③
\(~~~~~~~~~\)/\(~~~~~~~~~~~~~~~~~~~~\)/\(~~~~~~~~~~~~~~~~~~~~\)/\(~~~~~~\)\
\(~~~~~~\)②\(~~~~~~~~~~~~~~~~~~\)③\(~~~~~~~~~~~~~~~~~~\)②\(~~~~~~\)①
\(~~~~~~~~~~\)\\(~~~~~~~~~~~~~~~~\)/
\(~~~~~~~~~~~~\)③\(~~~~~~~~~\)② - 情况三,四,左旋和左右旋,对称即可
- 删除
- 如果左右节点都没有东西,删除,更新高度
- 如果只有左节点或者右节点,把子节点向上提即可
- 如果左右都有节点,找到根节点的右节点的最左子节点,覆盖根节点,改为删除用于覆盖的节点
- 递归删除后判断高度是否超出误差,如果超出误差则左旋或右旋
寻路
深度优先(DFS)
- 各个方向试探,优先一个方向探索,到思路回退,主要用到栈
广度优先(BFS)
- 将当前能走到的节点全部纳入数组,再纳入下一层节点,用动态数组
A*
- 和广度差不多,对节点赋予权值,每次从数组中找权值最小的节点向外拓展