北京大学：《数据结构与算法》课程教学资源（实验班讲义）第五章 树

主要内容 数据结构与算法 第五章树 51树的概念 52树的链式存储 任课教员:张铭 http:/db.pku.edu.cn/mzhang/ds/ 53树的顺序存储 zhang@db.pku.edu.cn 北京大学信息科学与技术学院 令54K又树 网络与信息系统研究所 版权所有,转或翻印必究 补充树计数 张铭嶇 0权责。翰印彭究 51树的概念 511树和森林 令511树和森林 令树的逻辑结构 令树形结构的各种 512森林与二叉树的等价转换 表示法 令513树的抽象数据类型 树的定义和概念∞ BObF GO C 令森林的定义 令514树的周游 张帖霉 斯有 京大息 树的逻辑结构 树形结构的各种表示法 包含n个结点的有穷集合K(n>0),且在K上定义了一个 关系N,关系N满足以下条件 树形表示法 有且仅有一个点k。∈K,它对于关系N来说没有齣驱。结 令形式语言表示法 除结点k外,K中的每个结点对于关系N来说备有且仅有一 令文氏图表示法 除結点k外的任何结点k∈K,都存在一个结点序列k0 令凹入表表示法 k1,…,k3,使得k就是树根,且k=k,其中有序对∈N(1≤≤s)。这样的结点序列称为从根到结点k的 北京大带息歌

1 数据结构与算法 第五章 树 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 5.1 树的概念 „ 5.2 树的链式存储 „ 5.3 树的顺序存储 „ 5.4 K叉树 „ 补充 树计数 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 5.1 树的概念 „ 5.1.1 树和森林 „ 5.1.2 森林与二叉树的等价转换 „ 5.1.3 树的抽象数据类型 „ 5.1.4 树的周游 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 5.1.1 树和森林 „ 树的逻辑结构 „ 树形结构的各种 表示法 „ 树的定义和概念 „ 森林的定义 I J F E G A B C D H 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 树的逻辑结构 „ 包含n个结点的有穷集合K (n>0)，且在K上定义了一个 关系N，关系N满足以下条件： „ 有且仅有一个结点k0∈K，它对于关系N来说没有前驱。结 点k0称作树的根 „ 除结点k0外，K中的每个结点对于关系N来说都有且仅有一 个前驱 „ 除结点k0外的任何结点k∈K，都存在一个结点序列k0， k1，…，ks，使得k0就是树根，且ks=k，其中有序对∈N(1≤i≤s)。这样的结点序列称为从根到结点k的 一条路径 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 树形结构的各种表示法 „ 树形表示法 „ 形式语言表示法 „ 文氏图表示法 „ 凹入表表示法 „ 嵌套括号表示法

树形表示法 形式语言表示法 树的理辑结构是 结点集合K={A,B,C,D,E,F,G,H,I, K上的关系N={,,, ○○○ B,E>,,, (a)树形表示法 有,轴 张铭嶇 0权责。翰印彭究 文氏图表示法 凹入表表示法 oooollo o (b)文氏图衰示法 c)凹入表表示法 张帖霉 张铭 512豪林与二叉树的等价转换 歌晶灵型 嵌套括号表示法 24动态左子点右兄弟点“二又链我表示法 (A(B(D)(E(D)(J)(F)C(G)(H)) (d)墩套括号表示法 534带度量的后次序表示 图书目录,杜威表示法

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 树形表示法 I J F E G A B C D H （a）树形表示法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 形式语言表示法 树的逻辑结构是： 结点集合K={A，B，C，D，E，F，G，H，I，J} K上的关系N={，，， ，，， ，，} 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 文氏图表示法 A B C D I J F E G H （b）文氏图表示法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 凹入表表示法 B A D E I J F G H C （c）凹入表表示法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 5 树 5.1 树的概念 5.1.1 树和森林 5.1.2 森林与二叉树的等价转换 5.1.3 树的抽象数据类型 5.1.4 树的周游 5.2 树的链式存储 5.2.1 子结点表表示法 5.2.2 左子结点/右兄弟结点表示法 5.2.3 动态结点表示法 5.2.4 动态“左子结点/右兄弟结点”二叉链表表示法 5.2.5 父指针表示法及等价类的并查算法 5.3 树的顺序存储 5.3.1 带右链的先根次序表示法 5.3.2 带双标记位的先根次序表示法 5.3.3 带左链的层次次序表示法 5.3.4 带度数的后根次序表示法 5.4 K叉树 „ 图书目录，杜威表示法 凹 入表表 示法 (例子 ) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 嵌套括号表示法 (A(B(D)(E(I)(J))(F))(C(G)(H))) （d）嵌套括号表示法

氏图到嵌套括号表示的转化 树的定义 从最外依次将示集合 的方福转化牺号对 ■树是包括n个结点的有限集合T(n1),使得 有一个特别标出的称作根的蜡点 除根以外的其它结点被分成m个m20不相交的靠合T o⊙@o⊙@ T2,…,Tm,而且这些集合的每一个又都是树。树T1 T2,…,Tm称作这个根的子树 ■这个定义是递归的,我们用子树来定义树:只包 (A(BDOE(OF(C(GHD 结点的树必然仅由根组成,包含n>1个结 点的树借助于少于n个结点的树来定义 北大啦 机新有,食 大息单 有,盛 树结构中的概念(1) 树结构中的概念(2) 着∈N,则称k是k!的父结点(或称“父 母),而k′则是k的子结点(或“儿子”、“子女”) 没有子树的结点称作树叶或终端结点 着有序对及∈N,则称k’和k 为兄弟 非终端结点称为分支结点 :若有一条由k到达k的陪径,则称k是k3的祖先,k是k 一个结点的子树的个数称为度数 的子孙 树形结构中,两个结点的有序对,称作连接这两结点的 根结点的层数为0,其它任何结点的层数 等于它的父结点的层数加1 北大位 张 新有,究 张铭鷾 叔有,印鱼究 树结构中的概念(3) 512森林与二叉树的等价转换 有序树在树T中如果子树T1,T2,…, 森林( forest)森林是零棵或多 Tm的相对次序是重要的,则称树T为有向 棵不相交的树的集合(通常是有 序集合)。 有序树,简称有序树。 删去树根,树就变成森林 在有序树中可以称T1是根的第一棵子树,T2 加上一个结点作树根,森林就变 是根的第二棵子树,等等 成树 物歌抗 新有,食邮岛究 张铭·票有,气即必究

3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 文氏图到嵌套括号表示的转化 A B C D E I J G H F (A(B(D)(E(I)(J)) (C (F)) (G)(H))) 从最外层依次将表示集合 的方框转化成括号对 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 树的定义 „ 树是包括n个结点的有限集合T（n≥1），使得： „ 有一个特别标出的称作根的结点 „ 除根以外的其它结点被分成m个(m≥0)不相交的集合T1， T2，…，Tm，而且这些集合的每一个又都是树。 树T1， T2，…，Tm称作这个根的子树 „ 这个定义是递归的，我们用子树来定义树：只包 含一个结点的树必然仅由根组成，包含n>1个结 点的树借助于少于n个结点的树来定义 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 树结构中的概念(1) „ 若∈N，则称k是k′的父结点（或称“父 母”），而k′则是k的 子结点(或“儿子”、“子女”) „ 若有序对及∈N，则称k′和k″ 互为兄弟 „ 若有一条由 k到达ks的路径，则称k是ks的祖先，ks是k 的子孙 „ 树形结构中，两个结点的有序对，称作连接这两结点的 一条边 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 树结构中的概念(2) „ 没有子树的结点称作树叶或终端结点 „ 非终端结点称为分支结点 „ 一个结点的子树的个数称为度数 „ 根结点的层数为0，其它任何结点的层数 等于它的父结点的层数加1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 树结构中的概念(3) „ 有序树 在树T中如果子树T1，T2，…， Tm的相对次序是重要的，则称树T为有向 有序树，简称有序树。 „ 在有序树中可以称T1是根的第一棵子树，T2 是根的第二棵子树，等等 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 5.1.2 森林与二叉树的等价转换 „ 森林(forest) 森林是零棵或多 棵不相交的树的集合(通常是有 序集合)。 „ 删去树根，树就变成森林 „ 加上一个结点作树根，森林就变 成树

森林与二叉树的等价转换(续) 图示:森林与二叉树 在树或森林与二叉树之间有一个自然 对应的关 树所对应的二叉树里 ○○ 二个孳蝻2 左子结点是它在原来树里的第 右子结点是它在原来的树里的下一个兄弟 机新有,食 大息单 张铭 有,盛 形式化:森林到二叉树 形式化:二叉树到森林 把森林F看作树的有序集合,F=(T1T2,…, 设B是一棵二叉树,rt是B的根,L是rt的左 Tn),对应于F的二叉树B(F)的定义是 子树,R是rt的右子树,则对应于B的森林 若n=0,则B(F)为空 F(B)的定义是: 着n>0,则B(F)的根是T1的根W1,B(F的左子树是 B(T1,T12,…,T1m),其中T1,T12,…,T1m是 若B为空,则F(B)是空的森林。 W1的子树;B(F的右子树是B(T2 若B不为空,则F(B)是一棵树T加上森林 此定义精确地确定了从森林到二叉树的转换 F(R),其中树T1的根为t,rt的子树为F(L 北大位 张 张铭鷾 叔有,印鱼究 513树/森林的结点ADT(1) 树/森林的结点ADT(2) emplate void setvalue(T&)/设量结点的值 class TreeNode /设量左子结点 void s Id(TreeNode* pointer) /设量右兄弟 Tree Node( const T&)//贝构造函数 void setsibling (TreeNode* pointer); virtual~ TreeNodert};//析构函数 //以第一个左子结点身份插入结点 bool isLeafo /如果绪点是叶,返回tue void InsertFirst(TreeNode* node); 返回结点的值 //以右兄弟的身份插入结点 TreeNode* LeftMostChildo;//返回第一个左孩子 void InsertNext(TreeNode* node); TreeNode* Rightsibling(;/返回右兄弟 物歌抗 张 张铭·票有,气即必究

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 森林与二叉树的等价转换(续) „ 在树或森林与二叉树之间有一个自然 的一一对应的关系。 „ 任何森林都唯一地对应到一棵二叉树；反 过来，任何二叉树也都唯一地对应到一个 森林。 „ 树所对应的二叉树里 „ 一个结点的左子结点是它在原来树里的第 一个子结点 „ 右子结点是它在原来的树里的下一个兄弟 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 图示：森林与二叉树 G F D H J T2 E A B1 T11 T12 T1 C K G F H D C A B1 K E J 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 形式化：森林到二叉树 „ 把森林F看作树的有序集合，F=(T1，T2，…， Tn)，对应于F的二叉树B(F)的定义是： „ 若n=0，则B（F）为空 „ 若n>0，则B(F)的根是T1的根W1，B(F)的左子树是 B(T11，T12，…，T1m)，其中T11，T12，…，T1m是 W1的子树；B(F)的右子树是B(T2，…，Tn) „ 此定义精确地确定了从森林到二叉树的转换 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 形式化：二叉树到森林 „ 设B是一棵二叉树，rt是B的根，L是rt的左 子树，R是rt的右子树，则对应于B的森林 F(B)的定义是： „ 若B为空，则F(B)是空的森林。 „ 若B不为空，则F(B)是一棵树T1加上森林 F(R)，其中树T1的根为rt，rt的子树为F(L) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 5.1.3 树/森林的结点ADT(1) template class TreeNode { public: TreeNode(const T&);//拷贝构造函数 virtual ~TreeNode(){}; //析构函数 bool isLeaf(); //如果结点是叶，返回true T Value(); //返回结点的值 TreeNode* LeftMostChild(); //返回第一个左孩子 TreeNode* RightSibling(); //返回右兄弟 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 树/森林的结点ADT(2) void setValue(T&); //设置结点的值 //设置左子结点 void setChild(TreeNode* pointer); //设置右兄弟 void setSibling(TreeNode* pointer); //以第一个左子结点身份插入结点 void InsertFirst(TreeNode* node); //以右兄弟的身份插入结点 void InsertNext(TreeNode* node); };

树/森林的ADT(1) 树/森林的ADT(2) template class Tree 返回 current结点的父结点 TreeNode* Parent(TreeNode* current); //构造函数 /删除以 subroot为根的子树的所有结点 virtual~ Tree(;//析构函数 void Delete SubTree(TreeNode* subroot) 回树中的根结点 /先根深度优先周游树 TreeNode* getRooto void Root First /创建树中的根结点,使根结点元章的值为 rootValue /后根深度优先周游树 void CreateRoot(const T& rootValue); 判断是否为空树,如果是则返回true 广度优先周游树 bool isEmpty Or id widthTraverse(TreeNode* root); 北大啦 514森林的周游 森林的周游 按深度方向周游 先根次序 后根次序 ○○ ndBI Rr 按广度方向周游 宽度优先周游 层次周游 北大位 张 新有,究 张铭鷾 叔有,印鱼究 周游森林vs周游二叉树 补充:一种广度优先周游森林 m先根次序周游森林 前序法周游二叉树 后根次序周游森林 ■按中序法周游对应的二叉树 ■中根周游? 无法明确规定根在哪两个子结点之间 Prevsiblingo函数采用本框架 物歌抗 新有,食邮岛究 张铭·票有,气即必究

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 树/森林的ADT(1) template class Tree { public: Tree(); //构造函数 virtual ~Tree(); //析构函数 //返回树中的根结点 TreeNode* getRoot(); //创建树中的根结点，使根结点元素的值为rootValue void CreateRoot(const T& rootValue); //判断是否为空树，如果是则返回true bool isEmpty(); 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 树/森林的ADT(2) //返回current结点的父结点 TreeNode* Parent(TreeNode* current); //返回current结点的前一个邻居结点 TreeNode* PrevSibling(TreeNode* current); //删除以subroot为根的子树的所有结点 void DeleteSubTree(TreeNode* subroot); //先根深度优先周游树 void RootFirstTraverse(TreeNode* root); //后根深度优先周游树 void RootLastTraverse(TreeNode* root); //广度优先周游树 void WidthTraverse(TreeNode* root); }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 5.1.4 森林的周游 „ 按深度方向周游 „ 先根次序 „ 后根次序 „ 按广度方向周游 „ 宽度优先周游 „ 层次周游 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 森林的周游 A B C K F D E G H J G H F D C A B K E J 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 周游森林vs周游二叉树 „ 先根次序周游森林 „ 前序法周游二叉树 „ 后根次序周游森林 „ 按中序法周游对应的二叉树 „ 中根周游？ „ 无法明确规定根在哪两个子结点之间 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 补充：一种广度优先周游森林 A B C K F D E G H J G H F D C A B K E J „ PrevSibling()函数采用本框架

广度优先周游森林 广度优先周游森林(续) template while (laQueue empty o void Tree: WidthTraverse2(TreeNode* pointer=qUeue. fronto /取队首 /使用STL队列 qUeue popO; //出队列 using st Visit(pointer> value();/访问 queuek> qUeue dek pointer=root pointer pointer->LeftMostchildo; while(pointer qUeue. push(pointer) aQueue. push (pointer); pointer= pointer-> Rightsiblingo pointer pointer->Rightsiblingo 机新有,食 大息单 张铭 有,盛 教材广度优先周游图示 广度优先周游森林(教材) void Tree: WidthTraverse1(TreeNode*k using sta::q /使用STL队列 queue*> qUeue if ( pointer) return; qUeue. push (pointer) while laQueue empty ot pointer≡ qUeue. fronto;/取队列首结点指针 北大位 张 新有,究 张铭鷾 叔有,印鱼究 广度优先周游森林 广度优先周游森林 Visit( pointer> Value0)//访问当前结点 if (pointer->LeftMostchildo d while(pointer->Rightsiblingo) qUeue. push(pointer f( pointer-> LeftMostchildo)//左子结点进入队列 >LeftMostchildoi aQueue. push(pointer->LeftMostchildo; qUeue popo;∥出队列 pointer=pointer->RightsiblingO; Visit(pointer-> Value();//访问右兄弟结点 f/end while 物歌抗 新有,食邮岛究 张铭·票有,气即必究

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 广度优先周游森林 template void Tree::WidthTraverse2(TreeNode* root){ using std::queue; //使用STL队列 queue*> aQueue; TreeNode* pointer=root; while (pointer) { aQueue.push(pointer); pointer = pointer-> RightSibling()； } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 广度优先周游森林(续) while(!aQueue.empty()){ pointer=aQueue.front(); //取队首 aQueue.pop(); //出队列 Visit(pointer->Value()); //访问 pointer = pointer->LeftMostChild(); while (pointer) { aQueue.push(pointer); pointer = pointer-> RightSibling()； } } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 教材广度优先周游图示 A B C K F D E G H J G H F D C A B K E J 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 广度优先周游森林（教材） template void Tree::WidthTraverse1(TreeNode* root){ using std::queue; //使用STL队列 queue*> aQueue; TreeNode* pointer=root; if (!pointer) return; aQueue.push(pointer); while(!aQueue.empty()) { pointer=aQueue.front();//取队列首结点指针 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 广度优先周游森林 Visit(pointer->Value()); //访问当前结点 while(pointer->RightSibling()) { if(pointer->LeftMostChild())//左子结点进入队列 aQueue.push(pointer->LeftMostChild()); pointer=pointer->RightSibling(); Visit(pointer->Value()); //访问右兄弟结点 } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 广度优先周游森林 if (pointer->LeftMostChild()) aQueue.push(pointer ->LeftMostChild()); aQueue.pop(); //出队列 }//end while } F D E G A B

452森林的链式存储52子结点表示法 521子结点表表示法 ①522左子结点/右兄弟结点表示法 523动态结点表示法 524动态左子/右兄弟”二又链表表示法 △525父指针表示法 ■第140页图56 北大啦 机新有,食 大息单 张铭 有,盛 522左子结点/右兄弟结点表示法 523动态结点表示法 第140页图57 第142页图59 练度皮右兄 山a國 张铭鷾 叔有,印鱼究 第142页图510 动态表示法 5.24动态“左子/右兄弟二叉链表 左结点/右兄弟:最常用 □ [ △E ①@弟①① 泅□d b)左子女一右兄弟表示Ma 新有,食邮岛究 张铭帖 有,即究

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 5.2 森林的链式存储 „ 5.2.1 子结点表表示法 „ 5.2.2 左子结点/右兄弟结点表示法 „ 5.2.3 动态结点表示法 „ 5.2.4 动态“左子/右兄弟”二叉链表表示法 „ 5.2.5 父指针表示法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 5.2.1 子结点表表示法 A 1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 J 4 2 3 4 5 6 7 8 9 索引 值 父节点 0 1 2 3 4 5 6 7 8 9 „ 第140页图5.6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 5.2.2 左子结点/右兄弟结点表示法 第140页图5.7 值 父 右兄弟 1 A 左子 结点 3 B 0 2 6 C 0 D 1 4 8 E 1 5 F 1 G 2 7 H 2 I 4 9 J 4 I J E F G A B C D H A’ X 11 A' X 10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 5.2.3 动态结点表示法 第142页图5.9 大小 A B 3 I J E F G A B C D H 2 值 C 2 D 0 E 2 F 0 G H 0 I 0 J 0 （a）树 （b）树的实现 0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 第142页图5.10 动态表示法 J I E F G A B C D H （a）树 （b）树的实现 A B D E F I J C G H 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 5.2.4 动态“左子/右兄弟”二叉链表 „ 左结点/右兄弟：最常用

Parento函数的算法效率? template * leftmostchild=pointer; Tree:: Parent(TreeNodek current) pointer=root; //返回 current结点的父结点 TreeNode* pointer=current; return NULL; else return getParent( pointer, leftmostchild) if(pointer !=NULL) return NULL; TreeNode* 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 TreeNode* Tree::Parent(TreeNode* current) {//返回current结点的父结点 TreeNode* pointer=current; if(pointer !=NULL) return NULL; TreeNode* 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

等价类的并查 ( UNION/FIND)算法 用树来表示等价类的并查 FIND ■“ UNION/FIND算法用一棵树代表一个集合 判斷两个结点是否在同一个集合中 集合用父结点代替 查找一个给定结点的根结点 如果两个结点在同一棵树中,则认为它们在同一个集合中 UNION 结点中仅需保存父指针信息 如果一个等价的两个元素不在同一棵树中 存储为一个以其结点为元亲的数组一静态 归并两个集合,这个归并过程常常被称 北大啦 机新有,食 大息单 张铭 有,盛 UNION/FIND算法示例()4UNN/FND算法示例(2) 例:10个结点A、B、C、D、E、F、G、H、J、K 首先对这5个等价对进行处理(AB)、(cK)、(F)、 和它们的等价关系(AB)、(cK)、,F)、 (HE)、(D,G) 后四个等价对处理同 (HE)、(D,G)、《KA)、(E,G)、(H刀) (AL B) (A, B)C,K, FXE,H)D, G) 1 D 如@@o23508① NBcK|GH可 北大位 张 新有,究 张铭鷾 叔有,印鱼究 UNION/FIND算法示例(2) 父指针表示法的树结点定义 然后对两个等价对(K,A)和(E,G)进行处理 template class harTree Node 己是根节点,A 以网属材罢合并 //树结点定义 4|5|6 /结点的值 ABCKDEFGHBOPG ParTreenode* parent;//父結点指针 ncount//以此结点为根的子树的总结点个数 Par'TreeNodeO; /构造函数 virtual~ ParTreeNode(};//析构函数 新有,食邮岛究 张铭

9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 等价类的并查 （UNION/FIND）算法 „ FIND „ 判断两个结点是否在同一个集合中 „ 查找一个给定结点的根结点 „ UNION „ 如果一个等价的两个元素不在同一棵树中 „ 归并两个集合，这个归并过程常常被称为 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 用树来表示等价类的并查 „ “UNION/FIND”算法用一棵树代表一个集合 „ 集合用父结点代替 „ 如果两个结点在同一棵树中，则认为它们在同一个集合中 „ 树 „ 结点中仅需保存父指针信息 „ 存储为一个以其结点为元素的数组——静态指针数组 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 UNION/FIND算法示例(1) 例：10个结点A、B、C、D、E、F、G、H、J、K 和它们的等价关系(A,B)、(C,K) 、(J,F) 、 (H,E) 、(D,G) 、(K,A) 、(E,G) 、(H,J) A B C K D E F G H J 01 89 2 3 4 5 6 7 A B C K D E F G H J 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 UNION/FIND算法示例(2) 首先对这5个等价对进行处理 (A,B)、(C,K) 、(J,F) 、 (H,E) 、(D,G) A C F E D B K J H G (A,B) 01 89 2 3 4 5 6 7 A B C K D E F G H J 0 (C,K) 2 (J,F)(E,H)(D,G) 后四个等价对处理同 （A，B） 4 5 6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 UNION/FIND算法示例(2) 然后对两个等价对（K，A）和（E，G）进行处理 A C F E D B K J H G 01 8 2 3 4 5 6 7 9 A B C K D E F G H J 0 2 4 5 6 K所在树的根为C，A自 (K,A) 己是根节点，A！=C, 所以两颗树要合并 (E,G) 同(K,A) 0 4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 父指针表示法的树结点定义 template class ParTreeNode { //树结点定义 private: T value; //结点的值 ParTreeNode* parent;//父结点指针 int nCount;//以此结点为根的子树的总结点个数 public: ParTreeNode(); //构造函数 virtual ~ParTreeNode(){}; //析构函数

父指针表示法的树定义 getvalue O; /返回结点的值 template oid setvalue( const T&val);//设量结点的值 class harTree //返回父结点指针 ParTreeNode* getParent(; //设量父结点指针 oid setParent( ParTreeNode* par) ParTreenode*aray;//存储树结点的数組 返回结点数目 //数組大小 nt get /查找node结点的根结点 设结点数目 ParTreenode* void setcount(const int count) Find( ParTreeNode* node)const 机新有,食 大息单 张铭邮露 有,盛 FIND算法 Hartree( const int size)//构造函数 template virtual NParTreeo //析构函数 ParTreenode* ParTree:: Find(ParTreeNode<>* node)const /把下标为i,j结点合并成一棵子树 void Union (int i, int j) Par TreeNode* pointer=node //判定下标为i,j的结点是否在一棵树中 while( pointer->getParentOI=NULL) pointer=pointer->getParento; bool Different(int i, int j; return pointer; 北大位 张 新有,究 张铭鷾 叔有,印鱼究 Different算法 UNION算法 template template bool ParTree: Different(int i, int ]) n( int i, int D) /找到结点的根 ParTreeNodek * pointer= Find(&array[i] pointer=Find(& array[i])//找到结点的根 /找到结点的根 ParTreeNode * pointerj=Find(&array UD) ParTreeNode* pointer=Find(&aray[j]/找到结点的根 ∥应用置量权衡合并规则 return pointer=pointerj; if(pointeri->getCount(>=pointerj->getCounto) 物歌抗 新有,食邮岛究 张铭

10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 T getValue(); //返回结点的值 void setValue(const T& val);//设置结点的值 //返回父结点指针 ParTreeNode* getParent(); //设置父结点指针 void setParent(ParTreeNode* par); //返回结点数目 int getCount(); //设置结点数目 void setCount(const int count); }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 父指针表示法的树定义 template class ParTree { //树定义 public: ParTreeNode* array;//存储树结点的数组 int Size; //数组大小 //查找node结点的根结点 ParTreeNode* Find(ParTreeNode* node) const; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 ParTree(const int size); //构造函数 virtual ~ParTree(); //析构函数 //把下标为i，j的结点合并成一棵子树 void Union(int i,int j); //判定下标为i，j的结点是否在一棵树中 bool Different(int i,int j); }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 FIND算法 template ParTreeNode* ParTree::Find(ParTreeNode* node) const { ParTreeNode* pointer=node; while ( pointer->getParent()!=NULL) pointer=pointer->getParent(); return pointer; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 Different算法 template bool ParTree::Different(int i,int j) { ParTreeNode* pointeri=Find(&array[i]);//找到结点i的根 ParTreeNode* pointerj=Find(&array[j]);//找到结点j的根 return pointeri!=pointerj; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 UNION算法 template void ParTree::Union(int i,int j) { //找到结点i的根 ParTreeNode* pointeri=Find(&array[i]); //找到结点j的根 ParTreeNode* pointerj=Find(&array[j]); if(pointeri!=pointerj) { // 应用重量权衡合并规则 if(pointeri->getCount()>=pointerj->getCount()) { pointerj->setParent(pointeri);