数据结构考研分类复习真题 第六章 答案 (四)[12]

．证明请参见第题和第题

由前序序列ABDGECFH和中序序列DGBEAFHC构造的二叉树如图

．参见第题

．先序遍历二叉树的顺序是根左子树右子树中序遍历左子树根右子树后序遍历顺序是左子树右子树―根＂根据以上原则本题解答如下

若先序序列与后序序列相同则或为空树或为只有根结点的二叉树

若中序序列与后序序列相同则或为空树或为任一结点至多只有左子树的二叉树

若先序序列与中序序列相同则或为空树或为任一结点至多只有右子树的二叉树

若中序序列与层次遍历序列相同则或为空树或为任一结点至多只有右子树的二叉树

由中序序列DBEAFIHCG和后序序列DEBHIFGCA确定的二叉树略

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []