资源简介

专题15　树
学业要求 知　识　点 学业水平等级
1.抽象二叉树的数据结构形式，掌握二叉树的概念及性质 3
2.通过数组和链表实现树的创建，理解数组和链表相应位置的方法 4
3.掌握前序遍历、中序遍历和后序遍历等规则 4
知识点一　树的性质
【知识梳理】
1.________可以描述为由n(n≥0)个节点(Node)构成的一个有限集合以及在该集合上定义的一种节点关系。
2.集合中的元素称为树的________，n＝0的树称为________；树中某个节点下面的所有节点所构成的树称为该节点的________。
3.树的两个节点之间如果有一条边连接，那么称这两个节点之间存在一条________，对于一棵具有n个节点的树，它有n－1条边。
4.树的一个节点所拥有的子树个数称为该节点的________，最大的节点的度称为树的度。线性表是度为1的特殊树状结构。
5.在树状结构中，没有前驱节点的称为________，又称为开始节点。度为0的节点称为________，也称为终端节点。
6.在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的________或双亲节点(Parent)。相应地，下端节点称为上端节点的孩子节点(Child)。
7.树中节点的________从根开始计算，根的层数为1，其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的________________。
8.________是一个具有n(n≥0)个节点的有限集合，它的所有节点的度都小于或等于2。当n＝0时，二叉树是一棵空树；当n不等于0时，它是一棵由根节点和两棵互不相交的，分别称作这个根节点的________和________组成的二叉树。
9.____________至多只有最下面两层中的节点度数小于2，且最下面一层的叶子节点都依次排列在该层的最左边位置。
10.二叉树的性质：①二叉树的第k层最多有________(k≥1)个节点；②深度为k的二叉树最多有2k－1(k≥1)个节点；③在任意一棵二叉树中，若度为2的节点数量为n2，叶子节点(度为0的节点)数为n0，则n0＝n2＋1。
【经典案例】
树是n(n>＝0)个节点的有限集合，有且仅有一个称为根的节点，没有后继的节点称为“叶子节点”，有后继的节点称为“分支节点”，除了根节点外，任何一个节点都有且仅有一个前驱，每个节点可以有0个或多个后继，任何一个树都可以被看作是由一个根节点和若干不相交的子树组成的，因此树是一种递归定义的数据结构。
树的属性：节点的层次(深度)，从上往下数，默认从1开始。节点的高度，从下往上数，总共有多少层。节点的度指当前节点有几个孩子(分支)，树的度指各节点的度的最大值。
【例1】 有一棵树，节点的度和个数如下表所示。
度 0 1 2 3 4
节点个数 x 4 3 2 1
则叶子节点x的个数为(　　)
A.8 B.9
C.10 D.11
思维点拨
精点拨 树中所有节点的度之和加1为节点总数，因此1*4＋2*3＋3*2＋4*1＝21。节点数为x＋4＋3＋2＋1＝x＋10，因此可以得到叶子节点数为11个
听课笔记：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 已知一棵完全二叉树的节点总数为12，则有关该二叉树的说法正确的是(　　)
A.树的度为12 B.树的层数为3
C.叶子节点数为5 D.最后一层有5个节点
【例2】 已知一棵完全二叉树有8个叶子节点，下列说法正确的是(　　)
A.该完全二叉树的高度最大为3
B.该完全二叉树的形态只有一种
C.该完全二叉树可能有1个度为1的节点
D.该完全二叉树有9个度为2的节点
思维点拨
明考向 本题考查树的性质。根据树的性质，2度节点个数为叶子节点个数减1，因此2度节点有7个。由于是完全二叉树，1度节点的个数为0或1，因此总共节点数为15或16个
精点拨 A 根据总共节点数，可知该树可能是3层，也可以是4层
B 当总节点是3层时，是一棵满二叉树，当节点为16时，在4层下有一个节点
C 当总节点为16时，有一个1度节点
D 2度节点个数为7个
听课笔记：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 已知完全二叉树T共有78个节点，则其叶子节点数量为(　　)
A.15 B.32
C.39 D.40
知识点二　树的遍历
【知识梳理】
1.____________的操作，可以按照层的顺序进行，先由第1层开始，依次到下一层，在每一层中按照从左到右的顺序创建节点。二叉树的建立可以用数组或者链表数据结构来实现。
2.____________________，从根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n－1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。
3.________________________，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示，数据存储时对应位置空缺，其它节点在数组中的位置参照完全二叉树。
4.________________，每个节点至少需要3个域，一个数据域和两个指针域。数据域用于存放本节点的数据信息，左右两个指针域分别指向左右孩子节点。
5.________________，是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。
6.________，若二叉树为空，则空操作返回；否则先访问根节点，再访问左子树，最后访问右子树。
7.________，若二叉树为空，则空操作返回；否则先访问左子树，再访问根节点，最后访问右子树。
8.________，若二叉树为空，则空操作返回；否则先访问左子树，再访问右子树，最后访问根节点。
【经典案例】
二叉树的建立可以用数组或者链表数据结构来实现。用数组实现时，需把二叉树补全为一棵完全二叉树，优点是能快速地检索到某个节点的值，如果根节点编号为1，则第i个节点的左孩子编号为2*i，右孩子编号为2*i＋1。缺点是当这棵二叉树不是完全二叉树时，会造成存储空间的浪费。
二叉树的遍历实现用线性结构来描述层次化、分支化的非线性结构。二叉树的遍历是按照一定的规则和次序(先访问左节点，后访问右节点)访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。一棵二叉树必定先访问左节点，再访问右节点，将根节点所有位置分为前、中、后序三种遍历方式。
【例1】 某二叉树的树形结构如图所示，其前序遍历结果为BDEFCA，则中序遍历结果为(　　)
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
思维点拨
明考向 本题考查二叉树的遍历
精点拨 前序遍历可知B为二叉树根节点，D和左子树根节点，E和F为左子树的左右孩子。C为F的左孩子，A为树的右子树。该树结构如图所示。因此中序遍历为EDCFBA
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 下列二叉树中，中序遍历结果为BAEDFC的是(　　)
【例2】 某二叉树用一维数组来表示如下表所示。该二叉树从根节点开始，按照从上到下，从左到右的顺序依次用A－H字母表示，该二叉树的中序遍历为(　　)
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素 A B C D E F G H
A.DBGEACFH B.DBGEACHF
C.DBEGACHF D.ABCDEFGH
思维点拨
明考向 本题考查二叉树的相关概念
精点拨 根据题意，可以构建出如下图的二叉树。该树的中序遍历为DBGEACFH。
听课笔记：_____________________________________________________________
______________________________________________________________________
【变式2】 某表达式树如图所示，下列说法错误的是(　　)
A.该表达式树是一棵二叉树，树的度是2，高度是5
B.该树的叶子节点数比度为2的节点数多1个
C.若采用完全二叉树数组从0号位开始存储，则节点b存储在6号位
D.该表达式树的前序遍历序列是×d＋/fc－ab
1.下列关于二叉树的说法，不正确的是(　　)
A.二叉树的数据元素之间呈非线性关系
B.二叉树的第k层上最多有2k－1(k≥1)个节点
C.由前序遍历和中序遍历序列能唯一确定一棵二叉树
D.具有100个节点的完全二叉树有50个度为2的节点
2.有一棵二叉树如图所示，下列说法正确的是(　　)
A.该二叉树是一棵完全二叉树，树的高度为3
B.该二叉树的前序遍历为A，B，D，C，E
C.该二叉树的叶子节点有4个
D.该二叉树的建立只能使用数组来实现
3.有树结构的示意图如图所示，下列关于该树的描述正确的是(　　)
A.该树的度为6 B.该树的叶子节点数量是7
C.节点I、J互为兄弟节点 D.该树的深度为5
4.对于如图所示的二叉树，下列说法正确的是(　　)
A.叶子节点有4个
B.是完全二叉树，树的高度为4
C.前序遍历的结果是一个递增序列
D.可以使用数组[2，5，10，7，8，13，9，15]存储
5.某二叉树如下图所示，下列说法正确的是(　　)
A.该二叉树共有5个叶子节点
B.该二叉树是一棵完全二叉树
C.对该二叉树进行中序遍历后的计算结果是32
D.该二叉树的后序遍历序列为731＋*426＋/－
6.某二叉树中序遍历为ABCDEF，则下列不可能是此二叉树的是(　　)
7.有一种二叉树，它的任何一个当前节点，左子树的数据都比该节点的数据小，右子树的数据都比该节点的数据大。下列有关该二叉树遍历说法正确的是(　　)
A.采用前序遍历，遍历到的节点元素升序排列
B.采用中序遍历，遍历到的节点元素升序排列
C.采用中序遍历，遍历到的节点元素降序排列
D.采用后序遍历，遍历到的节点元素降序排列
8.某二叉树的树形结构如图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为(　　)
A.语数英物化技 B.物数技化语英
C.语数物化技英 D.化物技英数语
9.某二叉树的数组表示示意图如图所示，该二叉树的后序遍历序列为(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
10.已知某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，则下列说法正确的是(　　)
A.其后序遍历结果为DCBFEA
B.该二叉树为完全二叉树
C.该二叉树深度为3，叶子节点数为3
D.该二叉树用一维数组实现需要6个节点的存储空间才能表示
11.某二叉树前序遍历的结果为“ABCD”，则中序遍历的结果不可能是(　　)
A.ABCD B.CDBA
C.BDAC D.DCBA
12.数学表达式3/(5*2)可用二叉树表示，如图所示。下列关于该二叉树的说法，正确的是(　　)
A.是完全二叉树 B.叶子节点数为2
C.前序遍历结果为352*/ D.用数组表示为
专题15　树
知识点一
知识梳理
1.树(Tree)　2.节点　空树　子树　3.边 4.度(Degree)　5.根节点(Root)　叶节点(Leaf) 6.父节点　7.层数(Level)　高度或深度(Depth) 8.二叉树　左子树　右子树　9.完全二叉树 10.2k－1
经典案例
例1　D
变式1　D　[本题考查二叉树的基本性质。符合完全二叉树的两个条件为：①只有最下二层中的节点度数小于2；②最下一层的叶子节点都依次排列在该层最左边位置。A选项度指树的最大节点数。B选项若为满二叉树，第3层及前面所有节点数和为7，因此至少4层。C选项最后一层上有5个节点，即有叶子节点数为5，但第3层上还有一个叶子节点。]
例2　C
变式2　C　[设二叉树0度、1度和2度的节点个数分别为t0，t1，t2，有等式t0＋t1＋t2＝78和t0＝t2＋1成立，代入可得t0＋t1＋t0－1＝78，且完全二叉树1度节点个数为0或1，因此t1值为1。]
知识点二
知识梳理
1.建立二叉树　2.用数组表示完全二叉树　3.用数组表示非完全二叉树　4.用链表实现二叉树　5.二叉树的遍历　6.前序遍历　7.中序遍历　8.后序遍历
经典案例
例1　A
变式1　C　[本题考查二叉树遍历。中序遍历的方法：左子树－根－右子树，每个子树，都遵循以上规定。A选项中序遍历结果为EDFBAC。B选项中序遍历结果为BEDFAC。C选项中序遍历结果为BAEDFC。D选项中序遍历结果为BACEDF。]
例2　A
变式2　D　[本题考查树与二叉树相关知识。树的度是最大的节点的度，树的高度是节点最大的层数，A选项在任意一棵二叉树中都有n0＝n2＋1的性质，即叶子节点数等于度为2的节点数多一个；非完全二叉树若用完全二叉树保存时需将树补成完全二叉树，即第3层需补全d节点的两个孩子节点，此时节点b存储在第6号位置上。D选项该表达式树的前序遍历序列是×d＋/f－cab，对节点“－”而言先于其子节点c。]
当堂过关检测
1.D　[本题考查树的性质。A选项树表现一种层次性的非线性关系。D选项设二叉树0度、1度和2度的节点个数分别为t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉树1度节点个数为0或1，因此t2值为49。]
2.B　[本题考查树的性质。A选项完全二叉树第n－1层为满二叉树，不符合。C选项叶子节点有2个。D选项可以用数组或链表实现。]
3.B　[本题考查树的基本概念。A选项度是指节点拥有的子树个数，其中最大的节点的度就是树的度。B选项共有H、I、J、C、K、L、M，7个叶子。C选项父节点是同一个的，才是兄弟节点。D选项该树共4层，所以深度是4。]
4.C　[本题考查二叉树相关知识。A选项叶子节点有7，9，15，共3个。B选项完全二叉树要求叶子节点从右开始，且最多只出现在最下面2层。C正确，前序遍历时2－5－7－8－9－10－13－15，是一个递增序列。D选项用数组表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15]。]
5.D　[A选项共有6个叶子节点。C选项中序遍历为7*(3＋1)－(4/(2＋6))＝28－0.5＝27.5。]
6.C　[C选项中序遍历为ACBDEF。]
7.B　[本题考查二叉树的遍历。画出如题描述的二叉树，根为5，故前序遍历和后序遍历都不可能实现升序或者降序。若采用中序遍历，因为中序遍历的结果是左根右，以左子树为例，左根右的结果是234，升序，故答案选B。]
8.B　[本题考查二叉树遍历。后序遍历是“物技化数英语”可知，根节点为语，数英分别是语节点的左右孩子。物为数的左孩子，技为最高层的左孩子，化为数的右孩子。]
9.B　[本题考查二叉树的遍历。根据题意画出二叉树如下。
后序遍历是：BFDGECA。]
10.C　[本题考查树的性质和遍历。
根据前序遍历确定根节点，中序遍历区分左右子树，画出二叉树。其后序遍历结果为CDBFEA，该二叉树最后一层叶子节点不是从左向右分布。该二叉树深度为3，叶子节点数为3。]
11.C　[本题考查二叉树相关概念。前序遍历为根左右，中序遍历为左根右。A选项当左子树缺失时，遍历序列相同。D选项当右子树缺失时，遍历序列正好相反。节点D可能是整棵树的右子树，也可能是左子树中的一个右孩子，但节点C一定先于节点D访问，因此C选项不可能。B选项当D是C的右孩子，C缺失左孩子，整棵树没有右子树。]
12.D　[本题考查二叉树的遍历。A选项完全二叉树是指一棵深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，编号为i(1≤i≤n)的节点与满二叉树中编号为i的节点在二叉树中的位置相同。3所在节点缺少叶子节点，故该二叉树不是完全二叉树。B选项3、5、2所在节点为叶子节点，数量为3。C选项前序遍历结果为/3*52。D选项将图中二叉树补全为完全二叉树，依次把完全二叉树中原二叉树的节点用一维数组的各元素表示。]

展开更多......

收起↑