已知一棵二叉树的前序序列为A B D G C E H I F;中序序列为:D G B A E I H C F,画出二叉树并写出它的后序?
1、由先序遍历特征,根节点必在先序序列首部,可知根节点是A;由中序遍历特征,根节点必在中间,可以得到左子树子孙(BFD),右子树子孙(GEHC);
2、继续可得子树B(先序BDF中序BFD)
3、C(先序CEGH中序GEHC);
4、重复上述步骤,即可唯一地确定一棵二叉树
先序序列是A,B,D,E,G,C,F,H,I,J
后序序列是D,G,E,B,H,J,I,F,C,A
二叉树的后序为G、D、B、I、H、E、F、C、A。
由前前序第一个为A,所以根节点,所以A的左子树为D、G、B,右子树为E、I、H、C、F。第二个根节点为B,又由中序的出B的左子树为D、G,然后得出D的右子树为G,C为A的右子树,依次进行判断,最后的出二叉树的序列。
二叉树图,如下图:
扩展资料:
二叉树性质:
1、二叉树的第i层上至多有2i-1(i≥1)个节点。
2、深度为h的二叉树中至多含有2h-1个节点。
3、若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1。
4、具有n个节点的完全二叉树深为log2x+1(其中x表示不大于n的最大整数)。
5、若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的节点:
当i=1时,该节点为根,它无双亲节点。
当i>1时,该节点的双亲节点的编号为i/2。
若2i≤n,则有编号为2i的左节点,否则没有左节点。
若2i+1≤n,则有编号为2i+1的右节点,否则没有右节点。
参考资料来源:百度百科-二叉树
后序:
GDBIHEFCA
已知一棵二叉树,前序ABECDFGHIJ,中序EBCDAFHIGJ,编程输出该树的后序遍 ...
找规律:前序:ABECDFGHIJ的第1个字符为A,说明它是树的根。然后定位A在中序:EBCDAFHIGJ中的位置,A把中序分成两个子串:EBCD和FHIGJ,它们分别是A的左子树和右子树的所有结点。前序:ABECDFGHIJ的第2个字符为B,同理它把子串EBCD分成两个子串E和CD,它们分别是以B为根的两个左、右子数。前...
有一棵二叉树的先序和中序遍历分别如下,画出该二叉树(...
有一棵二叉树的先序和中序遍历分别如下,画出该二叉树(...序:A B C D E F G H I J 中序:C B E D A G H F J I 确定根是A,C B E D在A的左子树上,G H F J I在A的右子树上。先序:B C D E 中序:C B E D 确...
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中,所有叶子结 ...
(1)先序遍历(D L R):访问根结点;先序遍历左子树;先序遍历右子树。(2)中序遍历(L D R):中序遍历左子树;访问根结点;中序遍历右子树。(3)后序遍历(L R D):后序遍历左子树;后序遍历右子树;访问根结点。一棵二叉树不论哪种遍历算法,有以下要点:①所有叶子节点先后顺序不...
已知一颗二叉树先序、中序、后序,画出该二叉树,在线等!
已知一棵二叉树的先序、中序和后序序列如下,其中空缺了部分,请画出该二叉树。先序:_BC_EFG_IJK_中序:CBED_GAJ_H_L后序:_E_FD_J_L_HA... 已知一棵二叉树的先序、中序和后序序列如下,其中空缺了部分,请画出该二叉树。先序: _BC_EFG_IJK_中序:CBED_GAJ_H_L后序:_E_FD_J_L_HA 展开 ...
一棵二叉树的先序、中序、后序序列如下,其中一部 分未标出,请构造出...
你的先序序列不少元素干嘛打那么多空格,结果是,先序 遍历为:ABCDEFGHIJK 中序遍历为:CBEDFAHJKIG 后续遍历 为:CEFDBKJIHGA.树状结构为:A \/ \\ B G \/ \\ \/ C D H \/ \\ \\ E F I \/ J \\ K
一棵二叉树的前序ABCD 中序BADC后序
后序为BDCA 树形图 A B C D 解释:BC分别为A的左孩子和右孩子,D为C的左孩子 按照后序遍历顺序:后序左—右—根 后序:BDCA
一棵二叉树的前序遍历结果是ABCEDF,中序遍历结果是CBAEDF,则其后序遍...
\/\/ 二叉树的"前序遍历"结果: A B C E D F\/\/ 二叉树的"中序遍历"结果: C B A E D F\/\/ 二叉树的"后序遍历"结果: C B F D E A\/\/ 2017-04-30#include "stdio.h"#include "stdlib.h"struct tree{ char data; struct tree *left; struct tree *right;};typedef stru...
设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5...
前序:abdgcefh 中序:dgbaecfh 本题问题在于如何根据给定的前序中序结果画出二叉树,从而来确定后序的问题。分析过程如下:(1)前序顺序为根左右,根据前序知道:a为根节点,然后观察a在中序遍历中的结果得到:dgb为a的左子树的中序遍历结果,echf为a的右子数的中序遍历结果。(2)紧接着上面...
已知一棵二叉树的前序序列abhfdeckg和中序序列hbdfaekcg画出二叉树...
二叉树是 a \/ \\ b e \/ \\ \\ h f c \/ \/ \\ d k g 后序是 hdfbkgcea
一棵二叉树的先序遍历次序为ABDGECFH,中序遍历次序为DGBEAFHC,则其后...
先序遍历次序由:根+根的左子树先序遍历次序+根的右子树先序遍历次序构成;中序遍历次序由:根的左子树中序遍历次序+根+根的右子树中序遍历次序构成;由先序遍历次序为ABDGECFH可知,二叉树的根为A;再由中序遍历次序为DGBEAFHC,可知根A的左子树中序遍历次序为DGBE,根A的右子树中序遍历次序为...
温芸尼必: 必为A、B、C
河北区19720891008: 数据结构 已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ,中序遍历的结果是 - ?
温芸尼必: 如果仅有“已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ”,则中序遍历的结果是不能确定的.
河北区19720891008: 已知一棵二叉树的先序遍历序列为: A B C D E F G H I,中序遍历序列为:B C A E D G H F I,画出这棵二叉树. - ?
温芸尼必: A/ \B D\ / \C E F/ \G I \H
河北区19720891008: 一棵二叉树的前序遍历序列为abdec,二叉树的根为什么? 答案和原因,谢谢 - ?
温芸尼必: 根是a.因为二叉树前序遍历按 根左右的顺序,所以a就是二叉树的根节点.
河北区19720891008: 知一棵二叉树的前序序列:ABDECFGH,中序序列:DEBACGFH.请画出此二叉树;写出该二叉树的后序遍历序列. - ?
温芸尼必: 这是递归算法. 前序第一个必定是根,根2113就是A, 从中5261序中就能分出左、右子树了:B和EDCHGIFJ,这是中序 就可据此从前4102序中分出左、右子树了:B和CDEFGHIJ,这是前序了. 这样一个1653问题专变成了两个同样的小问题了,递归下去不就属解决了. 多动动脑筋就出来了
河北区19720891008: 已知一颗二叉树的先序遍历序列为:ABDCEF,中遍历为:BDAECF,请画出这颗二叉树,并给出其后序遍历序列 - ?
温芸尼必: A->Lchild=D,A->Rchild=C,D->lchild=B,C->lchild=E,C->rchild=F 后序遍历:BDEFCA
河北区19720891008: 一棵二叉树前序序列为A B D E G C F H I 对称序列为DBGEACHFI则其后序列为??
温芸尼必: 应该是DGEBHFICA
河北区19720891008: 如果一棵二叉树结点的前序序列是A、B、C,后序序列是C、B、A,则该二叉树结点的对称序 序列?1.必为A、B、C2.必为A、C、B3.必为B、C、A4.不能确... - ?
温芸尼必:[答案] 选择4不能确定.因为至少有如下两种情况符合条件: 1.A(根)、B(左,第二层)、C(左,第三层) 2.A(根)、B(左,第二层)、C(右,第三层) 此时1的对称序为CBA,而2的对称序为BCA
河北区19720891008: 已知一棵二叉树的先序序列为ABCDEFGHIJ,中序序列为BCDAFEHJIG - ?
温芸尼必: AB EC F GD HJI =================== CDBFJIHGEA
河北区19720891008: 已知某二叉树的先序遍历序列为:A,B,D,E,G,C,F,H,I,J,中序序列为:D,B,G,E,A,H,F,I,J,C试给出该二叉树的先序序列和后序序列 - ?
温芸尼必:[答案] 先序序列是A,B,D,E,G,C,F,H,I,J 后序序列是D,G,E,B,H,J,I,F,C,A