第7章树和二叉树 提纲 CONTENTS 7.6线索二叉树 7.1树 7.7哈夫曼树 7.2二叉树 7.8二叉树与树、森林之间的转换 7.3二叉树先序、中序和后序遍历 7.9树算法设计和并查集 7.4二叉树的层次遍历 作业 7.5二叉树的构造 上机实验题 1/36
CONTENTS 提纲 1/36
7.1树树的定义7.1.1树是由n（n≥0）个结点组成的有限集合（记为T）如果n=0，它是一棵空树，这是树的特例。如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点（root），其余结点可分为m（m≥）个互不相交的有限集T1、T2、…Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。2/36
树是由n（n≥0）个结点组成的有限集合（记为T）。 如果n=0，它是一棵空树，这是树的特例。 如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点 （root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、.、 Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。 2/36
树是一种非线性数据结构，具有以下特点：每一结点可以有零个或多个后继结点，但有且只有一个前驱结点（根结点除外）。数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。3/36
树是一种非线性数据结构，具有以下特点： 每一结点可以有零个或多个后继结点，但有且只有一个前驱结 点（根结点除外）。 数据结点按分支关系组织起来，清晰地反映了数据元素之间的 层次关系。 3/36
抽象数据类型树的描述ADT Treet数据对象：D=ai| 0≤i≤n-1,n≥0,a,为E类型}数据关系：R=(r]r={|ai，ajED，0≤i，j≤n-1，其中每个结点最多只有一个前驱结点、可以有零个或多个后继结点，有且仅有一个结点即根结点没有前驱结点子基本运算：bool CreateTree()：由树的逻辑结构表示建立其存储结构。Stringtostring()：返回由树转换的括号表示串。EGetParent（inti）：求编号为i的结点的双亲结点值。4/36
ADT Tree { 数据对象： D={ai | 0≤i≤n-1，n≥0，ai为E类型} 数据关系： R={r} r={ | ai，aj∈D， 0≤i，j≤n-1，其中每个结点最多只有一个前驱 结点、可以有零个或多个后继结点，有且仅有一个结点即根 结点没有前驱结点 } 基本运算： bool CreateTree()：由树的逻辑结构表示建立其存储结构。 String toString()：返回由树转换的括号表示串。 E GetParent(int i)：求编号为i的结点的双亲结点值。 . } 抽象数据类型树的描述 4/36
树的逻辑结构表示方法7.1.2树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。5/36
树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结 构，非常直观和形象。 A B C D E F H G 5/36
文氏图表示法。使用集合以及集合的包含关系描述树结构。EH6/36
文氏图表示法。使用集合以及集合的包含关系描述树结构。 A B C D E F H G 6/36
凹入表示法。使用线段的伸缩关系描述树结构。MBCEHFDG7/36
凹入表示法。使用线段的伸缩关系描述树结构。 A B C D E F H G 7/36
括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。A(B,C(E(H),F),D(G))根（子树1，子树2，，子树m)8/36
括号表示法。将树的根结点写在括号的左边，除根结点之外的其 余结点写在括号中并用逗号分隔。 A(B,C(E(H),F),D(G)) A B C D E F H G 根(子树1，子树2， .，子树m） 8/36
树的基本术语7.1.31结点的度。树中每个结点具有的子树数或者后继结点数称为该结点的度。度为3度为19/36
度为3 度为1 结点的度。树中每个结点具有的子树数或者后继结点数称为该结 点的度。 A B C D E F H G 9/36
树的度。树中所有结点的度的最大值称之为树的度。树的度为310/36
树的度。树中所有结点的度的最大值称之为树的度。 树的度为3 A B C D E F H G 10/36