如何根据前序遍历序列和中序遍历序列确定二叉树
来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/05/01 17:29:33
如何根据前序遍历序列和中序遍历序列确定二叉树
假设某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,画出二叉树,并给出其后序遍历序列.
以下面的例题为例进行讲
已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列.
分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列.
先序:abdgcefh --> a bdg cefh
中序:dgbaechf --> dgb a echf
得出结论:a是树根,a有左子树和右子树,左子树有bdg结点,右子树有cefh结点.
先序:bdg --> b dg
中序:dgb --> dg b
得出结论:b是左子树的根结点,b无右子树,有左子树.
先序:dg --> d g
中序:dg --> d g
得出结论:d是b的左子树的根结点,d无左子树,有右子树.
先序:cefh --> c e fh
中序:echf --> e c hf
得出结论:c是右子树的根结点,c有左子树(只有e结点),有右子树(有fh结点).
先序:fh --> f h
中序:hf --> h f
得出结论:f是c的左子树的根结点,f有左子树(只有h结点),无右子树.
还原二叉树为:
a
b c
d e f
g h
后序遍历序列:gdbehfca
以下面的例题为例进行讲
已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列.
分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列.
先序:abdgcefh --> a bdg cefh
中序:dgbaechf --> dgb a echf
得出结论:a是树根,a有左子树和右子树,左子树有bdg结点,右子树有cefh结点.
先序:bdg --> b dg
中序:dgb --> dg b
得出结论:b是左子树的根结点,b无右子树,有左子树.
先序:dg --> d g
中序:dg --> d g
得出结论:d是b的左子树的根结点,d无左子树,有右子树.
先序:cefh --> c e fh
中序:echf --> e c hf
得出结论:c是右子树的根结点,c有左子树(只有e结点),有右子树(有fh结点).
先序:fh --> f h
中序:hf --> h f
得出结论:f是c的左子树的根结点,f有左子树(只有h结点),无右子树.
还原二叉树为:
a
b c
d e f
g h
后序遍历序列:gdbehfca
如何根据前序遍历序列和中序遍历序列确定二叉树
已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列!
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是什么?
二叉树的问题(2) 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是A) acbed B
已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?麻烦再画下这二叉树.
已知二叉树后序遍历序列是DABEC 中序遍历列是 DEBAC ,它的前序遍历序列是:
写出下列二叉树的中序遍历序列
(53) 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是______.A.cedba
VB已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是?
二叉树T,已知其前序遍历序列为1 2 4 3 5 7 6,中序遍历序列为4 2 1 5 7 3 6,其后序遍历序列为
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍因序列是多少
有一棵二叉树的先序和中序遍历分别如下,画出该二叉树(描述生成过程),并写出其后序遍历序列.