数据结构与算法“树”教学设计 北京大学信息科学技术学院王腾蛟 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 小时