这题有问题啊,我用正确答案对前序和中序对不上啊
回复 風靜靜吹、我痴痴醉:第一步,根据前序遍历的特点,我们知道根节点为A,中序遍历的特点,最左边节点为D,后序遍历最后一个节点是A,则后序遍历结果为D...A。
第二步,观察中序遍历DCBAEFG。其中根节点节点A左侧的ABCD必然是root的左子树,A右侧的EFG必然是根节点的右子树。
第三步,观察左子树ABCD,左子树的中的根节点必然是大树的root的左孩子。在前序遍历中,大树的根节点的左孩子位于根节点之后,所以左子树的根节点为B。
第四步,同样的道理,根节点的右子树节点EFG中的根节点也可以通过前序遍历求得。在前序遍历中,一定是先把根节点和根节点的所有左子树节点遍历完之后才会遍历右子树,并且遍历的左子树的第一个节点就是左子树的根节点。同理,遍历的右子树的第一个节点就是右子树的根节点。
前序是先中间后左边再右边
中序是先左边后中间再右边
后序是先左边后右边再中间
前序就是中间节点在前,然后是左子树,然后十右子树,每个子树都这样排
中序就是先排左子树,然后十中间节点,然后十右子树,每个子树都这样排
某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为( )
A. EFGDCBA
B. DCBEFGA
C. BCDGFEA
D. DCBGFEA
答案:D
解析:前序序列是中左右,根结点为A;中序序列是左中右,左子树BCD,右子树EFG;遵循遍历序列的规则排列出二叉树,得出后序遍历为DCBGFEA。所以选择D。