《数据结构》 第六章树和二叉树 (重点)
《数据结构》 第六章 树和二叉树 （重点）
第六章树和三叉树 第六章树和二叉树 内容树、二叉树、森林的概念和性质,树与 叉树的转换,树形结构的存储,遍历,哈夫 曼树的概念及应用 要求通过学习和上机,深刻理解树形结构的 递归特性,为应用它解决实际问题奠定理论基础 并获得实践经验。理解并准确叙述棡、二叉树、 森林及其有关概念并熟悉它们的基本性质,熟悉 树形结构的存储结构和中序线素二又树,熟悉树 的遍历方法,尤其是二叉树的前序、中序和后序 遍历的递归与应用,知道树形结构的若干应用 第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的空集合也看成树，并 称之为空树。 ⚫ 树的结构定义
0树的表示 第六章树和三叉树 树的表示示例 (A (A 仅有根纪 8 (BC D 点的树 EF A BC ⊙6c e M 般树 树的结点:一个个的记录 d 树的枝或边:指向其他结点的指针 二叉树 第6页
第六章 树和二叉树 第6页 树的表示示例 A B C A B C D E F － + / a e f b － c d A 仅有根结 点的树 一般树 A B C D E F H J K L G I M 二叉树 树的结点：一个个的记录 树的枝或边：指向其他结点的指针 ⚫ 树 的 表 示
0树的表示 第六章树和三叉树 非树表示示例 不是树,因为它 没有一个根结点 不是树,因为其中的一 个结点有两个前趋结点 )不是树,因为它是不相交的 两棵树的集合。它是森林 第7页
第六章 树和二叉树 第7页 非树表示示例 不是树，因为它 没有一个根结点 不是树，因为其中的一 个结点有两个前趋结点 不是树，因为它是不相交的 两棵树的集合。它是森林 ⚫ 树 的 表 示
0树的表示 第六章树和三叉树 一树的其它三种表示方法 文氏图表示法 D 用集合的嵌套 ⑩/① 即包含关系来表示 广义表表示法 用嵌套括号表示 根作为由子树森林组成的表的名字写在表的左边 (A(B(E(K,L),F),C(G), D(H(M, ID)) 第8页
第六章 树和二叉树 第8页 树的其它三种表示方法 文氏图表示法 用集合的嵌套 即包含关系来表示 广义表表示法 用嵌套括号表示。 根作为由子树森林组成的表的名字写在表的左边 (A(B(E(K,L),F),C(G), D(H(M),I,J))) A E K L F B H M I J D G C ⚫ 树 的 表 示
0树的表示 第六章树和三叉树 凹入表示法 类似于书的编目,即分成章节、小节,分别缩进表示 A B E K豸 L F H M多 J象第 第9页
第六章 树和二叉树 第9页 凹入表示法 类似于书的编目，即分成章节、小节，分别缩进表示 A B E K L F C G D H M I J ⚫ 树 的 表 示
树的葚本术语 第六章树和三叉树 以如图所示的一棵树为范例 A) B 结点(noe)树中的的一个独立单 元。它包括一个信息项和若干个指示其 他树结点的位置信息。结点的信息项可 K 包含一个关键字和其他的数据项。常用圆圈内的一个字母或数字表 示该结点的信息项或关键字,并用来标识该结点,如结点A,结点 B。 根(root)树唯一无前趋(前件)的结点,如结点A。有时也 用根结点标记整棵树,称其为树A 结点的度( degree of node)结点拥有的子树(或后件)数 如结点A的度为3,B的度为2,C的度为1,D的度为3,E的度为2 ,F的度为0,等等。 树的度( degree of tree)树内各结点度的最大值,如示例树 的度为3。 第10页
第六章 树和二叉树 第10页 以如图所示的一棵树为范例 结点（node）树中的的一个独立单 元。它包括一个信息项和若干个指示其 他树结点的位置信息。结点的信息项可 包含一个关键字和其他的数据项。常用圆圈内的一个字母或数字表 示该结点的信息项或关键字，并用来标识该结点，如结点A，结点 B。 根（root）树唯一无前趋（前件）的结点，如结点A。有时也 用根结点标记整棵树，称其为树A。 结点的度（degree of node）结点拥有的子树（或后件）数。 如结点A的度为3，B的度为2，C的度为1，D的度为3，E的度为2 ，F的度为0，等等。 A B C D E F H J K L G I M ⚫ 树 的 基 本 术 语 树的度（degree of tree）树内各结点度的最大值，如示例树 的度为3