《数据结构》课程教学资源（PPT课件讲稿）第六章 树与二叉树（6.1-6.3）

第六章树与二叉树 2007.9

2007.9 第六章 树与二叉树

61树的定义和基本概念 62二叉树 62.1二叉树的定义和基本术语 622二叉树的性质 62.3二叉树的存储结构 6.3遍历二叉树 6.31遍历二叉树 6.32线索二叉树 64树和森林 64.1树的存储结构 64.2森林与二叉树的转换 64.3树和森林的遍历 6.5哈夫曼树及哈夫曼编码

 6.1 树的定义和基本概念  6.2 二叉树 6.2.1 二叉树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构  6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树  6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历  6.5 哈夫曼树及哈夫曼编码

61树的定义和基本概念

6.1 树的定义和基本概念

树的定义 树(Tree是nn>=0)个结点的有限集T,T为空时称为空树, 否则它满足如下两个条件: (1)有且仅有一个特定的称为根(ROO的结点; 2)其余的结点可分为mm>=0个互不相交的子集 2,T3…Tm,其中每个子集又是一棵树,并称其为子树 Subtree)。 AICG D E( H K M

树的定义 树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树， 否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2) 其余的结点可分为m(m>=0)个互不相交的子集 T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树 (Subtree)。 I J A B C D E F G H K L M

树的基本概念 结点(node) 根结点(root)、叶子/叶结点(eaf) 孩子结点( child)、双亲结点( parent) 兄弟( brother) 度( degree 结点的度 树的度:max(结点的度) 树的深度/高度( depth):max(结点的层次) 有序树/无序树 ●森林( forest)

树的基本概念  结点（node）  根结点（root）、叶子/叶结点（leaf）  孩子结点（child）、双亲结点（parent）、 兄弟（brother）  度（degree）  结点的度  树的度：max(结点的度)  树的深度/高度（depth）：max（结点的层次）  有序树/无序树  森林（forest）

62二叉树

6.2 二叉树

621二叉树的定义和基本术语 二叉树的定义 是一颗空树 或是由根及两颗不相交的左子树、右子树构成,并且 左、右子树本身也是二叉树。 A A A A B B B C (b) 空二叉树根和空的左右根和左子树根和右子树 根和左右子树 子树

6.2.1 二叉树的定义和基本术语  二叉树的定义  是一颗空树  或是由根及两颗不相交的左子树、右子树构成，并且 左、右子树本身也是二叉树。 (a) 空二叉树 A A B A B A C B (b) 根和空的左右 子树 (c) 根和左子树 (d) 根和右子树 (e) 根和左右子树

说明 1)二叉树中每个结点最多有两颗子树;二叉树每个 结点度小于等于2; 2)左、右子树不能颠倒—有序树; 3)二叉树的定义是递归结构,在二叉树的定义中又 用到了二叉树的概念;

 说明 1）二叉树中每个结点最多有两颗子树；二叉树每个 结点度小于等于2; 2）左、右子树不能颠倒——有序树; 3）二叉树的定义是递归结构，在二叉树的定义中又 用到了二叉树的概念;

叉树的逻辑结构 叉树的五种基本形态

二叉树的逻辑结构 A F G D E B C A G D E C B F φ 二 叉 树 的 五 种 基 本 形 态

521二叉树的概念 两种特殊的二叉树 1)满二叉树:如果深度为k的二叉树,有2k-1个结点则称为满二 叉树; A B DE F G K=2的满二叉树 K=3的满二叉树

两种特殊的二叉树 1)满二叉树：如果深度为k的二叉树，有2 k-1个结点则称为满二 叉树； A D E F G B C A B C K=3的满二叉树 K=2的满二叉树 5.2.1 二叉树的概念