各位学员大家好，大家在学习程序设计语言的时候，树结构和表达式经常结合起来考察，树结构在以后的考试中尤其重要。为了让大家快速掌握这方面的知识点，接下来就带领大家一起来学习一下！
例题1：某算术表达式用二叉树表示如下，该算术表达式的中缀式为( 1 )，其后缀式为( 2 )。
1、A、a-b+c*d
B、a-(b+c)*d
C、(a-(b+c))*d
D、a-(b+c*d)
2、A、abc+-d*
B、abcd*+-
C、ab-c+d*
D、abcd+*-
【昊洋详解】：本题考查二叉树和算术表达式的基础知识。
树：是n (n≥0)个结点的有限集合，当n=0时称为空树。在任一非空树(n>0) 中，有且仅有一个称为根的结点，其余结点可分为m (m≥0)个互不相交的有限子集T1，T2，…，Tm，其中，每个Ti又都是一棵树，并且称为根结点的子树。树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。
二叉树：是n (n≥0)个结点的有限集合，它或者是空树(n=0)， 或者是由一个根结点及两棵不相交的且分别称为左、右子树的二叉树所组成。可见，二叉树同样具有递归性质。
需要特别注意的是，尽管树和二叉树的概念之间有许多联系，但它们是两个不同的概念。树和二叉树之间最主要的区别是：二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。另外，二叉树结点最大度为2，而树中不限制结点的度数。
有关中缀式和后缀式的问题，首先需要了解一下二叉树的三种遍历方式。
前序遍历（对应前缀式）：先访问根结点，再依次按前序遍历的方式访问根结点的左子树、右子树，子树本身也适用本规则。
中序遍历（对应中缀式）：先中序遍历根结点的左子树，再访问根结点，再中序遍历根结点的右子树，子树本身也适用本规则。其中中缀式最符合我们常规对表达式的书写方式，为了表示优先级，经常还需要加小括号。
后序遍历（对应后缀式）：先中序遍历根结点的左子树，再中序遍历根结点的右子树，再访问根结点，子树本身也适用本规则。其中后缀表达式也叫做逆波兰式。
二叉树采用中序遍历得中缀表达式：(a-(b+c))*d，采用后序遍历得后缀表达式：abc+-d*。
故本题目的正确答案为：1-C 2-A。
例题2：堆是一种数据结构，分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则( 1 )是一个小顶堆结构。堆结构用二叉树表示，则适宜的二叉树类型为( 2 )。对于10个结点的小顶堆，其对应的二叉树的高度(层数)为( 3 )。堆排序是一种基于堆结构的排序算法，该算法的时间复杂度为( 4 )。
1、A、10，20，50，25，30，55，60，28，32，38
B、10，20，50，25，38，55，60，28，32，30
C、60，55，50，38，32，30，28，25，20，10
D、10，20，60，25，30，55，50，28，32，38
2、A、普通二叉树
B、完全二叉树
C、二叉排序树
D、满二叉树
3、A、3
B、4
C、5
D、6
4、A、logn
B、nlogn
C、n
D、n²
【昊洋详解】：本题考查二叉树的基础知识。
对于n个元素的关键字序列{K1,K2,…,Kn}，当目仅当满足Ki<=K2i且Ki<=K2i+1(1
故第一空的正确答案为A。
二叉树：每个结点最多有两个子树的树结构，通常子树被称作左子树和右子树。
满二叉树：深度为k，且有2^k-1个节点的二叉树，每一层上的节点数都是最大节点数。
完全二叉树：除最后一层外，若其余层节点都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点。也就是说，如果把满二叉树从右至左、从下往上删除一些节点，剩余的结构就构成完全二叉树。如果从上到下，从左到右分别对满二叉树和完全二叉树进行编号的话，完全二叉树存在的所有编号和满二叉树是可以全部对上号的。其中，小顶堆是一种经过排序的完全二叉树。
二叉排序树：又称二叉查找树、二叉搜索树。它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
故第二空的正确答案为B。
对于一个完全二叉树，第1层为最多1个结点，第2层最多2个结点，第ｎ层最多2^(n-1)个结点，本题10个结点＝1+2+4+3，前三层的节点是满的，第四层只有3个节点，所以需要４层。
故第三空的正确答案为B。
如下表所示，八种常见的排序算法要求大家记住他们的平均时间复杂度和稳定性，其中堆排序的时间复杂度为O(nlogn)。
故第四空的正确答案为B。
（1）对下图所示的二叉树进行顺序存储(根结点编号为1，对于编号为i的结点，其左孩子结点为2i，右孩子结点为2i+1)并用一维数组BT来表示，已知结点X、E和D在数组BT中的下标分别为1、2、3， 可推出结点G、K和H在数组BT中的下标分别为( )。
A、10、11、12
B、12、24、25
C、11、12、13
D、11、22、23
（2）算术表达式a+b-c*d的后缀式是（） (-、+、* 表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。
A、ab+cd*-
B、abc+-d*
C、abcd+-*
D、ab+c-d*
（3）堆是一种数据结构，分为大顶堆和小顶堆两种类型，大（小）顶堆要求父元素大于等于（小于等于）其左右孩子元素，则（ 1 ）是一个大顶堆结构，该堆结构用二叉树表示，其高度（或层数）为（ 2 ）。
1、A、94，31，53，23，16，27
B、94，53，31，72，16，23
C、16，53，23，94，31，72
D、16，31，23，94，53，72
2、A、2
B、3
C、4
D、5
（4）已知某文档包含5个字符。每个字符出现的频率如下表所示。采用霍夫曼编码对该文档压缩存储，则单词“cade”的编码为（1 ），文档的压缩比为（ 2 ）。
1、 A、1110110101
B、1100111101
C、1110110100
D、1100111100
2、 A、20%
B、25%
C、27%
D、30%
（1）解析：本题考查二叉树的基础知识。
已知结点X、E和D在数组BT中的下标分别为1、2、3，对于编号为i的结点，其左孩子结点为2i，右孩子结点为2i+1。所以E的右孩子F的编号为2*2+1=5，同理：
F的右孩子节点G的编号为2*5+1=11；
G的左孩子节点K的编号为2*11=22；
G的右孩子节点H的编号为2*11+1=23。
故该题目的正确答案为：D。
（2）解析：本题考查程序语言中算数表达式的基础知识。
后缀式即逆波兰式，是逻辑学家卢卡西维奇发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+。这种表示法的优点是根据运算对象和运算符的出现次序进行计算，不需要使用括号，也便于实现求值。
a+b-c*d按照优先级，首先应该计算c*d，后缀式表示为cd*，然后计算a+b，其后缀式为ab+，最后计算前面两个结果的差值，所以最终的后缀式是ab+cd*-。
故该题目的正确答案为：A。
（3）解析：本题考察二叉树的基础知识。
对于n个元素的关键字序列{K1,K2,…,Kn}，当目仅当满足Ki<=K2i且Ki<=K2i+1(1<i<n/2)，则称该序列为小顶堆。若将其中的"<="换为">="则称其为大顶堆。题目问的是大顶堆，所以第一个元素肯定是最大的，可以排除C选项和D选项，将元素按照上述的公式依次带入A选项，发现94>=31，94>=53，31>=23，31>=16，53>=27，B选项带入后发现53不满足大于等于72的情况，所以第一空只有选项A满足大顶堆的要求。我们在例题中也说了，可以利用二叉树的方式求证，本题A选项的二叉树表示如下图所示，按照从上到下，从左到右的次序依次把选项中的元素填进去，大顶堆要求其父节点要大于等于其左右孩子节点，这种方法也可以验证只有A选项满足要求。
故该题目的第一空的正确答案为A。
大顶堆和小顶堆都是一种经过排序的完全二叉树。对于一个完全二叉树，第1层为最多1个结点，第2层最多2个结点，第ｎ层最多2^(n-1)个结点，本题6个结点＝1+2+3，前2层的节点是满的，第3层只有3个节点，第3层填满需要4个节点，所以一共需要3层。
故该题目的第二空的正确答案为B。
（4）解析：本题考察霍夫曼树的基础知识。
霍夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树或霍夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：
1)、将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；
2)、在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3)、从森林中删除选取的两棵树，并将新树加入森林；
4)、重复2)、3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
通过上述步骤和题干数据，构造哈夫曼树如下图所示：
编码规则为：左孩子为0，右孩子为1。
从根节点到该节点的所有编码连起来就是该节点的霍夫曼编码，由图可知，a的编码：0，b的编码100，c的编码111，d的编码110，e的编码：101。单词“cade”的编码连起来就是“1110110101”。
故第一空的正确答案为A。
压缩前，属于定长编码，每个字符用3位编码足够表示，压缩后编码长度是：1*40%+3*10%+3*20%+3*16%+3*14%=2.2，压缩率：（3-2.2）/3=27%。
故第二空的正确答案为C。
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2020年9月2日
作者：昊洋讲师
版权所有，侵权必究
