数据结构与算法“树”教学设计 北京大学信息科学技术学院王腾蛟 1.树在课程中的定位和前测知识点 树形结构是元素之间具有分层关系的结构,它类似于自然界中的树,是一类很重要的非 线性数据结构。一方面,计算机应用中,常出现嵌套的数据,树结构提供了对该类数据的自 然表示;另一方面,利用树结构,可以有效地解决一些算法问题。因此,树形结构有广泛应 用。树形结构常采用递归方式定义,被称为递归数据结构,有关树的许多算法是递归的。 树这一章重点介绍了链式存储和顺序存储。在树的链式存储单元介绍了子结点表示法 左子结点/右兄弟结点表示法、动态结点表示法、父指针表示法等,在树的顺序存储单元介 绍了带右链的先根次序表示法、带双标记位的先根次序表示法、带左链的层次次序表示法等, 本章的末尾还简单介绍了K叉树的概念 前测知识点要求如下,可以根据需要给学生补充 (1)二叉树的存储实现。 (2)二叉树的周游。 2.学习目标 (1)理解树和森林的基本概念 (2)掌握树与二叉树的联系、区别与转换 (3)掌握树的链式存储方法,重点掌握“左子结点/右兄弟结点”二叉链表和父指针表示 法,理解各种算法的优缺点 (4)掌握树的顺序存储方法 (5)理解K叉树的概念和性质 3.知识点和学时分配 理论授课2学时,建议安排实验4学时。 各知识点建议授课时间如下: 树的定义和基本术语0.5小时 树的链式存储结构 0.5小时 树的顺序存储结构 0.5小时
1 数据结构与算法“树”教学设计 北京大学信息科学技术学院 王腾蛟 1. 树在课程中的定位和前测知识点 树形结构是元素之间具有分层关系的结构，它类似于自然界中的树，是一类很重要的非 线性数据结构。一方面，计算机应用中，常出现嵌套的数据，树结构提供了对该类数据的自 然表示；另一方面，利用树结构，可以有效地解决一些算法问题。因此，树形结构有广泛应 用。树形结构常采用递归方式定义，被称为递归数据结构，有关树的许多算法是递归的。 树这一章重点介绍了链式存储和顺序存储。在树的链式存储单元介绍了子结点表示法、 左子结点/右兄弟结点表示法、动态结点表示法、父指针表示法等，在树的顺序存储单元介 绍了带右链的先根次序表示法、带双标记位的先根次序表示法、带左链的层次次序表示法等， 本章的末尾还简单介绍了 K 叉树的概念。 前测知识点要求如下，可以根据需要给学生补充 （1）二叉树的存储实现。 （2）二叉树的周游。 2．学习目标 （1） 理解树和森林的基本概念。 （2） 掌握树与二叉树的联系、区别与转换。 （3） 掌握树的链式存储方法，重点掌握“左子结点/右兄弟结点”二叉链表和父指针表示 法，理解各种算法的优缺点。 （4） 掌握树的顺序存储方法。 （5） 理解 K 叉树的概念和性质。 3. 知识点和学时分配 理论授课 2 学时，建议安排实验 4 学时。 各知识点建议授课时间如下： 树的定义和基本术语 0.5 小时 树的链式存储结构 0.5 小时 树的顺序存储结构 0.5 小时
K叉树及知识点总结 0.5小时 4.重点和难点 (1)掌握树与二叉树的联系、区别与转换。 (2)掌握树的链式存储方法和顺序存储方法,及各自的优缺点。 5.授课提示 采用灵活的教学方式,通过提出问题、分析问题、解决问题这样的基本流程,加深学生 对重难点知识的理解,并培养其创新意识和创新能力 下面是树这一章的重点和难点内容的讲授注意事项 (1)森林与二叉树的等价转换 树与二叉树、森林与二叉树之间可以相互转化,而且这种转换是一一对应的。树和森林 转化成二叉树后,那么森林或树的相关操作都可以转换成对二叉树的操作。 树和森林到二叉树的转换过程可用连线、切线、旋转“三步曲”来说明 连线:将兄弟结点用线连接起来。 切线:保留父结点与其第一个子结点的连线,将父结点到其它子结点的连线切掉。 旋转:以根为轴,平面向下顺时针方向旋转一定的角度。旋转只是为了调整画面,使得 转化后的二叉树看起来比较规整。 而二叉树转换为树或森林,就是上面三步曲的逆操作。 这种转换过程应多举例,并且用图片展示转换过程。 (2)父指针表示法 由于树中每一个结点的父指针是唯一的,所以父指针表示法可以唯一地表示任何一棵 树。在这种表示方法下,寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点 出发找出一条向上延伸到达其祖先的路径,即从一个结点到其父亲结点,再到其祖父结点等 等。求祖先路径所需要的时间正比于路径上的结点个数,因此父指针表示法对于求树根结点 的运算非常方便。 合并两棵树的操作也非常简单,只需要将一棵树的树根表示为另一棵树的子结点,也就 是设置父指针值即可。 父指针表示求结点的子结点和兄弟结点就比较麻烦,需要查询整个结构。另外,这种存 储结构中没有表示出结点之间的左右次序。父指针表示法适合于无序树的情况,而且只适合 于查询结点的根和合并树等操作,其主要优点是节省存储空间而且操作便捷。 (3)等价类和并查集 父指针表示法的一个重要应用是实现并查集( Union/ Find)。并查集是一种特殊的集合
2 K 叉树及知识点总结 0.5 小时 4．重点和难点 （1） 掌握树与二叉树的联系、区别与转换。 （2） 掌握树的链式存储方法和顺序存储方法，及各自的优缺点。 5．授课提示 采用灵活的教学方式，通过提出问题、分析问题、解决问题这样的基本流程，加深学生 对重难点知识的理解，并培养其创新意识和创新能力。 下面是树这一章的重点和难点内容的讲授注意事项 (1) 森林与二叉树的等价转换 树与二叉树、森林与二叉树之间可以相互转化，而且这种转换是一一对应的。树和森林 转化成二叉树后，那么森林或树的相关操作都可以转换成对二叉树的操作。 树和森林到二叉树的转换过程可用连线、切线、旋转“三步曲”来说明： 连线：将兄弟结点用线连接起来。 切线：保留父结点与其第一个子结点的连线，将父结点到其它子结点的连线切掉。 旋转：以根为轴，平面向下顺时针方向旋转一定的角度。旋转只是为了调整画面，使得 转化后的二叉树看起来比较规整。 而二叉树转换为树或森林，就是上面三步曲的逆操作。 这种转换过程应多举例，并且用图片展示转换过程。 (2) 父指针表示法 由于树中每一个结点的父指针是唯一的，所以父指针表示法可以唯一地表示任何一棵 树。在这种表示方法下，寻找一个结点的父结点只需要 O(1)时间。在树中可以从一个结点 出发找出一条向上延伸到达其祖先的路径，即从一个结点到其父亲结点，再到其祖父结点等 等。求祖先路径所需要的时间正比于路径上的结点个数，因此父指针表示法对于求树根结点 的运算非常方便。 合并两棵树的操作也非常简单，只需要将一棵树的树根表示为另一棵树的子结点，也就 是设置父指针值即可。 父指针表示求结点的子结点和兄弟结点就比较麻烦，需要查询整个结构。另外，这种存 储结构中没有表示出结点之间的左右次序。父指针表示法适合于无序树的情况，而且只适合 于查询结点的根和合并树等操作，其主要优点是节省存储空间而且操作便捷。 (3) 等价类和并查集 父指针表示法的一个重要应用是实现并查集(Union/Find)。并查集是一种特殊的集合
由一些不相交子集构成,合并查集的基本操作是 I)Find:判断两个结点是否在同一个集合中; 2) Union:归并两个集合 像栈、队列一样,并査集也是一种重要的抽象数据类型,可以用于求解等价类问题, 划分等价类需要对集合进行三种操作: I)构造只含有一个元素的集合; 2)判定某个元素所在的子集,目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类,对于同一个集合中的元素返回相同的结果,否则返回不同的结果; 3)归并两个不相交的集合为一个集合 由于用根结点表示子集的类别,那么“查找”某一个元素所属的集合,只要从该结点出 发,沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。 每次合并前都需要进行两次查找,查找所需要的时间由树的高度决定,合并所需的时间 为0(1)。容易看出,在最坏情况下,合并可能使n个结点的树退化成一条链。 为了防止树退化为单链,应该让每个结点到其相应根结点的距离尽可能小,可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目,然后令含成 员少的子集的树根指向含成员多的子集的根,称作“重量权衡合并规则”( weighted union rue)。把小树合并到大树中去,可以把树的整体深度限制在O(ogn,每次Find操作只需要 O(ogn)时间。 另一个办法是采用路径压缩( path compression)技术。在执行Find操作时,把结点到 树根的路径上所有结点的父指针都指向根结点。路径压缩可以缩短结点与根之间的路径 (4)带双标记的层次次序表示 由层次次序的性质可知,任何结点的子结点都排在该结点的所有兄弟结点后面。并且 任何结点的最后一个兄弟结点不会再有下一个兄弟,即最后一个兄弟的rtag为1。由结点的 层次次序以及ltag、rtag两个标志位,就可以确定树的左孩子/右兄弟链表中结点的link和 rik值。rik的值很容易确定:结点的rag为1,则rik为空;结点的rtag为0,则rink 指向该结点紧邻的下一个结点 当一个结点x的tag为0时,其lnk不空,应该指向结点序列中排在结点x的兄弟结 点后面的那个结点y。由于跟层次序列相关,需要使用队列。顺序扫描树的层次序列,若结 点的ltag值为1时,则置其link为空;否则把该结点x放入队列。如果遇到tag为1的结 点,这时该结点的兄弟结点链已经扫描完毕,下一个将要扫描的结点y就是结点x的最左孩
3 由一些不相交子集构成，合并查集的基本操作是： 1) Find：判断两个结点是否在同一个集合中； 2) Union：归并两个集合。 像栈、队列一样，并查集也是一种重要的抽象数据类型，可以用于求解等价类问题。 划分等价类需要对集合进行三种操作： 1) 构造只含有一个元素的集合； 2) 判定某个元素所在的子集，目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类，对于同一个集合中的元素返回相同的结果，否则返回不同的结果； 3) 归并两个不相交的集合为一个集合。 由于用根结点表示子集的类别，那么“查找”某一个元素所属的集合，只要从该结点出 发，沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。 每次合并前都需要进行两次查找，查找所需要的时间由树的高度决定，合并所需的时间 为 O(1)。容易看出，在最坏情况下，合并可能使 n 个结点的树退化成一条链。 为了防止树退化为单链，应该让每个结点到其相应根结点的距离尽可能小，可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目，然后令含成 员少的子集的树根指向含成员多的子集的根，称作“重量权衡合并规则”（weighted union rule）。把小树合并到大树中去，可以把树的整体深度限制在Ｏ(logn)，每次 Find 操作只需要 O(logn)时间。 另一个办法是采用路径压缩（path compression）技术。在执行 Find 操作时，把结点到 树根的路径上所有结点的父指针都指向根结点。路径压缩可以缩短结点与根之间的路径。 (4) 带双标记的层次次序表示 由层次次序的性质可知，任何结点的子结点都排在该结点的所有兄弟结点后面。并且 任何结点的最后一个兄弟结点不会再有下一个兄弟，即最后一个兄弟的 rtag 为 1。由结点的 层次次序以及 ltag、rtag 两个标志位，就可以确定树的左孩子/右兄弟链表中结点的 llink 和 rlink 值。rlink 的值很容易确定：结点的 rtag 为 1，则 rlink 为空；结点的 rtag 为 0，则 rlink 指向该结点紧邻的下一个结点。 当一个结点 x 的 ltag 为 0 时，其 llink 不空，应该指向结点序列中排在结点 x 的兄弟结 点后面的那个结点 y。由于跟层次序列相关，需要使用队列。顺序扫描树的层次序列，若结 点的 ltag 值为 1 时，则置其 llink 为空；否则把该结点 x 放入队列。如果遇到 rtag 为 1 的结 点，这时该结点的兄弟结点链已经扫描完毕，下一个将要扫描的结点 y 就是结点 x 的最左孩
子,此时取出队列的第一个元素(即先前保存的x),将其Ⅲink指向y即可 6.课后练习和实习 将书本上的理论知识与最前沿的技术知识融为一体,设计验证型、探索型、应用型的 实习题和上机题,帮助同学更好的理解书本上的基本原理,锻炼学生的思维能力、实践能力。 树这一章可以安排7-9道书面作业,1-2道综合上机实习题。安排一次习题讲评 例如:实现并查集方面的考察。 使用重量权衡合并规则与路径压缩,对下列从0到15之间的数的等价对进行归并,并 给出所得树的父指针表示法的数组表示。在初始情况下,集合中的每个元素分别在独立的等 价类中。当两棵树规模同样大时,使结点值较大的根结点作为值较小的根结点的子结点。 (0,2)(1,2)(3,4)(3,1)(3,5)(9,11)(12,14)(3,9) 4,14)(6,7)(8,10)(8,7)(7,0)(10,15)(10,13) 7.教学案例 划分等价类需要对集合进行三种操作 (1)构造只含有一个元素的集合 (2)判定某个元素所在的子集,目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类,对于同一个集合中的元素返回相同的结果,否则返回不同的结果; (3)归并两个不相交的集合为一个集合 用父指针表示的树形结构实现的并査集可以很容易地解决等价类问题。约定森林F T,T2,…,T}表示集合S,森林中的每一棵树T表示集合S的一个子集,树中的结点表 示集合S中的一个元素。树中的每一个非根结点都指向其父结点,用根结点作为集合的标 识符。 (a) 集合的表示方法
4 子，此时取出队列的第一个元素(即先前保存的 x)，将其 llink 指向 y 即可。 6．课后练习和实习 将书本上的理论知识与最前沿的技术知识融为一体，设计验证型、探索型、应用型的 实习题和上机题，帮助同学更好的理解书本上的基本原理，锻炼学生的思维能力、实践能力。 树这一章可以安排 7-9 道书面作业，1-2 道综合上机实习题。安排一次习题讲评。 例如：实现并查集方面的考察。 使用重量权衡合并规则与路径压缩，对下列从 0 到 15 之间的数的等价对进行归并，并 给出所得树的父指针表示法的数组表示。在初始情况下，集合中的每个元素分别在独立的等 价类中。当两棵树规模同样大时，使结点值较大的根结点作为值较小的根结点的子结点。 (0，2) (1，2) (3，4) (3，1) (3，5) (9，11) (12，14) (3，9) (4，14) (6，7) (8，10) (8，7) (7，0) (10，15) (10，13) 7．教学案例 划分等价类需要对集合进行三种操作： (1) 构造只含有一个元素的集合； (2) 判定某个元素所在的子集，目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类，对于同一个集合中的元素返回相同的结果，否则返回不同的结果； (3) 归并两个不相交的集合为一个集合。 用父指针表示的树形结构实现的并查集可以很容易地解决等价类问题。约定森林 F = {T1，T2，„，Tr}表示集合 S，森林中的每一棵树 Ti表示集合 S 的一个子集，树中的结点表 示集合 S 中的一个元素。树中的每一个非根结点都指向其父结点，用根结点作为集合的标 识符。 1 3 5 7 2 4 6 2 1 4 6 3 5 7 (a) (b) (c) S1 S2 S3 8 8 集合的表示方法
由于用根结点表示子集的类别,那么“查找”某一个元素所属的集合,只要从该结点出 发,沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。例如,上图(a)和(b)中的两棵树分别表示子集S1={1,3,5,7}和S2={2, 4,6,8}。图中的(c)就实现了S3=S1US2 SS, S (a)n个集合 (b)合并操作 合并操作的一个极端情况 每次合并前都需要进行两次查找,查找所需要的时间由树的高度决定,合并所需的时间 为O(1)。容易看出,在最坏情况下,合并可能使n个结点的树退化成一条链。下面就是 个例子。将上图(a)表示的子集合并时,每次都把集合元素多的根结点指向含元素少的根结 点,经过n-1次合并操作后得到的树的高度就为n,如上图(b所示。 为了防止树退化为单链,应该让每个结点到其相应根结点的距离尽可能小,可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目,然后令含成 员少的子集的树根指向含成员多的子集的根,称作“重量权衡合并规则”( weighted union le)。把小树合并到大树中去,可以把树的整体深度限制在O(logn),每次Find操作只需要 O(ogn)时间。 树的父指针表示与 Union/find算法实现 class Par TreeNode i 树结点类定义 ∥结点的值 ParTreeNode "p ∥父结点指针 n Count: ∥子树元素数目 Par TreeNodeo ∥构造函数 virtual -Par TreeNodeoti ∥析构函数 get Value ∥/返回结点的值
5 由于用根结点表示子集的类别，那么“查找”某一个元素所属的集合，只要从该结点出 发，沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。例如，上图(a)和(b)中的两棵树分别表示子集 S1 = {1，3，5，7}和 S2 = {2， 4，6，8}。图中的(c)就实现了 S3 = S1∪S2。 每次合并前都需要进行两次查找，查找所需要的时间由树的高度决定，合并所需的时间 为 O(1)。容易看出，在最坏情况下，合并可能使 n 个结点的树退化成一条链。下面就是一 个例子。将上图(a)表示的子集合并时，每次都把集合元素多的根结点指向含元素少的根结 点，经过 n - 1 次合并操作后得到的树的高度就为 n，如上图(b)所示。 为了防止树退化为单链，应该让每个结点到其相应根结点的距离尽可能小，可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目，然后令含成 员少的子集的树根指向含成员多的子集的根，称作“重量权衡合并规则”（weighted union rule）。把小树合并到大树中去，可以把树的整体深度限制在Ｏ(logn)，每次 Find 操作只需要 O(logn)时间。 树的父指针表示与 Union/Find 算法实现 template class ParTreeNode { // 树结点类定义 private: T value; // 结点的值 ParTreeNode *parent; // 父结点指针 int nCount; // 子树元素数目 public: ParTreeNode(); // 构造函数 virtual ~ParTreeNode(){}; // 析构函数 T getValue(); // 返回结点的值 合并操作的一个极端情况 1 2 3 „„ n S1 S2 S3 Sn (a) n个集合 1 2 1 2 n 3 1 2 3 „ „„ (b) 合并操作
void set Value(const T& val) ∥设置结点的值 Par TreeNode"get ParentO ∥返回父结点指针 void setParent(Par TreeNode"par) ∥设置父结点指针 int getCounto ∥/返回结点数目 void setCount(const int count) ∥设置结点数目 ∥树类定义 Par TreeNode * array, 存储树结点的数组 Par TreeNode<>Find( Par Treenode* HarTree:Find( ParTreeNode·node) const{∥返回node结点的根结点 Par TreeNode*pointer=node ool Par Tree: Different( int i, int)i ∥判断结点i和j是否有相同的根结点 Par TreeNode *pointer=Find(&array) ∥找到结点i的根 Par TreeNode<>*pointerj= Find(&arrayal); ∥找到结点j的根 return pointer ∥若结点i和j的根结点不相同返回tu template Par TreeNode pointer= Find( &array; ∥找到结点i的根 ∥找到结点j的根 interj-setParent( pointer) ∥把结点i设置为j的父结点 ntO,∥设置结点数目 else i ∥把结点j设置为i的父结点 pointer]-> setCount(pointer-> getCounto+ pointerj-> getCounto,∥设置结点数目
6 void setValue(const T& val); // 设置结点的值 ParTreeNode* getParent(); // 返回父结点指针 void setParent(ParTreeNode *par); // 设置父结点指针 int getCount(); // 返回结点数目 void setCount(const int count); // 设置结点数目 }; template class ParTree { // 树类定义 public: ParTreeNode *array; // 存储树结点的数组 int Size; // 数组大小 ParTreeNode* Find(ParTreeNode *node)const; // 查找 node 结点的根结点 ParTree(const int size); // 构造函数 virtual ~ParTree(); // 析构函数 void Union(int i,int j); // 把下标为 i，j 的结点合并成一棵子树 bool Different(int i,int j); // 判断结点 i 和 j 是否有相同的根结点 }; template ParTreeNode* ParTree::Find(ParTreeNode *node) const { // 返回 node 结点的根结点 ParTreeNode *pointer = node; while (pointer->getParent() != NULL) pointer = pointer->getParent(); return pointer; } template bool ParTree::Different(int i,int j) { // 判断结点 i 和 j 是否有相同的根结点 ParTreeNode *pointeri = Find(&array[i]); // 找到结点 i 的根 ParTreeNode *pointerj = Find(&array[j]); // 找到结点 j 的根 return pointeri != pointerj; // 若结点 i 和 j 的根结点不相同返回 true } template void ParTree::Union(int i,int j) { ParTreeNode *pointeri = Find(&array[i]); // 找到结点 i 的根 ParTreeNode *pointerj = Find(&array[j]); // 找到结点 j 的根 if (pointeri != pointerj) { if (pointeri->getCount() >= pointerj->getCount()) { pointerj->setParent(pointeri); // 把结点 i 设置为 j 的父结点 pointeri->setCount(pointeri->getCount()+pointerj->getCount()); // 设置结点数目 } else { pointeri->setParent(pointerj); // 把结点 j 设置为 i 的父结点 pointerj->setCount(pointeri->getCount()+pointerj->getCount()); // 设置结点数目
加速并査集运算的另一个办法是采用路径压缩( path compression)技术。在执行Find 操作时,把结点到树根的路径上所有结点的父指针都指向根结点。例如下图(a)表示了依次 合并集合{7,9,10}、{5,6,8}、{2,4}和{1,3}后所形成的树。下图b)表示出了查找结 点7的根时,对结点7到根所涉及的结点进行压缩路径之后的树形态。路径压缩可以缩短结 点与根之间的路径。 (a)路径压缩之前 (b)路径压缩之后 路径压缩示例 带路径压缩的 FindPC算法 template Par TreeNode' Par Tree FindPC(Par TreeNode *node)const i f (node->getParentO=NULL) node->setParent(FindPC(node->get ParentO) return node->getParentO 路径压缩大大加速了Find运算。在执行 Union时总是将小树并到大树上,而且在执行 Find时实行路径压缩,则可以证明n次Find至多需要O(n(n)时间。其中α(n)是单变量 Ackermann函数的逆,它是一个增长速度比logn慢得多但又不是常数的函数。在实际应用 中,α(n)往往小于4。因此,执行一串交错的合并和查找操作所需要的时间几乎与合并和查 找的次数成线性关系。上述路径压缩算法是目前最有效的并查集实现方法 8.总结 树”这一章介绍了树以及森林的概念、术语及表示方法。联系到树形结构的具体应用, 在存储器中有许多不同的表示树形结构的方法。本章重点介绍了链式存储和顺序存储。在树
7 } } } 加速并查集运算的另一个办法是采用路径压缩（path compression）技术。在执行 Find 操作时，把结点到树根的路径上所有结点的父指针都指向根结点。例如下图(a)表示了依次 合并集合{7，9，10}、{5，6，8}、{2，4}和{1，3}后所形成的树。下图(b)表示出了查找结 点 7 的根时，对结点 7 到根所涉及的结点进行压缩路径之后的树形态。路径压缩可以缩短结 点与根之间的路径。 带路径压缩的 FindPC 算法 template ParTreeNode* ParTree::FindPC(ParTreeNode *node) const { if (node->getParent() == NULL) return node; node->setParent(FindPC(node->getParent())); return node->getParent(); } 路径压缩大大加速了 Find 运算。在执行 Union 时总是将小树并到大树上，而且在执行 Find 时实行路径压缩，则可以证明 n 次 Find 至多需要 O(nα(n))时间。其中 α(n)是单变量 Ackermann 函数的逆，它是一个增长速度比 logn 慢得多但又不是常数的函数。在实际应用 中，α(n)往往小于 4。因此，执行一串交错的合并和查找操作所需要的时间几乎与合并和查 找的次数成线性关系。上述路径压缩算法是目前最有效的并查集实现方法。 8．总结 “树”这一章介绍了树以及森林的概念、术语及表示方法。联系到树形结构的具体应用， 在存储器中有许多不同的表示树形结构的方法。本章重点介绍了链式存储和顺序存储。在树 路径压缩示例 1 2 3 4 5 6 7 8 9 10 （a）路径压缩之前 （b）路径压缩之后 1 2 4 3 5 6 8 7 9 10
的链式存储单元介绍了子结点表表示法、左子结点/右兄弟结点表示法、动态结点表示法 父指针表示法等,在树的顺序存储单元介绍了带右链的先根次序表示法、带双标记位的先根 次序表示法、带左链的层次次序表示法等,本章的末尾还简单介绍了K叉树的概念 树形结构是一种重要的非线性结构。一方面,它为计算机应用中常出现的嵌套数据提供 了自然的表示;另一方面,它在解决各种算法问题中也有广泛的应用。 参考文献 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月 通高等教育“十一五”国家级规划教材。 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkueducn/pkujpk/course/sjjg/ 4.张乃孝、裘宗燕,《数据结构—C++与面向对象的途径》,高等教育出版社,1998.年6
8 的链式存储单元介绍了子结点表表示法、左子结点/右兄弟结点表示法、动态结点表示法、 父指针表示法等，在树的顺序存储单元介绍了带右链的先根次序表示法、带双标记位的先根 次序表示法、带左链的层次次序表示法等，本章的末尾还简单介绍了 K 叉树的概念。 树形结构是一种重要的非线性结构。一方面，它为计算机应用中常出现的嵌套数据提供 了自然的表示；另一方面，它在解决各种算法问题中也有广泛的应用。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 张乃孝、裘宗燕，《数据结构——C++与面向对象的途径》，高等教育出版社，1998.年 6 月
