1、知识回顾知识回顾一个元素前面（或上面）只有一个元素，而后面（或下面）却有多个（0个或多个）元素相邻，所有的数据元素之间的特征就像一棵倒放的树。4.1树与二叉树浙江省高中信息技术 选择性必修一 数据与数据结构4.1.1 4.1.1 树树 树的概念 树的基本术语 树的特性1.树 的 概 念可以描述为由n（n=0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。u节点：集合中的元素树的概念与特性s h u d es h u d e g a i n i a n y u t e x i n g g a i n i a n y u t e x i n g节点节点节点节点2.树 的 基
2、 本 术 语树的概念与特性s h u d es h u d e g a i n i a n y u t e x i n g g a i n i a n y u t e x i n gu节点：u根节点：u叶子节点：u分支节点：u父节点：u孩子节点：u边：集合中的元素(开始节点)没有前驱的节点(终端节点)度为0的节点除叶子节点以外的节点(内部节点：除根节点之外的分支节点)(双亲节点)对于两个以边直接连接的节点中的上端节点连接两个节点之间的线对于两个以边直接连接的节点中的下端节点2.树 的 基 本 术 语树的概念与特性s h u d es h u d e g a i n i a n y u t e
3、x i n g g a i n i a n y u t e x i n gu节点：u根节点：u叶子节点：u分支节点：u父节点：u孩子节点：u边：AM，共13个节点A，1个C D F G H J K L M，9个A B E I，4个A B E I，4个12条B C D E F G H I J K L M，12个2.树 的 基 本 术 语u子树：u空树：u节点的度：u树的度：u节点的层数：u树的深度：树的概念与特性s h u d es h u d e g a i n i a n y u t e x i n g g a i n i a n y u t e x i n g树中某个节点下面所有节点所构成
4、的树节点数n=0的树树的一个节点所拥有的子树个数节点的度中的最大值从根开始计算，根的层数为1节点的层数中的最大值2.树 的 基 本 术 语u子树：u空树：u节点的度：u树的度：u节点的层数：u树的深度：树的概念与特性s h u d es h u d e g a i n i a n y u t e x i n g g a i n i a n y u t e x i n gB G H、G、H、C 共12颗子树没有节点节点A的度为5、节点B的度为2 5节点A在第一层，节点KLM在第四层43.树 形 结 构 特 点u非线性结构：在有多个节点的树形结构中，只有一个没有前驱、只有后继的根节点，可以有多个没
5、有后继、只有前驱的叶子节点，其余节点都只有一个直接前驱和多个直接后继u有限集合：节点个数是有限的树的概念与特性s h u d es h u d e g a i n i a n y u t e x i n g g a i n i a n y u t e x i n g练一练10109 9A A3 3不是不是3 3，3 33 34 46 62 23 3A AB CB CI JI J实践运用猜数游戏：现在有一个100以内的正整数，请猜测这个正整数是多少，每猜测一次，都会反馈“猜大了”或者“猜小了”，直到猜出正确结果，请问猜数的策略是什么？这个猜数策略有什么特点？二叉树二叉树 概念 性质 满二叉树 完
6、全二叉树 哈夫曼树1.二 叉 树 的 概 念u概念：是特殊的树，是一个具有n（n=0）个节点的有限集合。u特点：各节点的度都小于等于2 分为左子树和右子树，且左右子树有序二叉树的概念e r c h a s h u d ee r c h a s h u d e g a i n i a n g a i n i a n2.二 叉 树 的 形 态二叉树的概念e r c h a s h u d ee r c h a s h u d e g a i n i a n g a i n i a n空二叉树（n=0）只有根节点的单点树A只有根节点和右子树左右子树均非空只有根节点和左子树练一练请画出包含4个节点的所
7、有形态的二叉树。二 叉 树 的 第 k 层 上 最 多 有 2k-1（k =1）个 节 点。u应用：（1）如图所示，第1层上最多只有 个节点；第2层上最多只有 个节点，以此类推，第k层上最多只有 个节点。二叉树的性质e r c h a s h u d ee r c h a s h u d e x i n g z h i x i n g z h i122k-1 深 度 为 k 的 二 叉 树 最 多 有 2k-1（k =1）个 节 点。u应用：根据性质可知，第1层节点数最多为20。第2层节点数最多为21，以此类推，深度为k的二叉树节点最多有20+21+22+2k=2k-1（2）某二叉树深度为3，
8、则该二叉树最多有 个节点。二叉树的性质e r c h a s h u d ee r c h a s h u d e x i n g z h i x i n g z h i7在任意一棵二叉树中，若度为2的节点数量为n2，叶子结点数为n0，则n0=n2+1u应用：如图甲，度为2的节点数为1，叶子节点数为2；如图乙：度为2的节点数为 ，叶子节点数为 。二叉树的性质e r c h a s h u d ee r c h a s h u d e x i n g z h i x i n g z h i23在任意一棵二叉树中，若度为2的节点数量为n2，叶子结点数为n0，则n0=n2+1二叉树的性质e r c
9、h a s h u d ee r c h a s h u d e x i n g z h i x i n g z h i 深 度 为 k 的 二 叉 树 最 多 有 2k-1（k =1）个 节 点。二 叉 树 的 第 k 层 上 最 多 有 2k-1（k =1）个 节 点。练一练1、已知二叉树T共有10个节点，其中度为1的节点数量为3，则叶子节点数量为（）A.3 B.4 C.5 D.6B1.满 二 叉 树u特点：每个节点的度为2（具有两个非空子树），或者度数为0（叶子结点）所有叶子节点都在同一层特殊的二叉树T e s h u d e T e s h u d e e r c h a s h ue
10、 r c h a s h u1.满 二 叉 树u应用：根据二叉树性质可知：（1）满二叉树第k层上的节点数一定为 。（2）一个深度为k的满二叉树一定有 个节点。特殊的二叉树T e s h u d e T e s h u d e e r c h a s h ue r c h a s h u2k-12k-12.完 全 二 叉 树u特点：至多只有最下两层中的节点的度小于2 最下一层的叶子节点都依次排列在该层最左边位置特殊的二叉树T e s h u d e T e s h u d e e r c h a s h ue r c h a s h u2.完 全 二 叉 树u应用：根据二叉树性质可知：（1）一棵
11、深度为k的完全二叉树，第k-1层的节点个数为 。第k层的节点数 (填关系运算符)2k-1。（2）已 知 某 完 全 二 叉 树 有 2 0 0 个 节 点，则 该 二叉 树 的 高 度 为 。特殊的二叉树T e s h u d e T e s h u d e e r c h a s h ue r c h a s h u2k-2=8练一练满二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树3.哈 夫 曼 树特殊的二叉树T e s h u d e T e s h u d e e r c h a s h ue r c h a s h u3.哈 夫 曼 树特殊的二叉树T e s h u d e T e s h u d e e r c h a s h ue r c h a s h u练一练请从下列三棵二叉树中找到最优二叉树WPL=2*2+4*2+5*2+8*2=38WPL=4*2+5*3+8*3+2*1=49WPL=8*1+5*2+2*3+4*3=36
