4.1树课件-浙教版高中信息技术选修1.pptx

4.1树 情景导入 PART 1 树的概念与特性 一 树的概念 树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合 树在计算机领域中也有广泛应用，在编译系统中，用树表示源程序的语法结构。在数据库系统中，树形结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。 一 树的概念 树是由n（n≧0）个节点构成的一个有限集合以及在该集合上定义的一种节点关系。 节点：集合中的元素。 空树：n = 0 的树。 子树：树中某个节点下面的所有节点所构成的树。 边：一颗具有 n 个节点的树有 n-1 条边。 二 基本术语 ·节点的度：树的一个节点所拥有的子树个数。 ·树的度：最大的节点的度。 二 基本术语 ·根节点：没有前驱的节点。 ·叶子节点：度为 0 的节点。 ·分支节点：度不为0的节点。 ·父节点或双亲节点：上端节点称为下端节点的父节点。 ·孩子节点：下端节点称为上端节点的孩子节点 ·兄弟节点：具有同一父节点的节点 二 基本术语 ·节点的层数：树中节点从根开始计算，根的层数为1，其他节点的层数等于父节点层数加1 ·树的高度或深度：树中节点的最大层数。根的层数为1。 第1层 第2层 第3层 第4层 树的深度 二 基本术语 ·森林：0个或多个不相交的树的集合 练习 【例1】(1)该树共有个 节点， 条边。 (2)根节点的名称是 它有 个孩子节点，节点E . (选填:是/不是)根节点的孩子节点. (3)节点A和节点B的度分别是 ,整棵树的度是 。 (4)该树的分支节点的数量是 ，叶子节点的数量是 。 (5)节点C的层数是 ，树的深度是 。 (6)节点D的父节点是 ，兄弟节点是 ，孩子节点是 。 10 9 A 3 不是 3、3 3 4 6 2 3 A B、C I、J PART 2 二叉树 一 二叉树的概念 二叉树是一种特殊的树，是由n（n≧0）个节点构成的一个有限集合，且各个节点的度小于或等于2，二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。 ≠ 二 二叉树的形态 A (1)空二叉树 (2)只有根节点的单点树 (3)只有根节点和左子树 (4)只有根节点和右子树 (5)左右子树均非空 三 特殊二叉树 1.完全二叉树 设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 (1～h-1) 层 第 h 层 三 特殊二叉树 2.满二叉树 每一层都是满的，每个节点的度要么是2，要么为0，而且所有叶子节点都在同一层。 练习 【例2】观察如图所示的二叉树示意图，下列说法正确的是( ） A.这是一棵完全二叉树 B.这是一棵满二叉树 C.这棵二叉树的深度是4 D.这棵二叉树的度是4 C 四 二叉树的性质 1.二叉树的第i层上最多有 （i=1）个节点。 2.深度为h的二叉树最多有 （h=1）个节点。 3.在任意一棵二叉树中，若其叶子节点的数量为n0，度为2的节点数量为n2，则 。       四 二叉树的性质 4.具有 n 个结点的完全二叉树的深度 。 5.给定n个节点，能构成 种不同的二叉树。     练习 【举一反三1】已知二叉树T共有10个节点,其中度为1的节点数量为3,则叶子节点数量为() A.3 B.4 C.5 D.6 B 练习 【举一反三2】某棵树有5个节点,树的度和深度均为3,请画出这棵树所有可能的形态。 练习 【举一反三3】已知某二叉树总共有7个节点,其中叶子节点的个数为4,叶子节点的数据分别为1,2,3,4;每个双亲节点的数据值均为其孩子节点数据值之和。 (1)该二叉树的深度为 。 (2)该二叉树根节点的数据值为 。 (3)若考虑叶子节点不同的排列情况,则该二叉树有 种画法。 (4)请画出2棵符合条件的二叉树。 3 10 24 练习 一棵完全二叉树上有1001个节点，其中叶子节点的个数是（ ） A.250 B.500 C.505 D.501 D 练习 一棵高度为4的完全二叉树上至少有（ ）个节点 A.15 B.7 C.8 D.16 8 PART 3 哈夫曼树 一 哈夫曼树 路径：树中两个节点之间所经过的分支 路径长度：一条路径上的分支数 节点的权：给二叉树中的节点赋一个值 节点带权路径长度：从根节点到一个节点的路径长度与该节点的权值 的乘积 树的带权