问答题 (1)试找出满足下列条件的二叉树:1)先序序列与后序序列相同2)中序序列与后序序列相同3)先序序列与中序序列相同4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA,画出这棵二叉树。【东北大学1999六(4分)】【东南大学2000一、4(6分)】
【正确答案】正确答案:(1)先序遍历二叉树的顺序是“根一左子树一右子树”,中序遍历“左子树一根一右子树”,后序遍历顺序是“左子树一右子树一根”,根据以上原则,本题解答如下: 1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。 2)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树。 3)若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。 4)若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。 (2)由中序序列DBEAFIHCG和后序序列DEBHIFGCA。
【答案解析】