树、二叉树的概念及其性质一轮复习课件-2025-2026学年浙江省高三信息技术选修一

树、二叉树的概念及其性质 1 知识过关 2 1. 树的概念 树(Tree)可以描述为由n(n≥0)个节点(Node)构成的一个有限集合，以及在该集合上定义的一种节点关系。集合中的元素称为树的节点,n=0的树称为空树。 2. 树的相关概念及性质 (1)对于一棵具有n个节点的树,它有n－1条边。 (2)树的一个节点所拥有的子树个数称为该节点的度,最大的节点的度称为树的度。线性表是度为1的特殊树状结构。 (3)在树状结构中,没有前驱的节点称为根节点(Root),又称为开始节点。度为0的节点称为叶子节点(Leaf),它又称为终端节点。 3 (4)树中节点的层数从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的高度或深度(Depth)。 (5)在树状结构中,对于两个以边直接连接的节点,上端节点称为下端节点的父节点或双亲节点。相应地,下端节点称为上端节点的孩子节点。同一双亲节点的孩子节点之间互为兄弟节点。 3. 二叉树的概念 二叉树是一个具有n (n≥0)个节点的有限集合,它的所有节点的度都小于或等于2。当n=0时,二叉树是一棵空树;当n不等于0时,它是一棵由根节点和两棵互不相交的、分别称为这个根节点的左子树和右子树组成的二叉树。 4 4. 二叉树的相关概念及性质 (1)完全二叉树至多只有最下面两层中的节点度数小于2,最下面一层的叶子节点都依次排列在该层的最左边位置(如有缺少,则缺少的只能是最下层最靠右的连续元素)。 完全二叉树 5 (2)二叉树的性质。 ①二叉树的第k层上最多有2k－1(k≥1)个节点。 ②深度为k的二叉树最多有2k－1(k≥1)个节点。 ③在任意一棵二叉树中,若度为2的节点数量为n2,叶节点(度为0的节点)数量为n0,则n0=n2+1。 (3)具有n个结点的完全二叉树的深度为⌊log2n」+1。(注:⌊ 」表示向下取整) 6 典例精选 7 【例1】 关于二叉树,下列说法中错. 误. 的是(　　) A. 用数组的方式存储二叉树,容易造成空间浪费 B. 若有前序和中序遍历,可以推导出一棵唯一的二叉树 C. 只有最下面两层有叶子节点的二叉树称为完全二叉树 D. 完全二叉树的第3层有3个叶子节点,则该树的节点数量可能是8 【解析】 本题考查二叉树的存储、二叉树的遍历、完全二叉树的基本性质。完全二叉树除了要满足至多只有最下面两层中的节点度数小于2这一条件外,还需要符合最下面一层的叶子节点都依次排列在该层的最左边位置这一条件。C符合题意。 C 【例2】 在一棵二叉树上,第4层的节点数最多为(　　) A. 2 B. 4 C. 8 D. 16 【解析】 本题考查二叉树的性质。二叉树的第k层上最多有2k－1(k≥1)个节点,C正确。 C 【例3】 有一棵完全二叉树具有100个结点。下列说法中,正确的是(　　) A. 树的深度为8 B. 有1个节点只有非空左子树 C. 此完全二叉树有49个叶子结点 D. 有50个度为2的节点 【解析】 本题考查二叉树的基础知识。树的深度为7时,27－1就有127个节点,树的深度为7的话,就有127个节点了,深度不可能为8,A错误。(100－n1－1)/2,n1要么是0要么是1,总结点数为100,n1有1个,B正确。叶子节点有(100－n1－1)/2,n1的个数为1,所以叶子节点为50个,C错误。根据以上总结n0=50,n1=1,n2=49个,D错误。 B 自我检测 11 1. 下列选项中,不. 属. 于. 树状结构的是(　　) A. B. C. D. 【解析】 根据树的相关性质可知,n个节点的树通过n－1条边相连,B有3个节点,共有3条边,与树的性质不符,符合题意。 B 12 2. 下列关于树和二叉树的说法,错. 误. 的是(　　) A. 树是一种非线性的数据结构 B. 二叉树是树的特殊形式 C. 完全二叉树是二叉树的特例 D. 二叉树所有节点的度都是2 【解析】 二叉树所有节点的度都小于等于2,D符合题意。 D 13 3. 有一棵树,如图所示。 该树中,节点B的度和树的度分别为(　　) A. 2,4 B. 3,4 C. 3,5 D. 2,5 【解析】 本题考查节点的度和树的度的概念。 树的一个节点所拥有的子树个数称为该节点的 度,所以节点B的度为3。最大的节点的度称为 树的度,C节点的度最大为4,所以树的度是4。 B正确。 B 14 必备知识练 15 1. 下列选项中,属于非线性数据结构的是(　　) A. 二叉树 B. 队列 C. 栈 D. 数组 【解析】 二叉树是一种非线性的数据结构,A符合题意。 A 16 2. 下列选项中,最适合用树表示的是(　　) A. 有序的数据元素 B. 无序的数据元素 C. 元素间无任何联系的数据 D. 元素间具有分支层次关系的数据 【解析】 树的最大特点是可以描述具有分支层次关系的数据,D正确。 D 17 3. 已知某完全二叉树有2022个节点,则该二叉树的高度是(　　) A. 9 B. 10 C. 11 D. 12 【解析】 由完全二叉树的结点数n与高度h的关系为n=2h－1可知,h=[log22022]＋1=11,所以该完全二叉树的高度为11,C正确。 C 18 4. 某完全二叉树的节点数为20个,则其深度是(　　) A. 4 B. 5 C. 6 D. 7 【解析】 本题考查完全二叉树的性质。具有n个结点的完全二叉树的深度为[log220]＋1=5,模拟后可知,从上层到下层,其节点数分别为1＋2＋4＋8＋5=20,共5层,B正确。 B 19 5. 具有10个叶子节点的二叉树中,度为2的节点个数是(　　) A. 8 B. 9 C. 10 D. 11 【解析】 在任意一棵二叉树中,如果度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2＋1。因此,度为2的节点个数为10－1=9,B正确。 B 20 6. 在一棵二叉树上,第5层的节点数最多是(　　) A. 4 B. 8 C. 16 D. 32 【解析】 本题考查二叉树的性质。二叉树的第k层上最多有2k－1(k≥1)个节点,24=16,C正确。 C 21 7. 关于如图所示的树,下列说法中正确的是(　　) A. 该树中共有6个叶子节点 B. 该树的度为3,深度为4 C. E节点的父节点是A D. 节点I和J都是B的孩子节点 【解析】 该树中共有5个叶子节点;E节点的父节点是B; 节点I是D的孩子节点,节点J是E的孩子节点。B正确。 B 22 8. 一棵二叉树共有20个节点,其中5个是叶子节点,则度为1的节点数是(　　) A. 11 B. 10 C. 9 D. 8 【解析】 任意一棵二叉树节点度数都小于等于2(0、1、2),叶子节点数等于度为2的节点数＋1,所以度为1的节点数=20－5－4=11,A正确。 A 23 9. 在如图所示的4棵二叉树中,不. 是. 完全二叉树的是(　　) C A. B. C. D. 【解析】 完全二叉树最下面一层的叶子节点都依次排列在该层的最左边位置,C符合题意。 24 10. 已知一棵完全二叉树的节点总数为10个,则最后一层的节点数为(　　) A. 1 B. 2 C. 3 D. 4 【解析】 本题考查完全二叉树的特性。二叉树的节点总数为10个,则深度至少为4层,前三层分别为1＋2＋4=7,因此第四层节点数为10－7=3,B正确。 C 25 关键能力练 26 11. 某二叉树前序遍历为abdcef,中序遍历为dbaecf,则此二叉树的后序遍历为 (　　) A. dbefca B. debfca C. dfebca D. dbfeca 【解析】 本题考查二叉树的遍历。前序遍历为abdcef,中序遍历为dbaecf,则说明根节点为a,其中根的左子树是bd,ecf是右子树,B、C错误。同时中序表达式中的“ecf”说明后序遍历时肯定是efc,A正确,D错误。 A 27 12. 某二叉树包含4个节点,共3层,该二叉树的形态有多种,如图所示为 其中的一种形态。该形态的中序遍历序列中,根节点在第3个位置。在 该树的各种可能的形态中,根节点出现在中序遍历序列中的同一个位置 的形态不超过(　　) A. 1种 B. 2种 C. 3种 D. 4种 【解析】 本题考查二叉树的遍历。另外一种符合要求的二叉树的形态如图所示,B正确。 B 28 13. 已知完全二叉树T共有30个节点,则其叶子节点的数量为(　　) A. 10 B. 15 C. 16 D. 20 【解析】 分别用n0、n1和n2表示二叉树度为0、1和2的节点数量,则有n0＋n1＋n2=30,且n2=n0－1 ,可得n0=(31－n)/2,又因为完全二叉树中n的值为0或1,代入可得n0=15,B正确。 B 29 14. 某二叉树的中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA。下列关于该二 叉树的说法,错. 误. 的是(　　) A. 该二叉树前序遍历的结果是ABDGCEF B. 该二叉树是满二叉树 C. 该二叉树有3个叶子节点 D. 节点D是节点G的父节点 【解析】 本题考查二叉树的遍历。根据中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA可知,具体二叉树的形态如图所示。 因此该二叉树前序遍历的结果是ABDGCEF,A不符合题意。该二叉树不是一个满二叉树,B符合题意。该二叉树有3个叶子节点,C不符合题意。节点D是节点G的父节点,D不符合题意。 B 30 15. 有一棵深度为4的二叉树,已知其根节点左侧的节点总数比右侧的节点总数多1。下列关于该树的说法,正确的是(　　) A. 这肯定是一棵完全二叉树 B. 根节点右侧可能只有1个节点 C. 可能共有16个节点 D. 可能共有7个叶子节点 【解析】 本题考查二叉树知识。该树可能是、但不一定是完全二叉树,A错误。右侧最少有2个节点,B错误。深度为4,最多有15个节点,C错误。 D 31 $