师：同学们，大家好。今天我们来学习高一信息技术必修一第三单元数据与结构中树和图的内容，这是3.2单元的第二课时。我们先了解一下本节课的学习目标：第一，了解树的概念和特征；第二，了解图的概念和特征；第三，掌握通过把图转化成树，也就是用枚举路径的方式来解决问题的基本方法。
首先，我们回顾一下上节课的知识。上节课我们学习了数据结构，它是存在特定关系的数据元素的集合。在解决某些问题时，相关联的数据会集中形成一个数据集合，这个集合可作为一个整体被访问或处理。数据结构分为线性数据结构和非线性数据结构。
线性数据结构就像排队，排成一列，除了队首和队尾的同学，每个同学前后都只有一人。课本图3.2.2中，红色的当前元素，前面的叫前驱元素，后面的叫后继元素。首元素无前驱，只有后继；尾元素无后继，只有前驱。线性数据结构最大特点是元素间数量关系为一对一，在图上能直观看到。比如队列，特点是先进先出（First In, First Out），和按规矩排队一样，要在队尾入队，队头出队，不能插队。再比如栈，特点是后进先出（Last In, First Out），只有一个出入口且出入口相同，先进去的元素会被后进去的挡住，后进去的先出栈，先进去的才能出栈。生活中有些停车场只有一条车道和一个出入口，管理员让车主留电话，就是因为先进入的车可能被后进入的车挡住，需要挪车，这和栈很相似。
接下来进入本节课学习内容——非线性数据结构。从名字可知，元素间数量关系不再是一对一，而是有更多变化。我们通过书本内容探讨非线性数据结构及其特点。
先看任务二探究快递的配送过程。每个快递员负责固定派送范围，从快递派送点取件后送到各自负责的快递领取点，如小区门卫、单位门卫或具体用户。我们用节点表示派送点、学校收发室和收件人员，用线段表示配送路线，就能用图形表示快递收发过程。
比如，快递员从快递发送点送快递到学校收发室，通知收件人员取件，A同学和B同学可去学校收发室取件。然后快递员又把快递送到某个单位的传达室，职工小王和职工小李可去单位传达室取件。
大家看这个图像什么？是不是像一棵倒挂的树？这棵树只有一个树根，即快递派送点。树根长出枝叶，枝叶最后是叶子，叶子不能再长枝叶。像A同学、B同学、职工小王、职工小李就是叶子节点，这种形态的数据结构叫树结构。
我们总结一下树结构的概念：树结构是一种具有层次关系的非线性结构，由n个节点组成有限集合，n≥0。当n = 0时，叫空树；若n≠0，就有明显层次结构。树有两个必要条件：一是仅有一个称为根的节点，如快递派送图中第一层的节点就是根节点，根节点有子节点，形成第二层，往下有第三层、第四层等；二是当n＞0时，其他节点可分为m个（m≥0）互不相交的有限集合，每个集合本身又是一棵树，称为根的子树。比如快递派送图中，派送点是根节点，它的左子树和右子树是两个互不相交的集合，且本身也是独立的树。
再看课本图3.2.3，这个树结构中A是根节点，有B、C、D三个子节点。父与子关系相对，B是A的子节点，同时是E、F、G三个节点的父节点。树的元素关系是一对多，除根节点外，每个节点只有一个父节点，但可有多个子节点。例如，B、C、D都只有一个父节点A，而节点B有E、F、G三个子节点，节点D有H、I、Z三个子节点，节点C没有子节点，是叶子节点。我们把以B为根节点的子树和以D为根节点的子树标示出来，它们是两个互不相交的集合，本身也各自是一棵完整的树。每个子树下面还可有自己的子树，比如以B为根节点的子树下，以G为根节点的子树。生活中，人事组织架构树清晰表现了管理层级关系，行政规划树以中国为根节点，湖北省是子节点，湖北省下有省会、地级市，市下有区，像武汉市有武昌区、汉阳区等，电脑里的资源管理器也是树状结构。