No.1
树的概念
本考点主要考查树的定义、树的性质。请同学们了解树的每一层的结点分布情况，以及树的叶子结点树计算方法。
树的基本概念，树的结点计算方法
NO
1
在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结，10个度为1的结点，则树T的叶结点个数是（）。
A.41
B.82
C.
D.
答案解析
本题画图或者计算，都不太容易。我们可以这样来推理：这棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点。所以，树的度数为20×4+10×3+1×2+10×1=。因为根结点没有父结点，所以，树中一共有结点+1=个。除去这20+10+1+10=41个结点，其他的82个结点是叶子结点。注意，这里不用再出去父结点了。因为父结点的度肯定不为零，即不是叶子结点。也就是说，父结点的度数一定是1,2,3,4当中的一个，已经在题目中所述的结点范围之内了。B
No.2
二叉树
本考点是考试的重点内容，常以选择题、作图题的形式出现，请同学们多多练习。涉及到二叉树的遍历、线索化二叉树、完全二叉树、二叉排序树、平衡二叉树等，并把二叉树的顺序存储结构和链式存储结构也归纳到这部分。所以，内容较多，多花点时间，争取多学习一些。
平衡二叉树的应用
NO
2
下列二叉排序树中，满足平衡二叉树定义的是（）。
答案解析
平衡二叉树或为空树，或为如下性质的二叉排序树：(1).左右子树深度之差的绝对值不超过1；(2).左右子树仍然为平衡二叉树。
我们定义平衡因子BF=左子树深度－右子树深度，平衡二叉树每个结点的平衡因子只能是1，0，-1。若结点平衡因子的绝对值超过1，则该二叉排序树就是不平衡的。显然，A答案的二叉树根节点的左子树深度为2，右子树深度为0，不是平衡二叉树。C答案对应的二叉树根节点的左子树深度为1，右子树深度为3，显然也不是平衡二叉树。D答案对应的二叉树根节点的左子树深度为4，右子树深度为1，显然也不是平衡二叉树。B答案每一个节点都满足平衡二叉树的定义，所以是平衡二叉树。B
完全二叉树的结点个数计算方法
NO
3
已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。A.39B.52C.D.
答案解析
对于完全二叉树而言，若有7层，则第一层到第6层的结点应该全部都是满的。第一层1个结点、第2层2个结点、第三层4个结点、第4层8个结点、第五层16个结点、第6层32个结点。因为第6层的32个结点中有8个是叶子结点，所以有24个非叶子节点。该完全二叉树结点最多的情况是，这24个结点都分别有左右孩子时，整棵完全二叉树的节点数目最多，即总共有1+2+4+8+16+32+48=。C
二叉树的后序线索化
NO
4
4.下面线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）。
答案解析
对于某一种遍历顺序对应的线索化，只需写出对应的遍历序列，然后修改空指针域分别指向该遍历序列的前驱和后继即可。例如，本题中的二叉树的后序遍历可得到序列d、b、c、a。那么，d是第一个元素，没有前驱，所以其左指针域原来为空，线索化时亦为空；a是最后一个元素，但是其左右孩子都不为空，所以不需要考虑该结点的线索化；其余的b和c结点都各有一个前驱结点和后继结点。那么，将d右指针域（初始为空）调整并指向其后继结点b。将b结点的左指针域调整指向其前驱结点d，因为b的右指针域不为空，所以线索化过程中不需要调整。c的左右指针域都为空，令其左指针域指向其前驱结点b，右指针域指向其后继结点a。D
二叉树的遍历
NO
5
若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是（）。A.1，2，3，4B.2，3，4，1C.3，2，4，1D.4，3，2，1
答案解析
已知二叉树的前序遍历序列和后序遍历序列，不能唯一确定一棵二叉树。只有在已知前序遍历序列或者后序遍历序列的情况下，又知道中序遍历序列，才能唯一确定一棵二叉树。遍历一棵二叉树，要使得前序遍历序列和后序遍历序列刚好相反，那么必须保证每一个结点都只有一个孩子结点。故而，二叉树的高度为4。那么，在前序遍历序列为1、2、3、4，后序遍历序列为4、3、2、1的情况下，该二叉树第1、2、3、4层的结点依次为1、2、3、4。显然，A、D答案可对应下图所示的二叉树：
C
预览时标签不可点收录于话题#个上一篇下一篇