PTA-10/7 二叉树

偏执的太偏执、 2022-12-12 15:07 145阅读 0赞

1-4 若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。

前序和中序指的是根的访问次序，因为a和b都是叶子节点，所以并不影响他们访问的先后次序。

1-5 若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。 (2分)

中序：根左右  
前序：左根右

这么看确实正确，但正确的前提是都有右子树，对于只有根和左子树的图是不成立的。

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

前：根左右  
中: 左根右

要想一样，必须无左子树

2-11 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 (2分) B

发生改变
    不发生改变
    不能确定
    以上都不对

因为先左子树后右子树的整体顺序并不变

2-15

某二叉树的中序序列和后序序列正好相反，则该二叉树一定是  
(2分) C

A.空或只有一个结点  
B.高度等于其结点数  
C.任一结点无左孩子  
D.任一结点无右孩子

2-16

某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是  
(2分) B  
A.空或只有一个结点  
B.高度等于其结点数  
C.任一结点无左孩子  
D.任一结点无右孩子

要么只有 左子树，要么只有右子树，要么空或者只有一个节点

2-18 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是： B  
![在这里插入图片描述][20201007225750763.jpg_pic_center]

(2分)  
A.NRL  
B.RNL  
C.LRN  
D.RLN

2-14下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是：(2分)  
A.  
![在这里插入图片描述][20201007230303833.jpg_pic_center]B.  
![在这里插入图片描述][20201007230333314.jpg_pic_center]  
C.![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTkxODEz_size_16_color_FFFFFF_t_70_pic_center]  
D.  
![在这里插入图片描述][20201007230428961.jpg_pic_center]不会

[20201007225750763.jpg_pic_center]: /images/20221123/b04d2ee4f4464762bce1e592e7535434.png
[20201007230303833.jpg_pic_center]: /images/20221123/7f2f9affa2b948568698d7e07ff5d16a.png
[20201007230333314.jpg_pic_center]: /images/20221123/1b3ee33b24d34e28af2916bdc533e204.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTkxODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/dd8990f0bf064cc483ad24fce920ad20.png
[20201007230428961.jpg_pic_center]: /images/20221123/7bdf3b4654f5416ebe4cf488f8fe88be.png