专题14　树 学案（含解析）2025届高中信息技术.DOCXVIP

学习目标1.通过描述现实世界中的树形结构实例，了解树的概念及性质，理解树对有分支和层次的数据集合的描述方法；

2.在实际应用中，抽象二叉树的数据结构形式，掌握二叉树的概念及性质；

3.通过数组和链表实现树的创建，理解树形结构的数据节点存储至数组和链表相应位置的方法；

4.按照一定的规则和次序访问二叉树中的所有节点，掌握前序遍历、中序遍历和后序遍历等规则.

判定树的依据：除根节点外，每个节点只有一个前驱，但可以有0个或多个后继。树体现的是一种层次和分支的关系，前驱表示他只能隶属于一个层次，但他可能有0个或多个分支结构。节点数量：树的度决定每层中最多的节点个数，决定了一棵深度为k层的树总节点的个数。边数量：边的数量比总节点数量少一个。二叉树的遍历是将非线性结构转换为线性结构，是按照一定的规则和次序(先访问左节点，后访问右节点)访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。

(2023年6月浙江省选考)某二叉树的树形结构如图所示，其前序遍历结果为BDEFCA，则中序遍历结果为()

A.EDCFBA B.ECFDAB

C.BFDEAC D.EDFCBA

重难点1节点和边的数量关系

n个节点的树有n－1条边，边的计算方法：从每节点到下一层孩子节点的边数之和，叶子节点下方没有边。各种度数的节点个数与度数和乘积之和为n－1，是解决这类问题的关键。深度为k层的完全二叉树从根节点到第k－1层是满二叉树，第k层的叶子节点从左向右依次排列。把握3个等量关系是解决该问题的关键：一是前k－1层总节点数为2k－2－1；二是叶子节点数为度为2的节点数加1，即n2＝n0＋1；三是度为1的节点数量为0或1。

例1已知一棵完全二叉树有8个叶子节点，下列说法正确的是()

A.该完全二叉树的高度可能为3

B.该完全二叉树的形态只有一种

C.该完全二叉树可能有1个度为1的节点

D.该完全二叉树有9个度为2的节点

变式1有一棵8个节点的二叉树，下列说法正确的是()

A.叶子节点可能为4个 B.第3层最多6个节点

C.度为1的节点最多4个 D.该树的层数可能为3层

例2假设完全二叉树的树根为第1层，树中第10层有5个叶子节点，则完全二叉树最多节点个数是()

A.2047 B.2048 C.2037 D.2038

变式2某完全二叉树共有300个节点，该二叉树的高度是()

A.8 B.9 C.10 D.1l

例1下列二叉树中，中序遍历结果为BAEDFC的是()

变式1某完全二叉树的后序遍历为EBAGDC，则下列说法正确的是()

A.该树的深度为4

B.该树有2个叶子节点

C.该树的节点B、G是兄弟节点

D.删除节点E后，该树的前序遍历为CABDG

例2用一维数组表示二叉树，如表所示：

0

1

2

3

4

5

6

7

8

9

10

A

B

C

D

E

F

G

下列有关该二叉树的说法正确的是()

A.该树中共有4个叶子节点

B.该树是完全二叉树，其深度为4

C.该树的中序遍历为B－F－D－G－A－C－E

D.该二叉树的结构图为(如图所示)

变式2一个数学表达式可以用一棵表达式树来表示，而一棵二叉树可以用一维数组表示。有一棵表达式树用一维数组表示如下。下列有关该表达式树的说法正确的是()

0

1

2

3

4

5

6

7

8

/

－

4

*

8

4

6

A.该表达式树是一棵完全二叉树

B.该表达式树的左右子树深度相差为1

C.该表达式树的叶子结点有4个

D.该表达式树中序遍历的结果为4*6/8－4

重难点3根据两种遍历序列确定一棵二叉树

前序遍历序列均为ABC的3个节点二叉树可能形态如图所示，

前3棵树的后序遍历均为CBA，前序遍历为根左右，后序遍历为左右根，当缺失一个孩子节点时，很难确定另外一个节点是左节点还是右节点，因此根据前后两种遍历序列，不能确定一棵二叉树。前后序遍历可以确定根节点，中序遍历根据根节点划分左右子树。先将一棵树分解成左右子树，再对子树再按上述方法来划分，直到分解为最小的树。

例题某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是()

A.前序遍历序列为DBACGFE

B.节点G为节点E的父节点

C.该二叉树有两个叶子节点

D.节点A与节点F为同一层

变式二叉树的中序遍历为BAEDFC，后序遍历为BEFDCA，其前序遍历为()

A.ABDEFC B.ABDCEF

C.ABCDEF D.ABCDFE

重难点1节点和边的数量关系

1.有树结构的示意图如图所示，下列关于该树的描述正确的是()

A.该树的度为6

B.该树的叶子节点数量是7

C