3.2 二叉树

3.2 二叉树

　　考试大纲涉及本节的知识点有：二叉树的定义、二叉树的性质、二叉树的存储结构、二叉树的遍历、线索二叉树、二叉排序树和平衡二叉树。

选择题

　　1．选择题
　　● 如果根的层次为1，具有61个节点的完全二叉树的高度为 （1） 。
　　（1）A．5 B．6 C．7 D．8
　　● 在一棵非空二叉树中，叶子节点的总数比度为2的节点总数多 （2） 个。
　　（2）A．1 B．0 C．1 D．2
　　● 在具有100个节点的树中，其边的数目为 （3） 。
　　（3）A．101 B．100 C．99 D．98
　　● 一棵完全二叉树上有1001个节点，其中叶子节点的个数是 （4） 。
　　（4）A．500 B．254 C．505 D．以上答案都不对
　　● 在一棵三元树中度为3的节点数为2个，度为2的节点数为1个，度为1的节点数为2个，则度为0的节点数为 （5） 个。
　　（5）A．4 B．5 C．6 D．7
　　● 一个具有1025个节点的二叉树的高h为 （6） 。
　　（6）A．11 B．10 C．11～1025 D．10～1024
　　● 一棵查找二叉树，其节点A、B、C、D、E、F依次存放在一个起始地址为n（假定地址以字节为单位顺序编号）的连续区域中，每个节点占4个字节：前两个字节存放节点值，后两个字节依次放左指针、右指针。
　　若该查找二叉树的根节点为E，则它的一种可能的前序遍历为 （7） ，相应的层次遍历为 （8） 。在以上两种遍历情况下，节点C的左指针Lc的地址为 （9） ，Lc的内容为 （10） 。节点A的右指针Ra的内容为 （11） 。
　　（7）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
　　（8）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
　　（9）A．n+9 B．n+10 C．n+12 D．n+13
　　（10）A．n+4 B．n+8 C．n+12 D．n+16
　　（11）A．n+4 B．n+8 C．n+12 D．n+16
　　● 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 （12） 。
　　（12）A．ABCDEFGHIJ B．ABDEGHJCFI C．ABDEGHJFIC D．ABDEGJHCFI
　　● 前序遍历序列与中序遍历序列相同的二叉树为 （13） ，前序遍历序列与后序遍历序列相同的二叉树为 （14） 。
　　（13）A．根节点无左子树的二叉树
　　B．根节点无右子树的二叉树
　　C．只有根节点的二叉树或非叶子节点只有左子树的二叉树
　　D．只有根节点的二叉树或非叶子节点只有右子树的二叉树
　　（14）A．非叶子节点只有左子树的二叉树 B．只有根节点的二叉树
　　C．根节点无右子树的二叉树 D．非叶子节点只有右子树的二叉树
　　● 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是 （15） 。
　　（15）A．0 B．1 C．2 D．不确定
　　● 若X是二叉中序线索树中一个有左孩子的节点，且X不为根，则X的前驱为 （16） 。
　　（16）A．X的双亲 B．X的右子树中最左的节点
　　C．X的左子树中最右节点 D．X的左子树中最右叶节点
　　● 如图3-1所示的二叉树有下列性质：除叶子节点外，每个节点的值都大于其左子树上的一切节点的值，并小于等于其右子树上一切节点的值。这是一棵 （17） 树。

　　现有一个斐波那契数列｛an｝，a0=a1=1，ak=ak-1+ak-2，k=2,3…。若把｛a1,a2,…,a9｝填入该二叉树，一般可采用 （18） 遍历法遍历该树上全部节点，得到由节点的值组成的从小到大顺序排列的序列。对本题给出的二叉树图形填入｛a1,…,a9｝后，其节点n8的值为 （19） ，根节点的值为 （20） 。若欲插入｛a1,…,a9｝的平均值，则应该再 （21） 增加一个节点。
　　（17）A．平衡二叉树 B．B树 C．完全二叉树 D．二叉排序树
　　（18）A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历
　　（19）A．3 B．1 C．8 D．13
　　（20）A．5 B．21 C．34 D．55
　　（21）A．n6 B．n7 C．n8 D．n9
　　● 在常用的描述二叉排序树的存储结构中，关键字值最大的节点 （22） 。
　　（22）A．左指针一定为空 B．右指针一定为空
　　B．左右指针均为空 D．左右指针均不为空
　　2．选择题练习答案与分析
　　题号（1）答案 B
　　习题分析：
　　根据二叉树的性质，具有n个节点的完全二叉树的深度为 +1，因此含有61个节点的完全二叉树的高度为 +1，即应该为6层。
　　题号（2）答案 C
　　习题分析：
　　我们用n0表示度为0（叶子节点）的节点总数，用n1表示度为1的节点总数，n2为度为2的节点总数，n表示整个完全二叉树的节点总数。显然，n=n0+n1+n2，根据二叉树和树的性质，还可得到n=n1+2n2+1（所有节点的度数之和+1=节点总数）。根据这两个公式，可得知：n0+n1+n2= n1+2n2+1=n，不难推出n2=n0-1，即：n0=n2+1。
　　题号（3）答案 C
　　习题分析：
　　这道题实际上是很简单的，在一棵树中，除了根节点之外，每一个节点都有一条入边，因此总边数应该是100-1，即99条。
　　题号（4）答案 D
　　习题分析：
　　二叉树的公式：n=n0+n1+n2=n0+n1+（n0-1）=2n0+n1-1。而在完全二叉树中，n1只能取0或1。若n1=1，则2n0=1001，可推出n0为小数，不符合题意；若n1=0，则2n0-1=1001，则n0=501。
　　题号（5）答案 C
　　习题分析：
　　第二题分析中已经推导出了在二叉树中，度为2的节点和叶子节点个数之间的关系，即n0=n2+1；本题中的三叉树的推导过程类似：n=n0+n1+n2+n3，根据三叉树的定义，还可得到n=n1+2n2+3n3+1（所有节点的度数之和+1=节点总数）。综合以上两公式：n0+n1+n2+n3= n1+2n2+3n3+1，因此，n0=n2+2n3+1。代入题中的已知条件，可得n0=6。
　　已知一棵度为k的树中有n1个度为1的节点，n2个度为2的节点，……，nk个度为k的节点，问树中有多少叶子节点？对于这种一般情况，要能进行灵活运用，举一反三！
　　题号（6）答案 C
　　习题分析：
　　本题重点在于看清题意，题中只给出了二叉树中节点的个数，而并未说明是否为完全二叉树。对于一个具有n个节点的二叉树来说，该树为完全二叉树时其高度最小；而当n个节点中n1个节点的度为1而只有一个叶子节点时，该树的高度最大，即高度为n，如图3-2所示。
　　而其高度最小时的高度，根据完全二叉树的相关性质，可得：k= +1=11。
　　综合以上分析，可知正确答案为C。
　　题号（7）  （8）  （9）  （10）  （11）答案 D  A  B  A  B
　　习题分析：
　　本题中有6个节点，其关键码值分别为A、B、C、D、E、F，此时值的大小是按字典顺序排列的。题中指定E是根节点，因为A、B、C、D的值都小于E，仅有F大于E，所以，A、C、B、D属于左子树，F属于右子树。根据（7）的4个选项，显然只有D才是可能的前序遍历序列。
　　既然已经知道前序遍历序列为EACBDF，且知道二叉树的左子树是ACBD，再根据前序遍历的性质和A是左子树的根节点，可知CBD均是A节点下的右子树（A的左子树为空）。同理，B和D分别是C的左子树和右子树。最后所得的二叉树如图3-3所示。

　　根据图3-3，立即可得该二叉树的层次遍历序列为EAFCBD。
　　根据习题条件，节点A、B、C、D、E、F依次存放，且每个节点占4个字节（前两个字节存放节点值，后两个字节依次放左指针、右指针），所以C的起始地址为n+8，Lc的地址为n+10。根据图3-3所示，Lc中应存放B的地址，由于且起始地址为n，因此B的地址为n+4，Lc的内容是n+4。节点A的右指针Ra中应存放C的地址，而C的地址为n+8，即Ra的内容是n+8。
　　题号（12）答案 B
　　习题分析：
　　根据前序、后序遍历的特点，可以确定A是根节点（在后序遍历的最后一个），再根据中序遍历的特点，可以知道DBGEHJ为左子树，CIF为右子树。
　　再看右子树的后序遍历为IFC，可以确定C为右子树的根节点；再加上中序为CIF，说明C无左子树，只有右子树。
　　而左子树的后序遍历为DGJHEB，因此B为左子树的根节点，再结合中序遍历，可以得知B的左子树只有D，GEHJ都是右子树。
　　GEHJ子树的后序遍历是GJHE，说明E是根，HJ为E的右子树，G是E的左子树。最后可以H为HJ子树的根，J为右子树。
　　通过以上分析，就可以绘制出这棵树，如图3-4所示：

　　然后再由前序遍历，可以得到：ABDEGHJCFI。
　　题号（13）  （14）答案 D  B
　　习题分析：
　　前序遍历的顺序是“根、左、右”，而中序遍历的顺序则为“左、根、右”，因此只有所有的子树都没有左子树，就是“只有根节点的二叉树或非叶子节点只有右子树的二叉树”时，其前序遍历和中序遍历的结果会相同。
　　而后序遍历则是“左、右、根”，这种情况，如果有左子树或右子树都是不可能产生相同的遍历序列的，因此只有一种可能，即没有左、右子树，因此满足要求的是“只有根节点的二叉树”。
　　题号（15）答案 B
　　习题分析：
　　根据二叉树线索化的概念，当其左、右子树均不为空时，其先序序列中的第一个为根节点，最后一个节点为其最右下的叶子节点。如图3-4中的二叉树，其先序序列为ABDEGHJCFI。对这种二叉树线索化时，显然除了第一个和最后一个节点外，其余节点都有明显的前驱和后继。因此，只需要考虑这两个节点的指针域情况。对第一个节点，即根节点，因为其左、右子树都不为空，所以该节点无空指针域；而对最后一个节点，该节点为叶子节点，即左、右子树都为空，那么该节点在先序序列中必然有一个前驱，因此该节点就只有一个空指针域。从以上分析可以得出，正确答案为B。
　　题号（16）答案 C
　　习题分析：
　　这里考查对二叉树中序线索的理解。X是非根节点，且其有左子树，则其中序线索的前驱即为其左子树按中序遍历的最后一个节点，也就是其左子树中的最右节点。
　　题号（17）  （18）  （19）  （20）  （21）答案 D  B  A  B  D
　　习题分析：
　　二叉排序树的定义：若除叶子节点外，每个节点的值都大于其左子树上的一切节点的值，并小于等于其右子树上一切节点的值，则说明它是一棵二叉排序树。对于二叉排序树进行中序遍历，就可以得到一个排好序的节点序列。
　　根据斐波那契数列的规则，a1，a2，…，a9的值应该是1，2，3，5，8，13，21，34，55。而图3-5所示的二叉树的中序遍历应该是：n7、n4、n8、n2、n5、n9、n1、n3、n6，因此一一对应一下，就可以得知n8的值应该是3，n1的值应该是21。

　　因此要想插入平均数（约为16），显然应该加在n9的右子树上。
　　题号（22）答案 B
　　习题分析：
　　来分析一下排序二叉树关键字值最大的节点的存储位置有何特点。以序列（50，72，43，85，75，20，35，45，65，30）为例，最大节点85的位置有两种情形，分别如图3-6和图3-7所示。

　　在这两种情形中，节点85都没有右子树，因为只有比85更大的节点，才能成为它的右子树，而这里的85是最大的节点，所以节点85不可能会有右子树，所以节点85的右指针一定为空。
　　3．训练自测表（如表3-2所示）

表3-2 选择题练习自测表

续表