数据结构、算法与应用-C++描述8.ppt

* * A B D E C G F H I J D E B C A G J H I F 对下图所示的森林，按后根遍历所得的结点序列为： * * 森林的广度优先遍历 是一种按照层次遍历树林的方法，具体的遍历过程是：首先从左到右访问层数为0的所有结点，然后再从左到右访问层数为1的所有结点，...，直到访问完其余各层所有的结点。 * * A B D E C G F H I J 按广度优先遍历图示的树林 ,所得到的结点序列为： AF BCGHI DEJ * * 输出树中所有从根到叶子的路径的算法: A B C D E F G H I J K 例如：对左图所示的树，其输出结果应为： A B E A B F A C A D G H I A D G H J A D G H K * * void AllPath( BiTree T, Stack S ) { if (T) { Push( S, T-data ); if (!T-Lchild !T-Rchild ) PrintStack(S); else { AllPath( T-Lchild, S ); AllPath( T-Rchild, S ); } Pop(S); } // if(T) } // AllPath 输出二叉树上从根到所有叶子结点的路径 * * void OutPath( Bitree T, Stack S ) { while ( !T ) { Push(S, T-data ); if ( !T-firstchild ) Printstack(S); else OutPath( T-firstchild, S ); Pop(S); T = T-nextsibling; } // while } // OutPath 输出树中所有从根到叶的路径 * * 设置信号放大器(Placement of Signal Boosters) 在线等价类(Online Equivalence Classes) 8.10 应用 * * 为简化问题，设分布网络是一树形结构，源是树的根。树中的每一节点(除了根)表示一个可以用来放置放大器的子节点。信号从一个节点流向其子节点。每条边上标出从父节点到子节点的信号衰减量。 问题形式化 * * 信号从节点p 流到节点v 的衰减量为?。从节点q 到节点x 的衰减量为? 问题形式化 * * 设D(i)为从节点i到以i为根节点的子树的任一叶子的衰减量的最大值。 D(叶节点)=? D(s)=? D(i)= max {D(j) + d(j)} j是i的一个孩子 如何计算D？ 定义 * * 计算D并放置放大器s 的伪代码为： D(i) = 0 ; for (i的每个孩子j ) if ((D(j)+d(j))tolerance) 在j 放置放大器; else D(i) = max{D(i),D(j)+d(j)}; 思想 * * n个元素初始各在其自己的类中，然后执行一系列Find和Combine操作。 操作Find(e)返回元素e所在类的唯一特征。 Combine(a,b)用来合并包含a和b的类。 其复杂性为O(n+ulogu+f)。 在线等价类问题也称作离散集合合并/搜索问题(disjoint setunion-find problem)。 在线等价类 * * 元素1、2、20、30等在以20为根的集合中；元素11、16、25、28在以16为根的集合中；元素15在以15为根的集合中；元素26和32在以26为根的集合中(或简称为集合26) 树形描述 * * 使用模拟指针。 每个节点有一个parent域。每个parent 域给出父节点的索引。 树形描述 * * void Initialize(int n) {//初始化，每个类/树有一个元素 parent=new int[n+1]; for(int e=1;e=n;e++) parent[e]=0; } 基于树结构的合并/搜索问题解决方案 * * Int Find(int e) {//返回包含e的树的根节点 while(parent[e]) e=parent[e];//上移一层 return e; } void Union(int i,int j) {//将根为i和j的两棵树进行合并 parent[j]=i; } 基于树结构的合并/搜索问题解决方案 * * 缩短