408数据结构

第一章 绪论
第二章 线性表
绪论、线性表选择题做题笔记
第三章 栈、队列和数组
栈、队列和数组选择题做题笔记
第四章 串
第五章 树与二叉树
树与二叉树选择题做题笔记

---

---

• 本章奇技淫巧：由于多是选择题，只需要代入特殊值对不同选项进行排除即可，或者一些比较特殊的树来推出答案，以下便证明一些正规证法

第一节 树的基本概念

（1）知识点补充

• 树是一种递归的数据结构
• 结论一：度为m，具有n个结点的树的最小高度h为[logm (n(m-1)+1)]
• 【推导】为使树的高度最小，在前h-1层，每层的结点都应达到最大值，即：1，m，m^2…，因此前h-1层的总结点为N1：（m ^ (h-1)-1）/(m-1)，前h层的总结点为N2：（m ^ h-1）/(m-1)，则n应该满足N1<n<=N2，解得：h-1<logm (n(m-1)+1)<=h，则h最小为[logm (n(m-1)+1)]（向上取整的高斯函数）
• 结论二：对于一颗树：结点个数=度和+1/边长+1
• 【证明】每个边/度下面就对应一个结点，但是根节点没有对应的边/度，所以+1

（2）错题归纳

• 本节考点一：结点个数还有树的高度的最值问题
• 本节考点二：不同度数结点的个数之间的关系

【2010年统考】在一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，,，Nm个度数为m的结点，则该树中有几个叶节点

• 正确答案：（（i-1）Ni）（i从2到m的累加）+1
• 标准分析：
• （1）由结点为各度数结点个数之和：N=N0+N1+N2+…+Nm
• （2）由结点个数=度数之和+1：N=N1+2N2+3N3+…+mNm+1
• （3）两式相减：N0=N2+2N3+…+(m-1)Nm+1

第二节 二叉树的概念

（1）知识点补充

• 度为2的树最少有_____个结点
• 答;3个

（2）错题归纳

判断题：结点按完全二叉树层序编号的二叉树中，第i个结点的左孩子的编号为2i（ ）

• 答：错误。未必存在左孩子。

具有n个结点且高度为n的二叉树的数目为_________

• 【分析】n个结点n行，因此每行一个结点，但是除了根节点之外，每个结点都有可能是上一个结点的左孩子结点和右孩子结点两种情况，因此一共有2^（n-1）种可能

【一个常见的坑】已知一颗完全二叉树的第6层（根所在层为第一层）有8个叶节点叶节点，则完全二叉树的结点个数最少为______

• 答：39
• 【分析】可能是前8个也可能是后8个

【一道好题】一颗有124个叶节点的完全二叉树，最多有____个结点

• 答：248个

一棵有n个结点的二叉树采用二叉链存储结点，其中空指针数为______

• 【分析】n个结点则一共有2n个指针域，n-1个非空指针域，因此空指针域为2n-（n-1）=n+1

一棵有n个结点的二叉树采用三叉链存储结点，其中空指针数为______

• 【分析】三叉链就是在二叉链的基础上，根节点的双亲指针为空，因此为n+2

判断：二叉树中，每个叶节点均被一个指针指向

• 【分析】当只有一个结点时，根节点就是叶节点，此时没有指针指向他

在一棵完全二叉树中，含有n个叶节点，当度为1的结点个数（1）为1时（2）为0时，该树的高度是多少？

• 【分析】结点的总个数N=n0+n1+n2=n1+2n2+1
• （1）N=n+1+n2=1+2n2，解得n2=n-1，则共有N=2n个结点
• （2）N=n+n2=2n2+1，解得n2=n-1，则共有2n-1个结点
• 再根据第一节的结论即可得到答案

第三节 二叉树的遍历和线索二叉树

（1） 错题归纳

在二叉树中有两个结点m和n，若m是n的祖先，则使用_____遍历可以找到从m到n的路径

• 答：后序遍历
• 【分析】
• （1）首先如果不考虑借助栈，无论是前序中序还是后序，就算你找到了，中间也会有一大堆杂碎，因此不可能实现
• （2）考虑栈的作用，对于遍历时候的进出栈，读取了就是出栈，暂时不读就是进栈，因此先序肯定不行，中序如果在右子树就寄了，后序就刚刚好，进栈的全是n的祖先结点！

下列不能唯一确定一棵二叉树的是________–
A. 层次遍历+中序遍历
B. 先序遍历+中序遍历
C. 后序遍历+中序遍历
D. 先序遍历+后序遍历

• 答：D
• 【分析】中序+另外三个其中一个即可

线索二叉树是一种______-结构
A. 逻辑
B, 逻辑和存储
C. 物理
D. 线性

• 【分析】只是改变了物理存储上指针的指向，因此选C

【简单但哪里怪怪的】一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是______

• 答：2个

二叉树线索化后仍不能有效解决的两个问题为_____________–

• 答：（1）后序线索二叉树的后序后继（2）先序线索二叉的先序前驱

[细节拉满]若X为二叉中序线索树一个有左孩子的结点，且X不为根，则X的前驱是________
A. X的左子树中最右的结点
B. X的左子树中最右的叶节点

• 答：A

_________线索树遍历仍需要栈的支持

• 答案：后序
• 【分析】画图分析看看，，右孩子退回根结点必须通过栈

第四节 树、森林

（1）错题归纳

已知一棵有2011个结点的树，叶节点的个数为116，则该树对应的二叉树中右孩子的结点的个数为________-

• 答案：1896
• 【方法一】树转化成二叉树，树的每个分支结点的所有子孩子中最右边的那个没有右孩子，，根结点转换后也没有右节点，因此对应二叉树中无右孩子的结点个数=分支结点数+1=2011-116+1=1896
• 【方法二】特殊求解

常考点：给出森林的遍历次序时，其实是给出了该森林对应二叉树的遍历次序，但是！！！！这只是对于中序和前序而言的，森林的后根遍历和与之对应的二叉树的后序遍历没有半毛钱关系！

例题：已知森林F和与之对应的二叉树T，若F的先根遍历序列是abcdef，后根遍历为badfec，则T的后序遍历序列是____

• 答：bfedca

若将一棵树T转化成对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是__________-

• 答：中序遍历
• 【解题方法】举例说明

设某树的孩子兄弟链表示中共有6个空的左指针域、7个空的右指针域，包括5个结点的左右指针均为空，则该树中叶结点的个数为______

• 答：6个
• 【方法一】特殊法，画个符合条件的图就好了
• 【方法二】叶结点应该满足的条件：没有孩子，那么在孩子表示法中的表现就是没有左孩子，所以答案是6

设F是一个森林，B是由F变换来的二叉树，若F中有n个非终端结点，则B中右指针域为空的结点有____个

• 答案：n+1
• 【巧计】随便画个树数一下然后转化成二叉树再数一下就搞定（不得不说这一章特殊值法真的很重要）
• 【推导】B中右指针域为空，说明该结点没有兄弟结点，那么没有兄弟结点的是哪些结点呢？每个分支结点的所有孩子里面最右边那个，也就是说，从个数上，没有兄弟结点的结点数目和分支结点的数目的个数是一样的，因为叶子结点都没有孩子，因此不会产生没有兄弟的结点。

第五节 树与二叉树的应用

（1）知识点补充

• （1）哈夫曼编码设计出来的是总长度最短的二进制 前缀编码
• （2）对于哈夫曼树的编码长度即为WPL，对于n位固定长度编码，编码长度=n * 叶子结点权重和

（2）错题归纳

判断题：哈夫曼树的结点总数肯定是偶数（ ）

• 答：正确
• 【分析】设一开始有n个结点要构成哈夫曼树，则会额外产生n-1个分支结点，因此总结点个数为2n-1，为奇数

判断题：哈夫曼树的带权长度等于其所有分支结点的取值之和

• 答：正确
• 【分析】哈夫曼的带权路径长度有两种计算方法：（1）所有叶结点的带权路径程度之和（2）所有分支结点的权值之和

判断题：哈夫曼树中没有度数为1的结点

• 答：正确

若度为m的哈夫曼树中，叶结点个数为n，则非结点的个数为________–

• 答：（n-1）/（m-1）
• 【分析】
• （1）度为m是指结点的度不是整棵树的度
• （2）n个叶结点有n-1个非叶结点这个结论仅适用于度为2的哈夫曼树
• （3）题目分析：一棵度为m的哈夫曼树只会有度为0/m的结点，设度为m的结点有k个，则总结点个数=n+k=mk+1，记得k=（n-1）/（m-1）

下列选项给出的是从根到两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_____
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

• 答：D
• 【分析】
• A. 24的一个孩子为10，则另一个孩子为14，但是10不可能两个孩子为5和7（5+7=12），因此排除
• B. 24的两个孩子不可能是10和12，排除
• C. 24的两个孩子是10和14，但10的孩子不可能是10
• D. 24的孩子为10和14，10的孩子为5和5，14的两个孩子为6和8，符合哈夫曼

在由6个字符组成的字符集S中，各字符出现的频次分别为3，4，5，6，8，10，为S构造的哈夫曼编码的加权平均长度为____

• 答：2.5
• 【分析】加权平均除的是权值和而不是结点数，即90/36=2.5

【不难但奇怪】对任意给定的含n个字符的有限集S，用二叉树表示S的哈夫曼编码集和定长编码集，分别得到二叉树T1和T2，下列叙述中正确的是_____
A. T1和T2的结点数相同
B T1的高度大于T2的高度.
C. 出现频次不同的字符在T1中处于不同的层
D. 出现频次不同的字符在T2中处于相同的层

• 答：D

---

总结

本章题目大多数是用奇技淫巧解决的，但实际上有很多是可以推可以的，还是知识不够扎实或者太懒了，需要再买一本练习来练了。