资源简介

(共20张PPT)
二、 二叉树的基本操作
第四章　树
知识过关
1. 二叉树的建立
(1)数组实现完全二叉树。从它的根节点开始,按从上而下、自左往右的顺序编号,根节点的编号为0,最后一个节点的编号为n－1。然后依次把二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一对应。如左下图所示的完全二叉树所对应的一维数组表示如右下图所示。
完全二叉树　　
编号 0 1 2 3 4 5 6 7
结点 A B C D E
数组表示示意图
(2)数组实现非完全二叉树。对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示,将如左下图所示的一棵非完全二叉树补全为完全二叉树。然后将补全后的完全二叉树,从它的根节点开始,按从上而下、自左往右的顺序编号,根节点的编号为0,最后一个节点的编号为n－1。如右下图所示,依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示,节点编号与数组的下标一一对应。
原二叉树　　 补全后的二叉树　　
0 1 2 3 4 5 6 7
A B C
数组实现示意图
(3)链表实现二叉树。用任意的一组存储单元来存储二叉树的节点,用指向节点的指针来表示节点之间的关系。由于二叉树的节点可能有两个孩子,即左孩子和右孩子,因此二叉树的节点至少需要3个域:一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子,这两个指针分别称为左指针和右指针,这样得到的链表也称为二叉链表。如图所示为二叉树及其对应的二叉链表实现示意图。
2. 二叉树的遍历(前序、中序和后序)
二叉树遍历是指按照一定的规则和次序访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。二叉树的遍历方式有很多,主要有前序遍历、中序遍历和后序遍历等。
(1)前序遍历(先根遍历)。
若二叉树为空,则空操作返回;否则,先访问根节点,再访问左子树,最后访问右子树。
(2)中序遍历(中根遍历)。
若二叉树为空,则空操作返回;否则,先访问左子树,再访问根节点,最后访问右子树。
(3)后序遍历(后根遍历)。
若二叉树为空,则空操作返回;否则,先访问左子树,再访问右子树,最后访问根节点。
二叉树
前序遍历(先根遍历):ABDECF 中序遍历(中根遍历):DBEAFC 后序遍历(后根遍历):DEBFCA 方法:找出根节点、划分子树,子树递归遍历。
典例精选
【例1】 (2024·浙江1月选考)某完全二叉树包含5个节点,其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为x,y,则x－y的值是(　　)
A. 0 B. 1
C. 2 D. 3
【解析】 本题考查完全二叉树及二叉树的遍历知识。二叉树的后序遍历:左子树—右子树—根节点,根节点一定是在最后的位置。中序遍历:左子树—根节点—右子树,5个节点的完全二叉树,左子树有3个节点,右子树只有1个节点,根节点在倒数第二的位置,那就有x－y=1,B正确。
B
【例2】 (2023·浙江6月选考)某二叉树的树形结构如下图所示,其前序遍历的结果为
BDEFCA,则中序遍历结果是(　　)
A. EDCFBA B. ECFDAB
C. BFDEAC D. EDFCBA
A
【解析】 本题考查二叉树的遍历知识。前序遍历规则为“根左右”,已知前序遍历结果为BDEFCA,结合题图可知:
①二叉树第一次划分状态应为
,如图1所示。
② 根据前序遍历规则结合结构图,对左子树进行划分
,
如图2所示。
③ 重复上述划分过程,对FC进行划分
,最后,根据完整的二叉树结构图,
如图3所示,可知中序遍历为EDCFBA。
A正确。
【例3】 (2023·浙江1月选考)下列二叉树中,中序遍历的结果为BAEDFC的是(　　)
C
A.
B.
C.
D.
【解析】 本题考查二叉树遍历的基本操作。中序遍历的特点:左子树—根—右子树,每个子树都遵循以上规定。4个二叉树的中序遍历结果如下:A:EDFBAC;B:BEDFAC; C:BAEDFC;D:BACEDF。C正确。
自我检测
1. 某完全二叉树共有300个节点,该二叉树的高度是(　　)
A. 8 B. 9
C. 10 D. 11
【解析】 本题考查二叉树的基础知识。根据二叉树知识可知,若满二叉树的深度为3,则该二叉树的节点数为20+21+22=7。现在已知完全二叉树共有300个节点,由于256+44=300,且21+22+……27=256,因此该二叉树的前面8层是满二叉树,第9层的左边有连续的44个节点,B正确。
B
2. 某二叉树如右图所示。下列关于该二叉树的说法,错. 误. 的是(　　)
A. 该二叉树的深度为3
B. 该二叉树的度均为2
C. 该二叉树的根节点为A
D. 该二叉树的节点D和E是兄弟节点
【解析】 本题考查二叉树的知识。叶子节点D、E、C的度均为0,B符合题意。
B
3. 某二叉树的前序遍历的结果为ABC,若该二叉树不是满二叉树,则其后序遍历的结果是
(　　)
A. ABC B. BCA
C. CBA D. CAB
【解析】 本题考查二叉树的遍历。若二叉树不是满二叉树,则其可能有如下图所示的形式:
可以看出,其后序遍历的结果均为CBA,C正确。
C
4. 有一棵完全二叉树,已知其中序遍历结果是CADGBEIHJ,则其前序遍历结果应该为
(　　)
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
【解析】 该完全二叉树有9个节点,因此共有4层,其中前3层是满二叉树(7个节点),第4层有2个节点,画出二叉树的形态和中序遍历路径,可得前序遍历序列。
B
5. 某二叉树中序遍历为ABCDEF,则下列不可能是此二叉树的为(　　)
A.　　　　 B.　　 　C.　　　　 D.
【解析】 C选项中序遍历为ACBDEF。
C

展开更多......

收起↑