4.2二叉树的基本操作 课件 -2022-2023学年浙教版（2019）高中信息技术选修1

4.1树与二叉树 选修一数据结构 知识回顾 该树的度为5— 体现一棵树的宽度 该树的深度为4—体现一棵树的高度 根节点/分支节点 A A节点的度为5，孩子节点为BCDEF B F节点的父节点为A 层数为2 分支节点 叶子节点 叶子节点 分支节点 叶子节点 /内部节点 /内部节点 叶子节点 叶子节点 分支节点 叶子节点 /内部节点 G、H为兄弟节点 叶子节点 叶子节点 知识回顾 ①二叉树的第k层上最多有2k-1(k>=1)个节点。 ②深度为k的二叉树最多有2k-1(k>=1)个节点。 ③在任意一棵二叉树中，若度为2的节点数量为2，叶子节点数为no, 则no=n2+1 知识回顾 1.满二叉树 2.完全二叉树 ◆特点： ◆特点： ①每个节点的度为2或者度为0 ①至多只有最下两层中的节点的度小于2 ②所有叶子节点都在同一层 ②最下一层的叶子节点都依次排列在该 层最左边位置 甲满二叉树 甲完全二叉树 练习 5.一棵完全二叉树上有1000个节点，其中叶子节点的个数是 (500) 特殊二叉树 哈夫曼树 路径：树中两个节点之间所经过的分支 路径长度：一条路径上的分支数 节点的权：给二叉树中的节点赋一个值 节点带权路径长度：从根节点到一个节点的路径长度与该节点的权值 的乘积 树的带权路径长度：一棵树中所有叶子节点的带权路径长度之和 WPL的公式： W:×P 最优二叉树：在具有个带权叶子节点的所有二叉树中，称带权路径长 度WPL最小的二叉树为最优二叉树。在最优二叉树中权值较大的节点 离根节点较近。 练习 12.若二叉树的叶节点带有权值，则叶节点的权值乘以其到根节点的长度（即边数）称 为带权路径长度。在具有个带权叶节点（带权节点指带有权值的节点）的所有二叉 树中，所有叶节点带权路径长度之和最小的二叉树称为最优二叉树。若有3个叶节点 A,B,C,权值分别为5,6,7，则对应的最优二叉树如图所示。其带权路径长度之和为29( 计算方法是5*2+6*2+7*1) 根据以上知识请回答下列问题. (1)若有4个叶节点A、B、C、D,权值分别为3,4,5,6，则其带权路径长度之和为(B) A.35 B.36 C.37 D.38 (2)根据对最优二叉树的定义可知，个节点权值确定时，最优二叉树是唯一的： 错误 (选填：正确/错误) (3)叶节点编码的过程中，叶节点的权值越大，离根节点的路径长度（从根节点到叶节点 经过的边数)越短 (选填越长越短) 练习 3 3 5 06 5 6 满二叉树/完全二叉树 完全二叉树 完全二叉树 ★满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 ★满二叉树度为1的节点一定是0个。 ★完全二叉树度为1的节点一定是0/1个。 二叉数的存储结构——顺序存储 概念：建立二叉树的操作，按照层的顺序进行，每一层中按照从左 到右的顺序创建节点。可以用数组或者数据结构来实现。 1、数组实现 (1）完全二叉树 ★节点编号与数组下标一一对应 二叉数的存储结构 顺序存储 1、数组实现 (2)非完全二叉树 A 补全为完全二叉树 B B 原二叉树 补全后的二叉树 0 1234567 A B C