数据结构-树和二叉树篇：
内容：
- 思维导图（基于教材）
- 错题复盘+计算题（基于习题解析）
- 课后习题
1.思维导图
从这章开始，要是上课听不懂的话，推荐去看B站青岛大学王卓王卓老师讲解的很细节，基本上每个知识点十几二十分钟，刚开始看的时候，可能会不习惯王老师的语气词，别退出，视频重要的是老师讲解的知识点而不是语气词，也最好不要发这类弹幕
2.错题复盘+计算题
1 利用二叉链表存储树，则根结点的右指针是（C）
A.指向最左孩子
B.指向最右孩子
C.空
D.非空
解析：二叉链表存储结构就是树的孩子兄弟表示法，左指针指向第一个孩子结点，右指针指向下一个兄弟结点。根节点没有兄弟结点，所以根节点的右指针指空
2 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其有孩子的编号，可采用（C）遍历实现编号
A.先序 B.中序 C.后序 D.从根开始按层次遍历
解析：按照先左孩子，再右孩子，最后根结点的顺序遍历可以满足题目要求
3 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.是任意一棵二叉树
解析：先序遍历顺序为‘根左右’，后序遍历顺序为‘左右根’，当没有左孩子的时候，先序遍历顺序为‘根右’，后序遍历顺序为‘右根’，A符合题意；同理，B也可以；当只有一个叶子结点时，说明没有左子树或没有右子树，所以C是A+B加强版，更合理了
4 设哈夫曼树中有199个结点，则该哈夫曼树中有（B）个叶子结点
A.99
B.100
C.101
D.102
解析：1.根据哈夫曼树由n个结点通过n-1次合并后共有2n-1个结点，直接可以代入，得n的值2.推导版：根据哈夫曼中没有度为1的结点，只有叶子结点和度为2的结点，设叶子结点的个数为n0，度为2的结点个数为n2，由二叉树的性质n0=n2+1，故总结点数n=n0+n2=2n0-1=199，所以n0=100
5 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（C）
A.X的双亲
B.X的右子树中最左的结点
C.X的左子树中最右结点
D.X的左子树中最右叶子结点
解析：线索二叉树利用二叉链表的空链域来存放结点的前驱结点和后继结点信息，又因为中序遍历顺序为‘左根右’，所以X的前驱为X左子树的最右的结点
6 线索二叉树是一种（C）结构
A.逻辑 B.逻辑和物理 C.物理 D.线性
7 在线索二叉树中，t所指结点没有左子树的充要条件是（B）
A.t->lchild== NULL
B.t->LTag== 1
C.t->LTag== 1&&t->lchild==NULL
D以上都不对
解析：线索二叉树中通过LTag是否为1来确定是否有左子树
8 下面关于树描述错误的是（C）
A.具有n个结点的树具有n-1个结点
B.度为m的树至少有一个度为m的结点，不存在度大于m的结点
C.一棵m叉树就是度等于m的树
D.树中任意两个结点之间的路径是唯一的
解析：m叉树是指允许树的每个结点最多有m个子结点，不是一定存在具有m个子结点的结点
9 设高度为h的二叉树中只有度为0和度为2的结点，称这种二叉树为正则二叉树，它所包含的结点树最少为（B）
A.2h B.2h-1 C.2h+1 D.h+1
解析：当结点最少时，除第h层，每层只有1个度为2的结点，即产生两个子结点
10 设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（C）个
A.n-1 B.n C.n+1 D.n+2
解析：我看了答案解析还是迷迷糊糊的，能看懂但下次遇到还是不会
1.若F中有t个终端结点，则结点总数为：N=t+n，左右指针域的个数分别为：N左=N右=t+n，其中非空链域个数（树中的分支个数）为：N非空=N-1=t+n-1
2.森林转成二叉树规则‘左孩子右兄弟’，因为有n个非终端结点，有且仅有n个结点有孩子，当转化成二叉树后则有n个非空的左指针域，记为：N左非空=n
3.非空的右指针域个数为：N右非空=N非空-N左非空=t+n-1-n=t-1
4.空的指针域个数为：N右空=N右-N右非空=t+n-t+1=n+1
11 在一棵二叉树中度为0的结点个数是k，度为1的结点个数是m，则该二叉树采用二叉链表存储结构时，指向子女结点的指针数目是（C）
A.k B.m C.2k+m-2 D.2k+m
解析：设度为2的结点数位n2，由二叉树的性质n0=n2+1，得总结点数n=k+m+n2=2k+m-1，分支数B=n-1=2k+m-1。二叉树采用二叉链表存储时，指向孩子结点的指针数目与分支数相等
12 已知一棵完全二叉树的第6层（设根位第一层）有8个叶子结点，则该完全二叉树的结点个数最多是（C）
A.39 B.52 C.111 D.119
解析：第6层有8个叶子结点说明高度可能为6或7，求结点个数最多，则当高度为7，前6层满二叉树，结点数为2^6 -1=63，第6层有8个叶子结点，结合性质1可得第6层非叶子结点数为2^(6-1)-8=24,非叶子结点数最多各有两个子结点，所以总结点数=63+24*2=111
13 将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（B）
1.父子关系 2.兄弟关系 3.u的父结点与v的父结点是兄弟关系
A.只有2 B.1和2 C.1和3 D.1，2，3
解析：根据题目画出二叉树形态关系，然后根据森林转换二叉树规则，画出森林形态关系，如下图所示，虽然潦草了点，但还是能看的
14 n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树说法正确的是（A）
A.该树一定是棵完全二叉树
B.树中一定没有度为1的结点
C.树中两个权值最小的结点一定是兄弟结点
D.树中任一非叶子结点的权值一定不小于下一层任一结点的权值
解析：哈夫曼树根完全二叉树没有任何关联
15 已知一棵有2011个结点的树，其叶子结点个数为116，该树对应的二叉树中无右孩子的结点个数为（D）
A.115 B.116 C.1895 D.1896
解析：1.利用孩子兄弟表示法，将树转换为二叉树，树中每一个分支结点的所有子结点中的最右子结点都没有右孩子，根结点也没有右孩子，所以，对应的二叉树中无右孩子的结点个数为分支总数+1=2011-116+1=1896；还有一种我不会的方法，利用特殊值法进行计算，假设题意中的树是下图左边所示结构，对应的二叉树中仅有前115个叶子结点有右孩子，则该树对应的二叉树中无右孩子的结点个数是：2011-115=1896，如下图右边所示
16 已知三叉树T中6个叶子结点的权分别是2，3，4，5，6，7，T的带权（外部）路径长度最小是（B）
A.27 B.46 C.54 D.56
解析：这题考的是k叉哈夫曼树的构造，请点击详细介绍，省流版：对给定的n个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式，更直接的方式是令(n-1)%(k-1)=0。所以6个叶子结点构建三叉树不满足这种形式，要补一个权值为0的叶子结点，构造如下图所示
17 若X是后序线索二叉树中的叶子结点，且X存在左兄弟结点Y，则X的右线索指向的是（A）
A.X的父结点
B.以Y为根的子树的最左下结点
C.X的左兄弟结点Y
D.以Y为根的子树的最右下结点
解析：根据后序线索二叉树的定义，X为叶结点且有左兄弟，可得X为右孩子结点，利用后序遍历顺序可得X的父结点时其后序后继结点，所以X的右线索指向的是X的父结点
18 将森林F转换为对应的二叉树T，F中叶子结点的个数等于（C）
A.T中叶子结点的个数
B.T中度为1的结点个数
C.T中左孩子指针为空的结点个数
D.T中右孩子指针为空的结点个数
解析：根据转换规则，可得森林的叶子结点转换为二叉树时没有左孩子
19 5个字符有如下四种编码方案，不是前缀编码的是（D）
A.01，0000，0001，001，1
B.011，000，001，010，1
C.000，001，010，011，100
D.0，100，110，1110，1100
解析：前缀编码：任一编码都不是其他任何编码的前缀（最左字串），D中110是1100的前缀
20 下列选项给出的是从根分别到达两个叶子结点路径上的权值序列，能属于同一棵哈夫曼树的是（D）
A.24，10，5和24，10，7
B.24，10，5和24，12，7
C.24，10，10和24，14，11
D. 24，10，5和24，14，6
解析：在构造哈夫曼的父结点权值=左右孩子权值之和
A：若两个10属于不同的两棵子树，根的权值为24与左右孩子权值之和20（10+10）不等；若两个10属于相同的子树，其权值10与左右孩子权值之和12（5+7）不等，所以A错误
B：根的权值为24与左右孩子权值之和20（10+12）不等，所以B错误
C：根的权值为24与左右孩子权值之和24（10+14）相等，权值为10左右权值分别为10和0，而权值为14的左右权值为11和3，明显不符合哈夫曼树构造原理，所以C错误
D.根的权值为24与左右孩子权值之和24（10+14）相等，权值为10左右权值分别为5和5，而权值为14的左右权值为6和5，符合哈夫曼树构造原理
图文解释请点击哈弗曼树的路径问题
21 若森林F有15条边，25个结点，则F包含树的个数是（C）
A.8 B.9 C.10 D.11
解析：由森林中树的个数与结点数关系可推导：一棵树的边数=结点数-1，每多一棵树，结点数就少一个，所以n棵树时，边数=结点数-n。F树个数n=25-15=10
22 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有两个子结点。若T有k个叶结点，则T的结点总数为（A）
A.2k-1 B.2k C.k^2 D.2^k -1
解析：由题目可得，这棵树是满二叉树，设这棵树的高度为h，则其叶子结点数k=2^(h-1)，则总结点数为2 ^h -1，即2k-1
23 已知字符集{a，b，c，d，e，f}，若各字符出现的次数分别为6，3，8，2，10，4，则对应字符集中各字符的哈夫曼编码可能是（A）
A.00，1011，01，1010，11，100
B.00，100，110，000，0010，01
C.10，1011，11，0011，00，010
D.0011，10，11，0010，01，000
解析：如下图所示，构造哈夫曼树，从哈夫曼树不难发现，db编码是最长的，排除了BD选项，a是根的左子孙结点，b是根的右子孙结点，哈夫曼编码的第一位是不同的，排除C
24 对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要存储单元数量至少是（A）
A.31 B.16 C.15 D.10
解析：对于完全二叉树，只要从根起按层存储依次自上而下自左至右存储即可；而对于一般二叉树，应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量里，常用0来表示不存在此结点，通俗讲就是占位，不管有多少结点，直接当作完全二叉树来存储，不存在的标0。所以高度为5的二叉树需要存储单元数量：2^5 -1=31
25 某森林F对应的二叉树为T，若T的先序遍历序列为a，b，d，c，e，g，f，中序遍历序列为b，d，a，e，g，c，f，则F中树的棵树是（C）
A.1 B.2 C.3 D.4
解析：如下图所示：根据先序遍历+中序遍历画出二叉树，再将其转为森林，得到3棵树
26 若某二叉树有5个叶子结点，其权值分别为10，12，16，21，30，则其最小带权路径长度（WPL）是（B）
A.89 B.200 C.208 D.289
解析：
3.课后习题
题目
1.对于一棵具有n个结点的树，该树中所有的结点的度数之和是________。
2.深度为h的完全二叉树至少有________个结点；至多有________个结点。
3.设一棵完全二叉树中有500个结点，则该二叉树的深度为________；若用二叉链表作为该完全二叉树的存储结构，则共有________个空指针域。
4.若一个完全二叉树有4182个结点，则度为1的结点个数为________，度为2的结点个数为________，叶子结点的个数为________，树的深度为________。
5.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为________个
6.已知完全二叉树T的第5层只有7个结点，则该树共有________个叶子结点。
7.设有10个值，构成哈夫曼树，则该哈夫曼树共有________个结点。
8.哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。
9.设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C
①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。
10.一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：
①设计一棵哈夫曼树；（画出其树结构）
②计算其带权路径长度WPL；
③尝试着写出6种字符的一种哈夫曼编码；
作答
文章来源：https://www.toymoban.com/news/detail-798357.html
正确答案
这章主要内容是二叉树，把上面的题都会了，差不多没啥问题了。今天要提前去学校，明天要做志愿迎新，后天要是有空再写文章来源地址https://www.toymoban.com/news/detail-798357.html
到了这里，关于数据结构-树和二叉树篇的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
