河池学院：《数据结构》课程电子教案（PPT教学课件）第7章 树和二叉树 7.1 树

第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

树是由n（n≥0）个结点组成的有限集合（记为T）。 如果n=0，它是一棵空树，这是树的特例。 如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点 （root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、.、 Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。 2/36

树是一种非线性数据结构，具有以下特点： 每一结点可以有零个或多个后继结点，但有且只有一个前驱结 点（根结点除外）。 数据结点按分支关系组织起来，清晰地反映了数据元素之间的 层次关系。 3/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

树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结 构，非常直观和形象。 A B C D E F H G 5/36

文氏图表示法。使用集合以及集合的包含关系描述树结构。 A B C D E F H G 6/36

凹入表示法。使用线段的伸缩关系描述树结构。 A B C D E F H G 7/36

括号表示法。将树的根结点写在括号的左边，除根结点之外的其 余结点写在括号中并用逗号分隔。 A(B,C(E(H),F),D(G)) A B C D E F H G 根(子树1，子树2， .，子树m） 8/36

度为3 度为1 结点的度。树中每个结点具有的子树数或者后继结点数称为该结 点的度。 A B C D E F H G 9/36

树的度。树中所有结点的度的最大值称之为树的度。 树的度为3 A B C D E F H G 10/36