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

4.1树情景导入PART1树的概念与特性一树的概念树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合树在计算机领域中也有广泛应用，在编译系统中，用树表示源程序的语法结构。在数据库系统中，树形结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。一树的概念树是由n（n≧0）个节点构成的一个有限集合以及在该集合上定义的一种节点关系。节点：集合中的元素。空树：n=0的树。子树：树中某个节点下面的所有节点所构成的树。边：一颗具有n个节点的树有n-1条边。二基本术语·节点的度：树的一个节点所拥有的子树个数。·树的度：最大的节点的度。二基本术语·根节点：没有前驱的节点。·叶子节点：度为0的节点。·分支节点：度不为0的节点。·父节点或双亲节点：上端节点称为下端节点的父节点。·孩子节点：下端节点称为上端节点的孩子节点·兄弟节点：具有同一父节点的节点二基本术语·节点的层数：树中节点从根开始计算，根的层数为1，其他节点的层数等于父节点层数加1·树的高度或深度：树中节点的最大层数。根的层数为1。第1层第2层第3层第4层树的深度二基本术语·森林：0个或多个不相交的树的集合ABC练习【例1】(1)该树共有个

节点，

条边。(2)根节点的名称是

它有

个孩子节点，节点E.(选填:是/不是)根节点的孩子节点.(3)节点A和节点B的度分别是

,整棵树的度是

。(4)该树的分支节点的数量是

，叶子节点的数量是

。(5)节点C的层数是

，树的深度是

。(6)节点D的父节点是

，兄弟节点是

，孩子节点是

。109A3不是3、334623AB、CI、JPART2二叉树一二叉树的概念二叉树是一种特殊的树，是由n（n≧0）个节点构成的一个有限集合，且各个节点的度小于或等于2，二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。ABCDEFGHABCDEFGH≠二二叉树的形态AABAC(1)空二叉树(2)只有根节点的单点树(3)只有根节点和左子树(4)只有根节点和右子树ABC(5)左右子树均非空三特殊二叉树1.完全二叉树设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。ABCDEGHIFJ(1～h-1)层

第h层三特殊二叉树2.满二叉树每一层都是满的，每个节点的度要么是2，要么为0，而且所有叶子节点都在同一层。ABCDEGF练习【例2】观察如图所示的二叉树示意图，下列说法正确的是( ）A.这是一棵完全二叉树B.这是一棵满二叉树C.这棵二叉树的深度是4D.这棵二叉树的度是4C四二叉树的性质1.二叉树的第i层上最多有

（i>=1）个节点。2.深度为h的二叉树最多有

（h>=1）个节点。3.在任意一棵二叉树中，若其叶子节点的数量为n0，度为2的节点数量为n2，则

。ABCDEGHIFJ

ABCDEGF四二叉树的性质4.具有n个结点的完全二叉树的深度

。5.给定n个节点，能构成

种不同的二叉树。ABCDEGHIFJABCDEGF

练习【举一反三1】已知二叉树T共有10个节点,其中度为1的节点数量为3,则叶子节点数量为()A.3B.4C.5D.6B练习【举一反三2】某棵树有5个节点,树的度和深度均为3,请画出这棵树所有可能的形态。练习【举一反三3】已知某二叉树总共有7个节点,其中叶子节点的个数为4,叶子节点的数据分别为1,2,3,4;每个双亲节点的数据值均为其孩子节点数据值之和。(1)该二叉树的深度为

。(2)该二叉树根节点的数据值为

。(3)若考虑叶子节点不同的排列情况,则该二叉树有

种画法。(4)请画出2棵符合条件的二叉树。31024练习一棵完全二叉树上有1001个节点，其中叶子节点的个数是（

）A.250B.500C.505D.501D练习一棵高度为4的完全二叉树上至少有（

）个节点A.15B.7C.8D.168PART3哈夫曼树一哈夫曼树4382路径：树中两个节点之间所经过的分支路径长度：一条路径上的分支数节点的权：给二叉树中的节点赋一个值节点带权路径长度：从根节点到一个节点的路径长度与该节点的权值的乘积树的带权路径长度：一棵树中所有叶子节点的带权路径长度之和WPL的公式：最优二叉树：在具有n个带权叶子节点的所有二叉树中，称带权路径长度WPL最小的二叉树为最优二叉树。在最优二叉树中权值较大的节点离根节点较近。

练习如图所示三棵树中哪棵树