师：同学们好，在这节课中，我们将学习数据与结构的第二课时。开始新课前，先回顾上一课时内容。上节课我们学习了数据结构中的线性结构，其中数据元素存在一对一的关系，还学习了典型线性结构——队列，它是操作受限制的线性结构，特点是只能在队尾依次添加元素，在队首依次出队。这节课我们要了解数据结构中的两种非线性结构：树结构和图结构。

　　上节课分析过网络购物路线，这节课主要聚焦物流运输和快递员派送两个环节。先来看快递员派送。大家都熟悉快递员，他们负责把快递送到离家最近的快递站点。现在站在快递员角度思考：快递到达本市后，他如何移动派送？请同学们思考，一分钟作答。

　　可以这样总结：每个快递员有一块固定区域，负责从快递派送点取件，再分配到各个小区保安室或快递柜，让顾客自行领取。接下来，请同学们拿出纸和笔，用点表示派送点、学校收发室以及收件人，用线段表示快件移动路线，画一个图。

　　画好图后，我们来连线，从派送点到学校收发室，从派送点到某单位传达室。到学校收发室后，由个人去领取，单位传达室同理。这个例子就是今天要讲的典型树结构。观察这张图，它有个明显特征——具有层次性。A点涵盖范围宽泛，越往下每个顶点涵盖范围越精细。将数据结构中的树结构和生活中的树对比，它们有相似之处，都有根、枝、叶，但不同在于，图中树结构的根节点在A点，是倒过来的树，根在顶部，叶子在底部。

　　从树的顶层可以到达任何一个顶点，移动的路线就形成一个路径。下面来看树的定义：树是由n个节点组成的组合，当n = 0时，称为空树；当n ≠ 0，即非空树，需满足两个条件：一是仅有一个根节点，二是剩余节点可分为m个互不相交的独立集合，这些集合本身又是一棵小树。观察这张图，从大范围讲，A是整棵树的根节点，从小范围看，B又是这棵小树的根节点，大结构和小结构是一致的。

　　下面了解树的术语。可以这样描述这棵树：节点A为根节点，B、C、D是节点A子树的根节点，对应的E、F、G是B子树的根节点。反过来，B是E、F、G的父节点，这种父子关系和现实中相似。和线性结构对比，线性结构数据元素是一对一，而树结构是一对多，同学们要记住这点。

　　接下来尝试用Python语言表示树。今天以包含一个根节点和两个子节点的树为例，用嵌套列表表示。列表大家之前学过，用列表表示简单树，可分别写根、左子树和右子树，如果左子树也是一棵树，再嵌套一个列表表示。比如这里加个方括号，里面结构和外面一致。

　　请同学们拿出纸和笔，尝试补全这棵树的嵌套列表表示。这里已给出前一部分范例，思考在D后面应该填什么。这里空括号表示什么呢？之前讲树的定义时说过，节点个数为0时称其为空树，这里就代表D的左子树和右子树都是空树，可用空括号表示。同学们，补全代码了吗？我们来看补全结果。

　　以B和以C为根节点的子树结构类似，所以可按上面一行模仿写出下面一行。即C节点的两个子树的根节点分别是F和G，F和G的子树是空树。通常写的时候可写成一行，为方便同学们初期学习，也可分行写。

　　用Python语言表示好树后，请同学们思考，要取出树A的左子树该怎么写？这要用到之前学的列表索引，列表索引从0开始。思考一下怎么表示A的左子树。思考完毕，来看结果。

　　左子树可观察例子得知，列表从0开始编号，左子树取用的索引是1，所以写为mytree[1]，输出结果就是mytree中A的左子树，包含B节点、D节点和E节点。接下来给大家一个挑战，怎么取出树B的右子树？可看下面列出的索引编号，因为列表是嵌套的，要先定位到B子树，再在B里找到其右子树，表示出来就是mytree[1][2]。对照例子理解，mytree是整棵树，[1]定位到树B，再[2]定位到右子树。同学们理解了吗？接下来看通常树有哪些操作。

　　建立数据结构是为方便取用数据，现在列出几种树的操作：一是获取树的根值，二是设置树的根值，三是获取树的左子树，四是获取树的右子树。还是以一个根节点和两个子节点的树为例，索引分别是1和2。

　　下面看几个生活中树结构的例子。第一个是行政区划分，我国行政区划分，国家之下有各省、直辖市，省里面有市、县、区，区下面有街道、乡镇，这种划分结构本质就是树结构。

　　第二个是网页的超文本标记语言，如果用过网页标记语言，会发现其架构很像树。比如最顶层标签是html，把网页分成头部（head）和身体（body）部位，再往下分成其他元素。