锐客网

  1. 首页 > 睿知 > it技术 > >

亿点点难的算法|PAT甲级备战-树（一）

c++PAT甲级


文章目录

      • 刷题技巧
      • 单链表
      • 邻接表
        • 用邻接表表示一棵树
      • 树的遍历
      • 并查集
    • 二叉树
      • 二叉树三种深度遍历
      • 二叉树的广度优先遍历
      • 二叉搜索树
      • 反转二叉树

刷题技巧
输入int类型的01，默认输入1
for(int i=0; ~b; i++) 这里的~b为b!=-1
memset(数组名，赋的初值，sizeof 数组名) 初始化数组

单链表
在解决图和树的数据结构问题时，常常用邻接表来存储。邻接表是由很多条单链表构成的，而单链表的实现方式有很多，如数组，结构体，vector等容器实现，在这些实现方式中，静态数组的速度是最快的。
亿点点难的算法|PAT甲级备战-树（一）
文章图片

  • 传统结构体表示链表
struct Node{ int value; Node* next; }

每次创建新的链表节点，都需要new一个新的结构体，在竞赛级别的算法题目里，链表的长度都是十万百万级，如果每次创建一个新节点都new一次，光创建出这个链表就已经超时了。
  • 静态数组表示
这里的静态和动态其实是指是否需要重复开辟空间。提前开辟好空间以后用这些空间去表示称为静态，与之对应的每次都需要开辟空间称为动态。
那，如何表示呢？
亿点点难的算法|PAT甲级备战-树（一）
文章图片

e[N], ne[N], head, idx来表示一个单链表！
**e[N]**存放每一个节点的值，**ne[N]**存放下一个节点的下标，head指向头结点，idx表示已经用到了数组中的哪个节点。
  • 具体操作
// 初始化 void init() { head = -1; idx = 0; }// 将x插到头结点 void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx ++ ; }// 将x插到下标是k的点后面 void add(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ; }// 将下标是k的点后面的点删掉 void remove(int k) { ne[k] = ne[ne[k]]; }


邻接表

用邻接表表示一棵树 用idx，h[N]，ne[N]，e[N]表示
h[N]用于存放邻接表的表头
亿点点难的算法|PAT甲级备战-树（一）
文章图片

构建树
add(int parent_id,int child_id){ //为值为parent_id的父节点添加一个值为child_id的子节点 e[idx] = child_id,ne[idx]=h[parent_id],h[parent_id] = idx++; }

  • e[]的索引是idx，值是节点中存放的值
  • ne[]的索引是idx，值是下一个节点的idx
  • h[]的索引是节点中存放的值，值是下一个节点的idx
树的遍历
  1. 前序遍历，中序遍历，后续遍历（DFS）
  • 前序遍历 (preorder) 根左右
  • 中序遍历 (inorder)左跟右
  • 后续遍历 (postorder)左右跟
倒推
亿点点难的算法|PAT甲级备战-树（一）
文章图片

  • 前序的第一个是root，后序的最后一个是root。
  • 先确定跟节点，然后根据中序遍历，在根左边的为左子树，根右边的为右子树
  • 对于每一个子树可以看成一个全新的树，仍然遵循上面的规律。
划重点！！根据上面的推论，只要确定了根节点的位置，根据中序遍历我们就能确定左右子树的位置，递归从而构建出整个二叉树。也就是说，我们知道一颗二叉树前序遍历和中序遍历或者后续遍历和中序遍历，就能构建二叉树，而知道前序遍历和后续遍历则不行。
// 一边建树一边遍历 #include using namespace std; const int N = 50010; unordered_map l,r,pos; int in[N],pre[N],n; vector post; int build(int il,int ir,int pl,int pr){ int root = pre[pl]; int k = pos[root]; if(il>n; for(int i=0; i>pre[i]; } for(int i=0; i>in[i]; pos[in[i]]=i; } int root=build(0,n-1,0,n-1); cout<

  1. 层序遍历（BFS）
//p存放层序遍历的结果，l存放父节点的左儿子，r存放父节点的右儿子 void bfs(int root){ p[0] = root; int hh=0,kk=0; while(hh<=kk){ int t = p[hh++]; if(l.count(t)) p[++kk] = l[t]; if(r.count(t)) p[++kk] = r[t]; } cout<


并查集
  • 并查集有思维巧妙，代码简短的特点，是面试热点问题。
简单描述一下并查集
现在有两个集合a和b，从这两个集合中取出任意一个元素，如何判断该元素属于哪个集合？以及如何快速将两个集合合并？
–常见思路–
定义一个belong[]数组存储元素归属
if(belong[x]=='a') puts('a'); else puts('b');

定义数组操作，查询元素归属的时间复杂度是O(1)；但合并两个操作呢？
只能在定义一个新的数组，然后把每个集合中的元素都存进去，时间复杂度为O(n)！
有没有什么办法实现这两个操作且时间复杂度低？
并查集可以在近乎O(1)的时间复杂度下实现这两个操作!!
  • 将集合中的元素存在树中，定义一颗树的跟节点为这个集合的id，定义一个数组p[]存取每个元素的父节点, x的父节点是p[x],而根节点的父节点就是其本身，即p[x]=x，所以我们只要一直不断向上查询这个元素的根节点，就能知道归属。
  • 对于合并集合，由于这两个集合是以两颗树的形式存在，我们只要让一颗树的根节点的父节点为另一颗树的根节点，即可把这两颗树连起来。
亿点点难的算法|PAT甲级备战-树（一）
文章图片

代码实现
  • p[]数组存放每个元素的父节点，即x的父节点是p[x]
  • find(int x)：查找某一元素的根节点
  • 判断归属 if( find(a) == find(b) ) 属于同一个集合
  • 合并 p[find(a)] = find(b)
  • 如何实现find()函数
//常规思路，由于每次都要while一遍，所以查找根节点的时间复杂度是个问题 int find(int x){ while(p[x]!=x) x = p[x]; return x; }// 采用路径压缩优化，路径压缩就是在查询根节点的过程中，将路径上的每一个节点的父节点都 //重新设置为根节点，避免重复查找，这样时间复杂度可以近乎缩减为O(1); int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }

亿点点难的算法|PAT甲级备战-树（一）
文章图片

#include using namespace std; const int N = 100010; int p[N]; int find(int x) // 返回x的祖宗节点 + 路径压缩 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main(){ int n,m; cin>>n>>m; for(int i=1; i<=n; i++){ p[i] = i; } while(m--){ char ins; int a,b; cin>>ins>>a>>b; if(ins=='M') p[find(a)] = find(b); else{ if(find(a)==find(b)) puts("Yes"); else puts("No"); } } return 0; }


二叉树 二叉树可以用两个数组 l[N] , r[N] 来表示, N 为节点数量，l[i] 记录节点 i 的左儿子，r[i] 记录节点i的右儿子

二叉树三种深度遍历
// k用来记录当前位置，满足pat空格检测输出 void dfs_pre(int root,int &k){ if(root == -1) return; if(++k == n) cout<


二叉树的广度优先遍历
void bfs(int root){ q[0] = root; int hh=0,tt=0; while(hh<=tt){ int t = q[hh++]; if(l[t]!=-1) q[++tt] = l[t]; if(r[t]!=-1) q[++tt] = r[t]; } }


二叉搜索树
二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树
如果是一棵二叉搜索树，那么其中序遍历必然为一组升序排列的数列！
c++里set容器就是用二叉搜索树实现的
完全二叉树可以用一维数组存储

反转二叉树
【亿点点难的算法|PAT甲级备战-树（一）】亿点点难的算法|PAT甲级备战-树（一）
文章图片

#include using namespace std; const int N = 11; int l[N],r[N],q[N],n; bool has_father[N]; void dfs_re(int root){ if(root == -1) return; dfs_re(l[root]); dfs_re(r[root]); swap(l[root],r[root]); } void bfs(int root){ q[0] = root; int hh=0,tt=0; while(hh<=tt){ int t = q[hh++]; if(l[t]!=-1) q[++tt] = l[t]; if(r[t]!=-1) q[++tt] = r[t]; } cout<>n; for(int i=0; i>a>>b; if(a!='-'){ l[i]=a-'0'; has_father[l[i]] = true; } if(b!='-'){ r[i]=b-'0'; has_father[r[i]] = true; } } int root = 0; // 寻找根节点 while(has_father[root]) root++; // 反转二叉树 dfs_re(root); // 输出层序遍历 bfs(root); // 输出中序遍历 int k = 0; // 负责记录当前位置来判断是否需要输出空格 dfs_in(root,k); return 0; }

    推荐阅读


    上一篇：笔记|js事件流

    下一篇：PAT甲级|PAT甲级备战-高精度和排序