Parento函数的算法效率? template <class T while((leftmostchild=PrevSibling (pointer))I=NULL) pointer=leftmostchild; TreeNode<t>* leftmostchild=pointer; Tree<T>:: Parent(TreeNode<T>k current) pointer=root; //返回 current结点的父结点 TreeNode<T>* pointer=current; return NULL; else return getParent( pointer, leftmostchild) if(pointer !=NULL) return NULL; TreeNode<t>* leftmostchild=nULLi 北大啦 张铭写 大息单 张铭 有,盛 525父指针表示法 父指针数组表示法 父指针( parent pointer)表示法 个点只保存一个指针指向其父点 最简单 ○○ 判斷两个结点是否在同一棵树 两个结点到达同一根鳍点,它们一定在同棵树中 父結点素引团0z国44s6 如果找到的根结点是不同的,那么两个点就不在同一操树中 标记 BCKDEFG 结点索引01234 北大位 张 新有,究 张铭鷾 叔有,印鱼究 父指针表示法构建树专题 等价类( equivalence classes 令等价类及其并查算法 误是素蠶 个元的集合S 个定义在集合S上的r个关 且仅当如下条件为真时成工 令算法示例 令树的父指针表示与 c)若(x,y)∈R且(y,z)∈R,则有(x,2)∈R(即关系是传递 UNION/FIND算法实现 如果(x,y)∈R,则元素x和y是等价的 令路径压缩和优化 愈桑#捏英价的秃素历驾爽钩都药尧食←侨最大, 由X∈s生成的一个R等价类 ∵R、分最不交的划分,5豆,.,s,这幽合的并为5 物歌抗 新有,食邮岛究 张铭帖 有,即究8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 Parent()函数的算法效率？ template <class T> TreeNode<T>* Tree<T>::Parent(TreeNode<T>* current) {//返回current结点的父结点 TreeNode<T>* pointer=current; if(pointer !=NULL) return NULL; TreeNode<T>* leftmostChild=NULL; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 while((leftmostChild=PrevSibling(pointer))!=NULL) pointer=leftmostChild; leftmostChild=pointer; pointer=root; if( leftmostChild ==root) return NULL; else return getParent ( pointer , leftmostChild); } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 5.2.5 父指针表示法 „ 父指针(parent pointer)表示法 „ 每个结点只保存一个指针域指向其父结点 „ 最简单 „ 但是…… „ 判断两个结点是否在同一棵树 „ 两个结点到达同一根结点，它们一定在同一棵树中 „ 如果找到的根结点是不同的，那么两个结点就不在同一棵树中 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 父指针数组表示法 A B C K H J F D E G 01 89 2 3 4 5 6 7 父结点索引 标记 结点索引 A B C K D E F G H J 0 0 2 4 4 4 5 6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 父指针表示法构建树专题 „ 等价类及其并查算法 „ 算法示例 „ 树的父指针表示与 UNION/FIND算法实现 „ 路径压缩和优化 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 等价类(equivalence classes) „ 一个具有n个元素的集合S，另有一个定义在集合S上的r个关 系的关系集合R。x，y，z表示集合中的元素 „ 若关系R是一个等价关系，当且仅当如下条件为真时成立： „ （a）对于所有的x，有(x，x)∈R（即关系是自反的）； „ （b）当且仅当(x，y)∈R时(y，x)∈R（即关系是对称的）； „ （c）若(x，y)∈R且(y，z)∈R，则有(x，z)∈R（即关系是传递 的）。 „ 如果(x，y)∈R，则元素x和y是等价的 „ 等价类是指相互等价的元素所组成的最大集合。所谓最大， 就是指不存在类以外的元素，与类内部的元素等价 „ 由x∈S生成的一个R等价类 „ [x]R = {y| y∈S ∧ xRy} „ R将S划分成为r个不相交的划分S1，S2，…Sr，这些集合的并为S