《数据结构》 第六章树和二叉树 (重点)
《数据结构》 第六章 树和二叉树 （重点）
第六章树和三叉树 第六章树和二叉树 内容树、二叉树、森林的概念和性质,树与 叉树的转换,树形结构的存储,遍历,哈夫 曼树的概念及应用 要求通过学习和上机,深刻理解树形结构的 递归特性,为应用它解决实际问题奠定理论基础 并获得实践经验。理解并准确叙述棡、二叉树、 森林及其有关概念并熟悉它们的基本性质,熟悉 树形结构的存储结构和中序线素二又树,熟悉树 的遍历方法,尤其是二叉树的前序、中序和后序 遍历的递归与应用,知道树形结构的若干应用 第2页
第六章 树和二叉树 第2页 第六章 树和二叉树 内容 树、二叉树、森林的概念和性质，树与 二叉树的转换，树形结构的存储，遍历，哈夫 曼树的概念及应用。 要求 通过学习和上机，深刻理解树形结构的 递归特性，为应用它解决实际问题奠定理论基础 并获得实践经验。理解并准确叙述树、二叉树、 森林及其有关概念并熟悉它们的基本性质，熟悉 树形结构的存储结构和中序线索二叉树，熟悉树 的遍历方法，尤其是二叉树的前序、中序和后序 遍历的递归与应用，知道树形结构的若干应用
第六章树和三叉树 第六章树和二叉树 重点 1、树、二叉树的概念和性质 2、树结构的存储 3、树和二叉树的遍历算法以及树的前序 中序和后序遍历算法 难点 1、树形结构的存储方法 2、中序线索树 3、二叉树遍历的非递归算法 4、树的应用 第3页
第六章 树和二叉树 第3页 重点 1、树、二叉树的概念和性质 2、树结构的存储 3、树和二叉树的遍历算法以及树的前序、 中序和后序遍历算法 难点 1、树形结构的存储方法 2、中序线索树 3、二叉树遍历的非递归算法 4、树的应用 第六章 树和二叉树
树的结构定义 第六章树和三叉树 一树的逻辑结构—它定义一类重要的非线性结构 树结构在计算机科学的很多领域都得到了广泛的应用。 树结构可应用于诸如 编译程序中表示源程序的语法结构一 数据库系统中的信息组织 文件目录 电路分析 社会各个组织和管理机构 家谱 书的章节编目 军队编制 树型结构是结点之间有分支、层次关系的结构,它 非常类似于自然界中的树。树型结构在客观世界中大量 存在。 第4页
第六章 树和二叉树 第4页 树的逻辑结构——它定义一类重要的非线性结构。 树结构在计算机科学的很多领域都得到了广泛的应用。 树结构可应用于诸如 编译程序中表示源程序的语法结构 数据库系统中的信息组织 文件目录 电路分析 社会各个组织和管理机构 家谱 书的章节编目 军队编制 树型结构是结点之间有分支、层次关系的结构，它 非常类似于自然界中的树。树型结构在客观世界中大量 存在。 ⚫ 树的结构定义
树的结构定义 第六章树和三叉树 定义1树Tree=(D,R)是一种层次数据结构,其中D是具有相 一同特性的数据元素(称为树结点)的有限集合,R是定义在D上 的二元关系。在这种关系中,有且仅有一个特定的无前趋的结 点(称为树的根,记作root),其余的每一个结点有且仅有一个 直接前趋 注.树的这种结构对每一个结点的后继不加限制,任何一个 结点都可以有0至多个后继结点 定义2(树的递归定义)树是n(n21)个结点的有限集合,一 其中 (1)有且仅有一个特定的称之为根(rot的结点; (2)其余的结点可分为m(m≥0)个互不相交的集合T1,T2 Tn,而每一个集合本身又是一棵树,并且称为根的子树( sub tree)。 为了讨论方便,有时也将结点数为0的空集合也看成树,并 称之为空树。 第5页
第六章 树和二叉树 第5页 定义1 树Tree=(D,R)是一种层次数据结构，其中D是具有相 同特性的数据元素（称为树结点）的有限集合，R是定义在D上 的二元关系。在这种关系中，有且仅有一个特定的无前趋的结 点（称为树的根，记作root），其余的每一个结点有且仅有一个 直接前趋。 注. 树的这种结构对每一个结点的后继不加限制，任何一个 结点都可以有0至多个后继结点。 定义2 （树的递归定义）树是n(n≥1)个结点的有限集合， 其中 (1) 有且仅有一个特定的称之为根（root）的结点； (2) 其余的结点可分为m(m ≥0)个互不相交的集合T1 ,T2 ,… ，Tm，而每一个集合本身又是一棵树，并且称为根的子树（ sub tree）。 为了讨论方便，有时也将结点数为0的空集合也看成树，并 称之为空树。 ⚫ 树的结构定义