考研 数据结构，考研数据结构真题
文 彦 考 研
让 | 梦想 | 有迹可循
老师介绍
小鱼学姐：2017年考入电子科技大学计算机技术专业，专业课成绩129分。研究生入学后便开始做考研辅导，截止目前已辅导三十多名学生。擅长进行大纲、考点剖析，将知识点与习题相结合，用通俗的事例让学生理解相关术语，耐心细致、深受好评。
这是成电计算机考研第 11 篇文章
大家好~我是电子科大计算机学院的17级的小鱼学姐，这篇文章我们继续讲解数据结构中的另一个重要的章节—–树：
树是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵树，称为根的子树。树的定义具有递归性，即“树中还有树”。
那我们再来一下二叉树的概念：
二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成。基本特征:① 每个结点最多只有两棵子树;② 左子树和右子树次序不能颠倒。
在电子科大的期末考试题中曾出过关于树和二叉树的一个简答题。考研题中，就有相当一部分来自于学校的期末考试，只不过难度比期末考试稍高，比全国统考稍微简单一些。请大家看一下这道题：
度为2的树，和度为2的二叉树一样吗？为什么？
看到这个题，很多同学都会感觉是同一棵树，其实不然，因为二叉树有严格的左右之分，交换一下左右子树就是两棵不同的树，而树不分左右，所以不一样。
知识点 关于二叉树的几个性质：
1. 在二叉树的第 i 层上至多有 2i －1个结点。
证明：当i=1时，只有根结点，2i-1=20=1。
假设对所有j，i>j1，命题成立，即第j层上至多有2 j-1 个结点。
由归纳假设第i-1 层上至多有 2i－2个结点。
二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i－2= 2i-1。
（这个比较简单，不再叙述）
2. 深度为 k 的二叉树至多有 2 k-1个结点，其中k >=1。
证明：由性质1可见，深度为k的二叉树的最大结点数为
（这个性质也相对比较简单，不再叙述）
证明：由性质1可见，深度为k的二叉树的最大结点数为
（这个性质也相对比较简单，不再叙述）
3.（重要！！！）对任何一棵二叉树T, 如果其叶子结点数为 n0, 度为2的结点数为 n2,则n0＝n2＋1。
证明：n = n0 + n1 + n2 ①
分支数e = n – 1 = 2n2 + n1 ②
因此，2n2 + n1 = n0 + n1 + n2 – 1
n0 = n2 + 1
这个性质是经常考题中会隐含需要用到的知识点，非常重要，二叉树中度为0的结点个数等于度为二的结点个数加一，证明的过程也必须会，因为会了二叉树的这个知识点的证明就能处理三叉树等n叉树的结点和度之间的关系。对于二叉树而言，因为结点一共分成三类，即度为零的结点，度为一的结点，度为二的结点，那么第一个等式就是结点个数n等于度为零的结点个数n0，加上度为一的结点个数n1，再加上度为2的结点个数n2;另一个方面，根据结点个数和分支之间的关系入手，对于一颗二叉树而言，从小往上看，每一个结点都有一个分支与其对应，根节点除外，所以结点比分支个数多了一个，又分支个数和度有关系，从上往下看，度为1的结点有一个分支，度为2的结点有两个分支，度为零的结点没有分支，所以分支数应该为2乘以n2，加上1乘以n1+0乘以n0，分支数加一就等于结点数。和第一个式子联立即可得到要证明的结论。
证明：n = n0 + n1 + n2 ①
分支数e = n – 1 = 2n2 + n1 ②
因此，2n2 + n1 = n0 + n1 + n2 – 1
n0 = n2 + 1
这个性质是考题中经常会涉及到的知识点，非常重要。二叉树中度为0的结点个数等于度为二的结点个数加一，证明的过程也是必须要掌握的，因为会了二叉树的这个知识点的证明就能处理三叉树等n叉树的结点和度之间的关系。对于二叉树而言，因为结点一共分成三类，即度为零的结点，度为一的结点，度为二的结点，所以第一个等式就是结点个数n等于度为零的结点个数n0，加上度为一的结点个数n1，再加上度为2的结点个数n2；另一方面，根据结点个数和分支之间的关系入手，对于一棵二叉树而言，从小往上看，每一个结点都有一个分支与其对应，根节点除外，所以结点比分支个数多了一个；又分支个数和度有关系，从上往下看，度为1的结点有一个分支，度为2的结点有两个分支，度为零的结点没有分支，所以分支数应该为2乘以n2，加上1乘以n1+0乘以n0，分支数加一就等于结点数。和第一个式子联立即可得到要证明的结论。
4. 具有 n (n >=0) 个结点的完全二叉树的深度为log2(n) 下取整＋1
2h-1-1< n<=2h – 1,
取对数
h－1<= log2n < h，
又h是整数，因此有：
h = log2(n)下取整＋1
证明：设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有
2h-1-1< n<=2h – 1,
取对数
h－1<= log2n < h，
又h是整数，因此有：
h = log2(n)下取整＋1
（这个性质也相对比较简单，一般会出选择填空题）
5.若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：
(1)若i=1，则该结点是二叉树的根，否则，编号为i/2下取整的结点为其父亲结点。
(2)若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点。
(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。
（这个性质在一些题中也能用到，用该性质能提升解题速度）
下面分享一下关于三种遍历方式的递归算法。
对于先序递归遍历，其思想是：
若二叉树t非空，则：
访问根结点t；
前序遍历t的左子树；
前序遍历t的右子树；
对应的算法为：
void preorder（ BiTree t）
{
if (t) {
putchar(t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
同理中序和后序算法的递归算法如下：
中序遍历
void inorder( BiTree t)
{
if ( t ) {
inorder(t->lchild);
putchar(t->data);
inorder(t->rchild);
}
}
后序遍历
void postorde(BiTree t)
{
if ( t ) {
postorder(t->lchild);
postorder(t->rchild);
putchar(t->data);
}
}
这三个递归算法写起来比较简单，但是要真正把握递归的含义却不简单。希望大家在遇到关于给出先序和中序，或者给出后序和中序序列让你画出某一序列的线索二叉树或者画出二叉树等的题目时，认真思考，细心作答。
下篇关于数据结构的文章我们会分析非递归的遍历算法，大家要加油啦~
今天的干货分享就先到这里喽~
大家有任何课程问题可以入群或
直接添加文末微信
与老师一对一咨询哦~
1.来文彦，考上研！报名方式：淘宝搜“文彦考研”2.成电计算机考研群号：6126308353.我是文彦考研，wyky66666，加小彦微信 获取更多考研干货~4.文彦成电考研微信公众号：uestcwykycom
公众号推荐阅读
20成电计算机考研 | 操作系统知识点大汇总（下）
20成电计算机考研 | 操作系统知识点大汇总！
20届电子科大计算机|你有一份复习攻略，请查收~
20届成电计算机 | 被录取的开心！
20届成电计算机 | 计算机考研新形势之（一）：预面试
20届成电计算机 | 计算机考研新形势之（二）：初试+复试笔试
20成电计算机 | 全方位解读夏令营
20成电计算机 | 暑假来袭，课后作业第一弹！
20届成电计算机 | 计算机考研新形势之（三）：学硕/专硕
20成电计算机 | 数据结构习题在这里，赶紧练练手！
考研 数据结构(考研数据结构真题)