Question

某二叉树的前序序列与中序序列正好相反,则该二叉树具有_____ a)二叉树为

某二叉树的前序序列与中序序列正好相反,则该二叉树具有_____
a)二叉树为空或只有一个结点
b)若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子
c)若二叉树不为空，则任一结点没有左孩子
d)若二叉树不为空，则任一结点没有右孩子

Answer 1

前序遍历过程是根左右
中序遍历过程是左根右


所以根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树
如本题
根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。
确定A之后，再看中序第二值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。所以本题的具体二叉树如下：

1.          A


2.        /


3.     B


4.   /


5. C

所以后序是CBA

Answer 2

如果是多选的话B应该也可以选，但如果单选则不能选B。B中描述的二叉树包括C和D，更准确的说应该是每个节点都只有一个孩子的二叉树，其中只有C中描述的二叉树才满足题目要求的中序和后续相反。简单分析如下：对任意一个节点A，其左右孩子分别为BC（可能为空），则其中续为BAC，后续为BCA，要BCA与BAC相反，即ACB与BAC相同只能是B为空，即左孩子为空，推广到整个二叉树即任意节点无左孩子。