作业12

1-1 某二叉树的后序和中序遍历序列正好一样， 则该二叉树中的任何结点一定都无右孩子。(T) [解析]后序:L,R,root 中序:L,root,R 要想两个序列一样 一定无R

1-2 某二叉树的后序和中序遍历序列正好一样， 则该二叉树中的任何结点一定都无左孩子。(F)

1-4 若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树， 其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。() [解析]前序遍历A在B前面,假设 A和B在同一个双亲结点x下面 那么在中序遍历的时候,在访问到这个双亲结点的时候,一定会A, x, B的顺序访问 若不这么假设,那么A还是在一棵左子树上,B一定在一棵右子树上 最终还是L(A不确定在L左侧还是右侧,不影响),root,R(B不确定在R左侧还是右侧,不影响)

1-5 若一个结点是某二叉树的中序遍历序列的最后一个结点， 则它必是该树的前序遍历序列中的最后一个结点。(F) [解析]前序遍历的最后一个节点是根节点, 但中序遍历的最后一个节点, 不一定是根节点,所以不确定

1-6 某二叉树的前序和中序遍历序列正好一样， 则该二叉树中的任何结点一定都无左孩子。(T) [解析]前序:root,L,R中序:L,root,R.那就无左孩子 1-7 已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。(T) [解析]假设CAB是中序遍历的结果 那么C就是根节点,C左侧的AB就是右子树的部分,然后根据先序得出,B就是子树的根 A是B的左子树,满足假设

2-3 要使一棵非空二叉树的先序序列与中序序列相同， 其所有非叶结点须满足的条件是： A.只有左子树 B.只有右子树 C.结点的度均为1 D.结点的度均为2 [解析]先序:root,L,R 中序:L,root,R 所以只有右子树,没有左子树

2-4 已知一棵二叉树的树形如下图所示,其后序序列为{ e, a, c, b, d, g, f } 树中与结点a同层的结点是:(B) A.c B.d C.f D.g [解析]将图中的结点编号(从1开始),然后执行后序遍历得到的序列应该和 题目中是一样的或者说对应的

2-6 若一棵二叉树的后序遍历序列是{ 1, 3, 2, 6, 5, 7, 4 }， 中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？(A) A.这是一棵完全二叉树 B.2是1和3的父结点 C.这是一棵二叉搜索树 D.7是5的父结点

2-9 若一棵二叉树的前序遍历序列是{ 4, 2, 1, 3, 6, 5, 7 }， 中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？(D) A.这是一棵完全二叉树 B.所有的奇数都在叶子结点上 C.这是一棵二叉搜索树 D.2是5的父结点

2-11 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序(A) A.发生改变 B.不发生改变 C.不能确定 D.上都不对 [解析]左子树和右子树的相对位置 无论什么遍历方式 都不发生改变 左叶子部分始终在右叶子部分的前面

2-13 先序遍历图示二叉树的结果为(B) A.A，B，C，D，H，E，I，F，G B.A，B，D，H，I，E，C，F，G C.H，D，I，B，E，A，F，C，G D.H，I，D，B，E，F，G，A，C [解析]先序:root, L, R 2-15 某二叉树的中序序列和后序序列正好相反，则该二叉树一定是© A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 [解析]中序:L, root, R 后序:L, R, root 因为顺序相反,所有任意节点无左孩子

2-16 某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是(B) A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 [解析]前序:root, L, R 后序:L, R, root, 有要求两序列相反 A, 若是空树或者只有一个结点,那么先序和后序序列相同 C, 任意节点无左孩子, 确实构造出的二叉树满足条件 D 和C一样, 也满足条件 所以 C和D 都不是充要条件 对B若高度等于其节点数, 也就是一个高度,一个节点 此时,每层只有一个节点 这种二叉树的前序,根节点在前, 子树在后 后序子树在前,根在后 满足定义, 这才是充要条件, 我不知道为什么,也不能举反例, 排除法把

2-17 设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是() A.n在m左方 B.n在m右方 C.n是m祖先 D.n是m子孙 2-18 给定二叉树如下图所示。设N代表二叉树的根， L代表根结点的左子树，R代表根结点的右子树。 若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是：(B) A.NRL B.RNL C.LRN D.RLN [解析]这种遍历方式也可以实现,就是代码的顺序调换一下而已

2-21 如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG， 那么该二叉树的前序遍历结果是什么？(B) A.ABCDEFG B.ABDFEGC C.ABDFECG D.ABDEFCG

2-22 已知二叉树的先序遍历序列为ABCDEFGH， 中序遍历序列为CBEDFAGH，则该二叉树形态中， 父节点的右子节点为()。© A.D B.H C.G D.F

2-14 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是： A. B. C. D. 解析先忽略虚线部分,只看实现,进行后序遍历,得dbca前驱后继关系 (2)根据后序遍历的顺序,依次考虑各个节点,当左孩子为空时,指向前驱, 右孩子为空时指向后继 其中,结点d,五左右孩子,由于是第一个结点,故指向前驱null,后继为b 比较特殊一点

2-19 二叉树若用顺序存储结构(数组)存放， 则下列四种运算中的()最容易实现。© A.先序遍历二叉树 B.判断两个结点是不是在同一层上 C.层次遍历二叉树 D.根据结点的值查找其存储位置 [解析]层次遍历二叉树,就是将数组遍历一遍

2-20 在下述结论中，正确的是：() ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①④ B.②④ C.①②③ D.②③④ [解析]C.二叉树是有序树,两子节点不能交换顺序

2-23 已知一棵完全二叉树的第6层(设根为第1层)有8个叶子结点， 则该完全二叉树的结点个数最多是()。© A.39 B.52 C.111 D.119 [解析]根据完全二叉树的结构特点,第6层存在叶子结点,那么最后一层 一定是第7层,且,第6层除了后面的八个结点没有子节点 其余的结点都有子节点, 最多最少的情况出现在第八层的倒数第9个结点有几个子节点 (这个节点必须有孩子,但是不知道是一个还是两个)最小值的情况L这个结点只有一个孩子 最大的情况:这个结点有两个孩子 所以 最大结点数为: (2^6 - 1) + 2 * (2^(6-1) - 8)