数据结构中已知前序序列和中序序列,怎么得出后序序列,谢谢回答!
发布网友
发布时间:2022-04-30 14:48
我来回答
共2个回答
热心网友
时间:2023-10-06 20:39
标准的答案!首先要明确前序,中序和后序的遍历顺序:
前序:父节点,左子节点,右子节点;
中序:左子节点,父节点,右子节点;
后序:左子节点,右子结点,父节点;
明确之后,首先根据前序遍历,确定整个二叉树的根节点(前序的第一个节点);再通过中序遍历,可以直接根据根节点将整个二叉树分为左右两颗子树。这时再逐步根据前序和中序顺序,不难画出整个二叉树。进而可以写出后序遍历序列了。
例:已知某二叉树先序遍历序列是:ABCDEFH,中序遍历序列是:BDCEAHF,写出后序遍历序列。
由前序可知,该树根节点为A;
由中序及根节点可知,B,D,C,E在根节点的左子树上H,F在根节点的右子树上;
再逐步分析各子树,可得该树为:
A
╱╲
BF
╲╱
CH
╱╲
DE
后序为:DECBHFA
热心网友
时间:2023-10-06 20:40
记住各个序列的原理,前序是根左右,中序是左根右,后序是左右根,具体的你找一个树,然后写出它的各个序列,然后知其二,反推画出树,然后写出另一
数据结构中已知前序序列和中序序列,怎么得出后序序列,谢谢回答!
前序:父节点,左子节点,右子节点;中序:左子节点,父节点,右子节点;后序:左子节点,右子结点,父节点;明确之后,首先根据前序遍历,确定整个二叉树的根节点(前序的第一个节点);再通过中序遍历,可以直接根据根节点将整个二叉树分为左右两颗子树。这时再逐步根据前序和中序顺序,不难画出...
数据结构中已知前序序列和中序序列,怎么得出后序序列
一般是先还原二叉树,再后序遍历就可以得到后序序列了,还原过程如下:首先在前序序列第一个就是根,拿到中序序列中,就可以将中序序列分解成3个部分:左子树的中序、根、右子树的中序 再分别将左子树的中序和右子树的中序回到前序序列,这些子树的前序序列里面,子树的根依然排在第一位,再次回...
数据结构知道先序遍历和中序遍历怎么求后续遍历?
找到根节点(通过后序),然后将中序序列分成两段,左右子树,然后递归进行,分的时候可以利用求中序的左右子树的结点个数来确定后序序列的每段节点个数.例如:中 BDACE 后 DBECA 1.由后序遍历的知道最后一个节点一定是根节点,该例中为A 2.中序中对应的根就是A,推得A为根BD为左子树CE为...
已知前序和中序求后序序列如何用c语言实现
先序的第二个元素是B,所以B是A的左子树根节点 由中序B在最前,知道其他元素都在B的右子树上 所以,后序序列为(DE_)B(G_H)A,对比已有的后序序列_DC_GH_A 得后序序列为:EDCBGHFA,中序序列为:BDECAGFH 先序序列 ABC_EF__中序序列 BDECAGFH 后序序列 EDCBGHFA 所以,二叉树为:_...
中序遍历和前序遍历,如何求后序遍历
即:前序遍历:根、左、右;中序:左、根、右;后序:左、右、根。当然了,这里面会涉及到递归的概念,需要慢慢编程消化。现在有很多 C 语言版的数据结构教材上,都有二叉树的三种遍历方法的子函数调用程序。只需要在主函数、以及相应的子函数中把教材上的数据类型修改为适合自己的数据类型即可。
已知先序中序求后序的算法:
/ 树中已知中序和后序求先序。如中序为:bdac 后序为:dbca 则程序可以求出先序为:abdc 。此种题型为数据结构常考题型。算法思想:后序遍历树的规则为左右中,则说明最后一个元素必为树的根节点,比如上例 中的a就为根节点,由于中序遍历为:左中右,再根据根节点a,我们就可以知道,左子树...
数据结构、 已知树T的先序遍历序列为ABDFGCE,中序遍历序列为BFDGAEC...
F、G、D、B、E、C、A。首先由先序遍历的结果得出根节点为A,由中序遍历找左右子树。得A的左子树为BFDG,右子树为EC,然后A的左子树B为根节点,DFG为右子树,A的右子树的根节点为C,然后用此方法递归进行处理得出数T。得出树T利用后序遍历的结果为:F、G、D、B、E、C、A。
数据结构,某二叉树前序遍历ABCDEFG,中序遍历CBDAEFG,求后序遍历及一般...
先看前序遍历的,找到根a,然后看中序遍历找到左子树(cbd),右子树(efg),之后看前序,找到根b,再看中序遍历,b为左,d为右,右子树同理,前序遍历知e为根,中序遍历知,fg为右,前序遍历知f为根,g为右。所以整棵树如下:a b e c d f g 后序遍历为cdbgfea ...
【紧急求助】某二叉树的前序序列为ABCD,中序序列为DCBA,则后序序列为...
后序序列为DCBA。详解为:前序序列的顺序是根、左、右,序列ABCD第一个一定是根结点,A是根节点。中序序列顺序是左、根、右,因为A是根节点,所以DCB位于A左侧,A右侧没有结点,B是DCB三个结点中的根。前序序列是中左右,根结点为A;中序序列是左中右,左子树BCD;遵循遍历序列的规则排列出二叉...
麻烦请大神讲解一下数据结构中根据给出的前序中序怎么画出对应的树...
前序:VLR 中序:LVR 后序:LRV 2/6 前序序列{ A B H F D E C K G} 中序序列{ H B D F A E K C G} 这样我们可以确定,我们的根节点是A,然后在中序中根据 A 的位置,可以确定 L(HBDF)和 R(EKCG)取出 A,画出二叉树 查看剩余1张图 3/6 继续根据 前序:VLR 中序...