6.1树的概念与实现树-算法竞赛（Python进阶-数据结构与算法）课件

什么是树 数据结构与算法（Python版） ❖ 本章我们来讨论一种基本的“非线性 ”数 据结构——树； ❖ 树在计算机科学的各个领域中被广泛应用 操作系统、图形学、数据库系统、计算机网络 ❖ 跟自然界中的树一样 ， 数据结构树也分为： 根、 枝和叶等三个部分 一般数据结构的图示把根放在上方，叶放在下方 数据结构与算法（Python版） 树的例子 树的例子：生物学物种分类体系 数据结构与算法（Python版） 0 ❖ 首先分类体系是 层次化的 树是一种分层结构 越接近顶部的层越 普遍 越接近底部的层越 独特 界、门、纲、目、 科、属、种 树的例子：生物学物种分类体系 数据结构与算法（Python版） 0 ❖ 分类树的第二个特征： 一个节点的子节点 与另一个节点的子节点相互之间是隔离、 独立的 猫属Felis和蝇属Musca下面都有Domestica的 同名节点 但相互之间并无任何关联，可以修改其中一个 Domestica而不影响另一个。 树的例子：生物学物种分类体系 数据结构与算法（Python版） 0 ❖ 分类树的第三个特征： 每一个叶节点都具 有唯一性 可以用从根开始到达每个种的完全路径来唯一标 识每个物种 动物界->脊索门->哺乳纲->食肉目->猫科->猫 属->家猫种 Animalia->Chordate->Mammal->Carnivora- >Felidae->Felis->Domestica 树的例子：生物学物种分类体系 数据结构与算法（Python版） 0 数据结构与算法（Python版） 树的例子：文件系统 0 树的例子： HTML文档（嵌套标记） 数据结构与算法（Python版） 0 数据结构与算法（Python版） 树的例子：域名体系 0 ❖ 首先我们尝试用Python List来实现二叉 树树数据结构； ❖ 递归的嵌套列表实现二叉树 ， 由具有3个 元素的列表实现： 第1个元素为根节点的值； 第2个元素是左子树（所以也是一个列表）； 第3个元素是右子树（所以也是一个列表）。 数据结构与算法（Python版） 实现树：嵌套列表法 ❖ 以右图的示例 ， 一个6节点的二叉树 根是myTree[0]，左子树myTree[1]，右子树 myTree[2] ❖ 嵌套列表法的优点 子树的结构与树相同，是一种递归数据结构 很容易扩展到多叉树，仅需要增加列表元素即可 数据结构与算法（Python版） 实现树：嵌套列表法 0 ❖ 我们通过定义一系列函数来辅助操作嵌套 列表 BinaryTree创建仅有根节点的二叉树 insertLeft/insertRight将新节点插入树中作 为其直接的左/右子节点 get/setRootVal则取得或返回根节点 getLeft/RightChild返回左/右子树 数据结构与算法（Python版） 实现树：嵌套列表法 0 数据结构与算法（Python版） 嵌套列表法代码 0 数据结构与算法（Python版） 嵌套列表法代码 0 数据结构与算法（Python版） 实现树：嵌套列表法 0 $$