第六章树与二叉树 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 二叉树的概念