4.1 树与二叉树的概念及其性质 课件（共19张PPT）2022—2023学年浙教版（2019）高中信息技术选修1

4.1 树与二叉树 01 PART 认识树与二叉树 Click here to add your title 试分析左图的数据结构 你是如何确定该数据结构的？ 可从以下概念进行分析描述： 孩子、父节点（双亲节点）、兄弟、祖先、子孙 树的定义： 由n(n≥0)个节点 构成的一个有限集合以及在该集合上定义的一种节点关系，集合中的元素称为树的节点，n=0的树称为空树。 树的概念及性质： （1）对于一颗具有n个节点的树，它有n-1条边 （2）度：树的一个节点所拥有的子树的个数，最大结点的度称为树的度。 （3）没有前驱结点称为根节点。度为0的结点称为叶节点（终端节点） （4）树中节点的层数从根算起，根的层数为1，其余节点层数等于其父节点的层数加1，树中节点的最大层数称为树的高度或深度。 练习 分别找出这颗树共有多少条边？树的度？树的深度？根节点，叶子节点。C节点的父节点，兄弟节点，孩子节点？ 二叉树 在猜数字游戏中，甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。 乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果，具体过程可以抽象成下图的二叉树结构。 50 25 12 37 6 18 31 43 75 62 56 68 88 82 96 小 小 小 小 小 小 小 大 大 大 大 大 大 大 二叉数的基本概念 二叉树是n（n≥0）个结点的有限集合： ① n = 0时，二叉树是一棵空树。。 ② 当n ≠ 0时，二叉树是由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。 二叉数的特点 ①每个结点至多只有两棵子树。 ②左右子树不能颠倒（二叉树是有序树） 二叉数的五种状态 特殊的二叉树—满二叉树 满二叉树：每一层的节点数都达到最大值 特殊的二叉树--完全二叉树 当且仅当其每个结点都与高度为h的满二叉树中的结点一一对应时，称为完全二叉树 特点： ①只有最后两层可能有叶子结点 ②最多只有一个度为1的结点 特殊的二叉树 不是完全二叉树 完全二叉树如果某结点只有一个孩子，一定是左孩子 该二叉树是完全二叉树吗？ 二叉数的性质 ①二叉树第i层至多有2i?1个结点（i≥1） ? ②深度为k的二叉树多有2k?1个结点（i≥1） ? 第 1 层：20 第 2 层：21 第 3 层：22 第 4 层：23 二叉数的性质 ③在任意一棵二叉树中，若度为2的节点数量为n2， 叶子节点数为n0，则n0＝n2＋1（叶子节点比分支节点多一个） 哈夫曼树 特殊的二叉树 Teshu de erchashu 哈夫曼树 特殊的二叉树 Teshu de erchashu 练一练 请从下列三棵二叉树中找到最优二叉树 ①WPL=2*2+4*2+5*2+8*2=38 ②WPL=4*2+5*3+8*3+2*1=49 ③WPL=8*1+5*2+2*3+4*3=36 CREATIVE FASHION GENERAL PPT TEMPLATE 谢谢！ ... ...