树与二叉树的常用算法

《树与二叉树的常用算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、树与二叉树的常用算法2010山东夏令营Author:Will1.定义树：要么为空，要么由根结点(root)和n棵子树组成。森林：若干棵树二叉树：递归定义要么为空，要么由根结点左子树和右子树组成左右子树都是一颗二叉树2.树与二叉树的转化左儿子右兄弟表示法这样的好处是在很多树形动态规划问题中能大大降低编程复杂度和算法的时间复杂度3.如何分辨树关键词任意两点只有一条路径平面每个点只向左连一条边N个点N-1条边的连通图……4.树遍历先序遍历中序遍历后续遍历层次遍历对应了搜索问题——搜索问题即在一颗搜索树上进行遍历4.1深度优先遍历分析遍历序列的性质先序遍历：aBC中序遍历：BaC后

2、序遍历：BCa可以发现在DFS遍历序列中一棵子树必然是连续一段，因此子树可以和区间相对应aBC4.2宽度优先遍历和图的宽度优先遍历一致使用队列优点：不使用栈空间速度快遍历序列即为层次拓扑序列4.3树遍历的若干技巧由于树的稀疏性，请使用邻接表来存储树邻接表并不需写链表，建议使用数组模拟链表structedge{Intu,v,nxt;Inlineedge(intu=0,intv=0,intnxt=-1):u(u),v(v),nxt(nxt){};}e[MaxE];Inthead[MaxN],tot;//head初始值为-1IntInsert(u,v){E[tot]=edge(u

3、,v,head[u]);head[u]=tot++;}遍历：For(inti=head[u];i!=-1;i=e[i].nxt)5.并查集支持操作：合并两个集合查找集合的代表元素实现方式：父亲记录法用一棵树来表示一个集合根作为集合的代表元素合并即将一个集合的根指向另一个集合的根5.并查集优化：按秩合并每次总是将点的个数小的那个集合的根指向点数较多的那个集合的根路径压缩即在寻找根的过程中，将所有指针经过的结点都直接指向根5.并查集C++代码:fst记录父亲，rank记录点的个数intfind(v){If(fst[v]==v)returnv;Elsereturn(fst[v]=

4、find(fst[v]))}Intunite(intu,intv){U=find(u);v=find(v);If(rank[u]>rank[v])swap(u,v);Rank[v]+=rank[u];fst[u]=v;}5.并查集思考题：团伙城市里有N个人，给出M条信息，每条信息告诉你两个是朋友还是敌人一个人朋友的朋友是朋友一个人敌人的敌人还是朋友请问这个城市里有多少个团伙？或者输出不可能N,M<5000006.LCALCA(LowestCommonAncestor)最近公共祖先问题：倍增算法O(NlogN)-O(logN)——在线区间RMQ算法O(NlogN)-O(1)—

5、—在线区间+1RMQ算法O(N)-O(1)——在线Tarjan算法O(N+Qα(N))-O(1)——离线6.LCA倍增算法：Dep[v]记录v的深度Fa[v][k]记录v向上第2k个祖先预处理：Fa[v][k]=fa[fa[v][k-1]][k-1]时空复杂度O(NlogN)6.LCAv向上走p层Go_up(&v,p){For(inti=0;i=0;--i)If(fa[u

6、][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];Returnfa[v][0];}//O(logN)7.二叉堆堆是一个特殊的二叉树每个结点有一个权值根结点的权值不小于其两个孩子结点的权值支持操作：插入一个元素O(logN)删除一个元素O(logN)调整一个元素O(logN)寻找最大值O(1)7.二叉堆堆的存储方式——数组C++的选手可以使用Algorithm内的标准的堆相关函数E.g.hp[]记录堆元素pos[]记录元素在堆中位置val[]记录元素的权值元素个数为S则对于点v其父亲为v-1>>1其左孩子为(v<<1)+1//若大于S则不存在其右孩子为

7、(v<<1)+2//若大于S则不存在7.二叉堆调整元素——将一个元素v的值变大/变小Pop_down(v){Intc=v,i=(v<<1)+1,j=(v<<1)+2;If(i