计算机二级公共基础专题探究二叉树.docx
《计算机二级公共基础专题探究二叉树.docx》由会员分享，可在线阅读，更多相关《计算机二级公共基础专题探究二叉树.docx（11页珍藏版）》请在冰点文库上搜索。
计算机二级公共基础专题探究二叉树
公共基础专题探究——二叉树
1．6树与二叉树
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
在树结构中，没有前件的结点只有一个，称为树的根结点，简称树的根。
每一个结点可以有多个后件，称为该结点的子结点。
没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。
树的最大层次称为树的深度。
二叉树的特点：
（1）非空二叉树只有一个根结点；
（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树的基本性质：
必考的题目
（1）在二叉树的第k层上，最多有2k-1（k≥1）个结点；
（2）深度为m的二叉树最多有2m-1个结点；
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）二叉树中n=n0+n1+n2
满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历：
（一般画个图要你把顺序写出来）
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
序号
高频考点
1
树是简单的非线性结构，二叉树作为树的一种也是一种非线性结构。
2
重点题型：
二叉树的基本性质3：
在任意一棵二叉树中，度为0的叶子结点总比度为2的结点多一个
例1：
某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（6）
例2：
一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（16）
【解析】度为2的结点是5－1＝4个，所以度为1的结点的个数是25－5－4＝16个。
例3：
某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）（ 7 ）。
【解析】度为2的结点为1－1＝0个，所以可以知道本题目中的二叉树的每一个结点都有一个分支，所以共7个结点共7层，即度为7
例4：
某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（48）。
【解析】由16个度为2的结点可知叶子结点个数为17，则结点结点总数为16+17+15=48
例5：
某二叉树共有12个结点，其中叶子结点只有1个。
则该二叉树的深度为（根结点在第1层）（12）
【解析】二叉树中，度为0的节点数等于度为2的节点数加1，即n2=n0-1，叶子节点即度为0，n0=1，则n2=0，总节点数为12=n0+n1+n2=1+n1+0，则度为1的节点数n1=11，故深度为12，
例6：
一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为（229）
【解析】二叉树中，度为0的节点数等于度为2的节点数加1，即n2=n0-1，叶子节点即度为0，则n2=79，总结点数为n0+n1+n2=80+70+79=229
3
在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。
4
前序遍历（访问根结点在访问左子树和访问右子树之前）
前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
前序遍历描述为：
若二叉树为空，则执行空操作。
否则：
①访问根结点；②前序遍历左子树；③前序遍历右子树，
5
中序遍历（访问根结点在访问左子树和访问右子树两者之间）
6
后序遍历（访问根结点在访问左子树和访问右子树之后）
7
重点题型：
二叉树的遍历
例1：
某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（DCBA）。
【解析】前序序列为ABCD，可知A为根结点。
根据中序序列为DCBA可知DCB是A的左子树。
根据前序序列可知B是CD的根结点。
再根据中序序列可知DC是结点B的左子树。
根据前序序列可知，C是D的根结点，故后序序列为DCBA
例2：
对下列二叉树进行前序遍历的结果为ABDYECFXZ
例3：
设二叉树如下，则后序序列为DGEBHFCA
【解析】本题中前序遍历为ABDEGCFH，中序遍历为DBGEAFHC，后序遍历为DGEBHFCA
8
完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
例1：
深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（63）
【解析】在树结构中，定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1，树的最大层次称为树的深度。
深度为6的满二叉树，结点个数为2^6-1=63，则第7层共有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，加上第6层的最后1个叶子结点，该完全二叉树共有63个叶子结点，故B选项正确。
9
满二叉树和完全二叉树可以按层序进行顺序存储，一般的二叉树不试用。
10
堆可以用一维数组储存也可以用完全二叉树来表示堆的结构。
11
完全二叉树中，若总结点数是偶数，则N1=1，若为奇数，则N1=0
12
深度为i的满二叉树中，N2=2i-1-1
排序二叉树中有序的是中序序列。
堆排序问题：
题型一：
三种序列的转换。
（文字叙述型）
例1：
已知前序序列与中序序列均为ABCDEFGH，求后序序列
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R已知ABCDEFGH
中：
L-D-R已知ABCDEFGH
后：
L-R-D待求
由此可知，L=0，D-R=ABCDEFGH
故R-D=HGFEDCBA，即后序序列=HGFEDCBA
变式训练1：
已知后序序列与中序序列均为ABCDEFGH，求前序序列
答案：
HGFEDCBA，（这次R=0）
结论：
若前序序列与中序序列均为某序列，则后序序列为该序列的倒序，且为折线；同样地，若后序序列与中序序列均为某序列，则前序序列为该序列的倒序，且为折线
例2：
已知前序序列=ABCD，中序序列=DCBA，求后序序列
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R已知ABCD
中：
L-D-R已知DCBA
后：
L-R-D待求
因为ABCD与DCBA正好相反，由此可知，R=0
所以D-L=ABCD，即L-D=DCBA
所以后序序列=DCBA
变式训练2-1：
中序序列=BDCA，后序序列=DCBA，求前序序列
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R待求
中：
L-D-R已知BDC,A
后：
L-R-D已知DCB,A
通过观察可知，R=0，L={B,D,C}，D=A
中、后变换时，{B,D,C}发生了变化，说明左子树结构特殊，进一步
令中’：
L’-D’-R’已知B,DC
后’：
L’-R’-D’已知DC,B
可知L’=0，即D’=B，R’=DC
可以画出二叉树示意图为：
D
所以前序序列=ABCD
变式训练2-2：
中序序列=ABC，后序序列=CBA，求前序序列
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R待求
中：
L-D-R已知ABC
后：
L-R-D已知
通过观察可知，L=0，D-R=ABC，R-D=CBA
所以前序序列=D-L-R=D-R=ABC
变式训练2-3：
前序序列=ABC，中序序列=CBA，求后序序列
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R已知A,BC
中：
L-D-R已知CB,A
后：
L-R-D待求
通过观察可知，D=A，L={B,C}，R=0
所以后序序列=CBA（一边偏）
题型二：
求二叉树的深度。
例1：
已知某二叉树共有12个节点，其中叶子结点1个，求深度。
（令根节点在第一层）
【解析】设叶子结点=N0，度为1的节点为N1，度为2的节点为N2。
有二叉树的性质3，N0=N2+1
由题，N2=N0-1=0，有总节点数N=N0+N1+N2=12，
解得N1=11，故二叉树的图像为一条折线（或直线）
所以深度为12
例2：
已知二叉树的前序序列=ABCDEFG，中序序列=DCBAEFG，
（1）求后序序列
（2）求深度。
（令根节点在第一层）
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R已知A,BCD,EFG
中：
L-D-R已知DCB,A,EFG
后：
L-R-D待求
通过观察可知，R=EFG，D=A，L={B,C,D}
同理，B为C的父节点，C为D的父节点，且CD在B的同侧
可得后=DCB,GFE,A
可以画出二叉树示意图为：
由图可知，深度为4
题型三：
求树的叶子结点数或某度的结点数。
例1：
【解析】先列一个表，设叶子结点数=n
N4
2
N3
3
N2
3
N1
0
N0
n
有N=（4×2+3×3+2×3+1×0）+1=24，其中多加的1是根节点
然后n=24-2-3-3-0=16
变式训练1：
【解析】先列一个表，设叶子结点数=n
N3
3
N2
0
N1
4
N0
n
有N=（3×3+2×0+1×4）+1=14，其中多加的1是根节点
然后n=14-3-0-4=7
例2：
【解析】先列一个表，设叶子结点数=n
N3
8
N0
n
有N=（3×8）+1=25，其中多加的1是根节点
然后n=25-8=17
变式训练2-1：
【解析】先列一个表，设度为3的结点数=n
N3
n
N0
7
有N=（3×n）+1=25，其中多加的1是根节点，可知n=8
然后7≠25-8=17！
！
！
故：
“不存在这样的树”（启示：
一定要验算）
变式训练2-2：
【解析】先列一个表，设度为3的结点数=n
N3
n
N2
3
N1
4
N0
15
有N=（3×n）+2×3+1×4）+1，其中多加的1是根节点
然后15=N-22-n联立后无整数解
故：
“不存在这样的树”（启示：
一定要验算）
例3：
5+1=6
题型四：
与按层次输出有关的问题。
例1：
（由层次输出求序列）
【解析】第一步，画图：
H
求中序序列：
L-D-R，所以是HDB,E,A,FC,G
例2：
（由序列求层次输出）
【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：
前：
D-L-R已知A,BDEGH,CFIJ→A为第一层根结点
中：
L-D-R已知DBGEH,A,CIFJ
通过观察可知，R={C,F,I,J}，L={D,B,G,E,H}，D=A
对第一层的第二层L，
前：
D’-L’-R’已知B,D,EGH→B为第二层左结点
中：
L’-D’-R’已知D,B,GEH
对第一层的第二层R，
前：
D’-L’-R’已知C,FIJ→C为第二层右结点
中：
L’-D’-R’已知C,IFJ
……
由此分析，最终层次输出为ABCDEFGHIJ
升级会员 