已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的的前序遍历序列是什么?
二叉树的后序遍历序列是DACBE, 中序遍历序列是DEBAC根据后序DACBE最后的字符是E, 可以确定E是根结点.那么,中序DEBAC就以E为中心, D为根结点的左子树, BAC是根结点的右子树. E / \ D BAC 后序DACBE里的B在E之前, 中序DEBAC里的B在E之后, 可以确定B是E的右孩子. E / \ D B \ AC后序DACBE里的A跟着D之后, 预计A在二叉树的最后, 那么C层次上应该在B和A之间.二叉树的示意图如下: E / \ D B \ C / A所以, 前序遍历序列是 EDBCAC语言测试程序测试结果:创建二叉树,输入前序扩展序列: ED##B#CA###前序遍历序列: E D B C A中序遍历序列: D E B A C后序遍历序列: D A C B E#include#includetypedef struct Node{ char data; struct Node *lchild; struct Node *rchild;}Bitree;//用"前序遍历"算法创建二叉树void CreateBiTree(Bitree **bt){ char s; scanf("%c",&s); //输入数据 if(s=='#') //'#'是空节点 *bt=NULL; else { *bt=(Bitree *)malloc(sizeof(Bitree)); (*bt)->data=s; CreateBiTree(&((*bt)->lchild)); CreateBiTree(&((*bt)->rchild)); }}//前序遍历void preOrder(Bitree *ptr){ if(ptr!=NULL) { printf("%c ",ptr->data); preOrder(ptr->lchild); preOrder(ptr->rchild); }}//中序遍历void inOrder(Bitree *ptr){ if(ptr!=NULL) { inOrder(ptr->lchild); printf("%c ",ptr->data); inOrder(ptr->rchild); }}//后序遍历void postOrder(Bitree *ptr){ if(ptr!=NULL) { postOrder(ptr->lchild); postOrder(ptr->rchild); printf("%c ",ptr->data); }}int main(){ Bitree *root; printf("创建二叉树,输入前序扩展序列: "); CreateBiTree(&root); printf("前序遍历序列: "); preOrder(root); printf("
中序遍历序列: "); inOrder(root); printf("
后序遍历序列: "); postOrder(root); printf("
"); return 0;}
选D
首先看后续遍历,最后的c是二叉树的根节点,然后看中序遍历,最后一个又是c,所以这个二叉树根节点没有右子树。
c的位置得到后,再看后续遍历,e在c前面,所以e是c的左孩子节点,e的位置得到。
然后再看中序遍历,e前面只有一个d,所以d是e的左孩子节点,d的位置得到;剩下的b和a就在e的右子树。
然后再看后序遍历,dabec,d是一个叶子节点,那么就还有一个叶子节点,那么这个节点就一定是a,那么b就是e的右孩子节点,最后再结合中序遍历就可得出所表示得二叉树。(如果这步没看懂,可以在前面得基础上一个一个的试,也不麻烦,就四种可能,最后只有一个是符合的)
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的的前序遍历序列是edbac。
后序遍历顺序是“左子树―右子树―树根节点”:中序遍历是“左子树-树根节点-右子树”,前序遍历是“树根节点―左子树―右子树”。
二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。四种遍历方式分别为:先序遍历、中序遍历、后序遍历、层序遍历。
扩展资料
二叉树具有以下几个性质:
1、二叉树中,第 i 层最多有 2i-1 个结点。
2、如果二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点。
3、二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1。
满二叉树除了满足普通二叉树的性质,还具有以下性质:
1、满二叉树中第 i 层的节点数为 2n-1 个。
2、深度为 k 的满二叉树必有 2k-1 个节点 ,叶子数为 2k-1。
3、满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。
4、具有 n 个节点的满二叉树的深度为 log2(n+1)。
由于后序遍历序列中排在最后的是E,说明E是根结点,又由于中序遍历序列中D排在E之前,说明D为根结点E的左子树,其余的结点B、A、C在根结点E的右子树上,结构如下图所示:
后序遍历序列中B排在E之前,说明B就是根结点E的右子树的根,即B是E的右孩子,再结合中序遍历序列,可以发现B没有左孩子,那么结点A、C均在结点B的右子树上,结构如下图所示:
后序遍历序列中A排在C之前,说明A是C的孩子,而中序遍历序列中A也排在C之前,可以进一步确定A是C的左孩子,这样的话,该二叉树完整的结构图应为:
所以,该二叉树的正确前序遍历序列应为 EDBCA.
后序遍历说明E是根节点,可见在中序中E的左边是左子树,右边是右子树,可知左子树只有一个D
节点, 再看后序遍历中ACB序列说明B是右子树的根节点, 在中序中找到B,发现B没有左子树,
就是说AC都在B的右子树上, 又知道后序遍历中顺序是AC 说明 A是C的子节点, 而中序顺序是AC说明A在C的左子树上,
前序:EDBCA
已知某二叉树的后序遍历序列为fcbeda,中序遍历序列为cfbead 画出这颗...
. a e d b c f 因为后序为左,右,根 中序为左,根,右 可以看出a为根,d为a的右孩子,其余为a的左孩子 在fcbe中,根据后序为fcbeda可以确定e为根,再根据中序为cfbead可以确定fcb都为e的左孩子,而e没有右孩子 在cfb中,根据后序fcbeda可以确定,b为根,再根据中序为cfbe...
某二叉树的后序遍历的结果是abcd-*+ef\/-,令a=2,b=3,c=4,d=5,e=6.f...
二叉树的后续遍历计算时,符号在后,每次遇到一个运算符就将前两个数字进行运算 (1)先算-前面的c与d,有c-d=-1,此时整个表达式子为ab-1*+ef\/-(这里是-1,负一)(2)先算*前面的b与-1,有b*(-1)=-3,此时整个表达式子为a-3+ef\/-(这里是-3,负三)(3)先算+前面的a与-5,有a+...
已知某二叉树的后序遍历序列为CEDBHJIGFA,中序遍历序列为CBEDAHGIJF...
画筐法 解决这个问题!下图的画法完全正确!先通过后序遍历的最后一个确定根节点是A。根据A把中序遍历的序列分成两部分即:CBED(左)和HGIJF(右)。此时,后序遍历的序列也分成了两部分即:CEDB和BHJIGFA。同理即可推出一楼的答案图!希望能帮到你哦 ...
已知二叉树后序遍历序列是CDABE,中序遍历序列是CADEB,它的前序遍历序列...
所以中序中E左边是E的左子树上的结点,右边是右子树上的结点。依照上述规则找左子树的根节点,在后序中查看,B是E的右子树根节点,A是左子树的根节点.依次类推,最终二叉树得到如下:E \/ \\ A B \/ \\ C D 这样前序也很容易得到了,EACDB ...
已知一颗二叉树的后序遍历结果是EDCBIHJGFA,中序遍历的结果是EBCDAFHIG...
后序遍历结果是EDCBIHJGFA 中序遍历的结果是EBCDAFHIGJ 二叉树还原如下:A B F E C G D H J I 所以,前序遍历结果为:ABECDFGHIJ
某二叉树的先序和后序遍历序列正好相反,则该二叉树一定是什么二叉树
分析如下:先序遍历顺序是:M-L-R,后序遍历顺序是:L-R-M,可以看到,只有中间的结点(M)顺序变化了,左右结点相对位置是不变的;那可以推断出,要满足题意的话“二叉树的先序序列与后序序列正好相反”,说明整个二叉树左子树或者右子树有一个没有(遍历就成了,先:M-L ;后:L-M 或者 ...
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍因序 ...
前序遍因序列是cedba。二又树的遍历有3种:前序、中序和后序。①前序首先遍历访问根结点,然后按左右顺序遍历子结点。②中序遍历首先访问左子树,然后访问根结点,最后遍历右子树。③后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点。本题根据后序和中序遍历的结果可以得出二叉树的结构,然后...
某二叉树的中序遍历为CBADE,后序遍历序列为CBEDA,则前序遍历序列为?
后序遍历中最后一个就是树根结点,即A结点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为CB。去掉根节点和左子树节点,右子数节点为DE。在二叉树中,求前序遍历,先根后左再右,即首先访问根结点,然后遍历左子树,最后访问遍历右子树。则该二叉树的前序遍历是ABCDE。
某二叉树的后序遍历序列与中序遍历序列相同,均为ABCDEF,则前序遍历序 ...
根据后序和中序,该二叉树如下:F \/ E \/ D \/ C \/ B \/ A 所以前序遍历是:FEDCBA
已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序...
后续遍历的顺序是左右根,中序遍历的顺序是左根右 这点应该懂吧 由后续访问序列可以看出最后一个被访问的必定是这个树的根 而中序遍历的序列可以看出,一棵树当根确定后,在根前面被访问的是他的左子树,后边的是他的右子树元素 弄懂了上边两点就开始做题吧 由后序遍历序列是DBCEFGHA 为了方便,我...
永爬辰立: 由于后序遍历序列中排在最后的是E,说明E是根结点;又由于中序遍历序列中仅D排在E之前,其余的结点B、A、C相继排在E之后,说明D为根结点E的左子树,其余的结点B、A、C在根结点E的右子树上,结构如下图所示: 后序遍历序列中B排在E的前一位,说明B就是根结点E的右子树的根,即B是E的右孩子,再结合中序遍历序列,可以发现B没有左孩子,那么结点A、C均在结点B的右子树上,结构如下图所示: 后序遍历序列中A排在C的前一位,说明A是C的孩子,而中序遍历序列中A也排在C的前一位,可以进一步确定A是C的左孩子,这样的话,该二叉树完整的结构图应为:那么,该二叉树的正确前序遍历序列应该为 EDBCA.
舒城县18229739811: 已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的的前序遍历序列是什么? - ?
永爬辰立: 前序遍历,也叫先根遍历,遍历的顺序是,根,左子树,右子树中序遍历,也叫中根遍历,顺序是 左子树,根,右子树后序遍历,也叫后根遍历,遍历顺序,左子树,右子树,根所以前序为EDBCA
舒城县18229739811: 已知二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的前序遍历序列是? - ?
永爬辰立: 二叉树的后序遍历序列是DACBE, 中序遍历序列是DEBAC 根据后序DACBE最后的字符是E, 可以确定E是根结点.那么,中序DEBAC就以E为中心, D为根结点的左子树, BAC是根结点的右子树. E / \ D BAC 后序DACBE里的B在E之前, 中...
舒城县18229739811: 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 A) acbed B) decab C) deabc D - ?
永爬辰立: 前序遍历是cedba.从后序遍历可知,根节点为c,从中序遍历可知,这个树没有右子树.然后从后序遍历可知,e是左子树的根节点.从中序遍历可知,d是左子树的左子树,因为只有一个节点,因此也是叶子节点.e的右子树包含ba两个节点.从后序遍历可知,b是e的右子树的根节点,由中序可知,a是b的右叶子节点.这棵二叉树也就出来了.因此,前序遍历为cedba
舒城县18229739811: 已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是 - ?
永爬辰立: 后序:左 右 根 中序:左 根 右由定义可以知道: 1、后序遍历中最后一个就是树根节点,即C节点 2、在中序遍历中,根结点左边的是左儿子集,右边的是右儿子集,即deab是根节点C的左儿子集合问题就会转化为: 求后序遍历是dabe,中序...
舒城县18229739811: 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 - ?
永爬辰立: 选D 首先看后续遍历,最后的c是二叉树的根节点,然后看中序遍历,最后一个又是c,所以这个二叉树根节点没有右子树. c的位置得到后,再看后续遍历,e在c前面,所以e是c的左孩子节点,e的位置得到. 然后再看中序遍历,e前面只有一个d,所以d是e的左孩子节点,d的位置得到;剩下的b和a就在e的右子树. 然后再看后序遍历,dabec,d是一个叶子节点,那么就还有一个叶子节点,那么这个节点就一定是a,那么b就是e的右孩子节点,最后再结合中序遍历就可得出所表示得二叉树.(如果这步没看懂,可以在前面得基础上一个一个的试,也不麻烦,就四种可能,最后只有一个是符合的)
舒城县18229739811: 已知某二叉树的后序遍历和中序遍历的序列分别为? - ?
永爬辰立: 您好,你的问题,我之前好像也遇到过,以下是我原来的解决思路和方法,希望能帮助到你,若有错误,还望见谅!展开全部 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前...
舒城县18229739811: 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是什么? - ?
永爬辰立: 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点.中序遍历的根节点前面的节点均为左子树的节点,所以左子树上...
舒城县18229739811: 已知某二叉树的后序遍历序列是dabec,中序遍历是debac.则它的前序遍历是?为什么??
永爬辰立: 后序遍历时,根节点是在最后一个的,所以c就是根节点,而中序遍历里,c也在最后一个,说明该树只有左子树,左子树的后序遍历是dabe,所以e是c的左儿子,又根据中序遍历deba可以知道,e的左儿子是d,ba是e的右子树,又由后序遍历dab知,该右子树ba中b是a的父节点,a是b的右儿子.该树的图如下:c/ e/ \ d b\a 因此,其前序遍历是:cedba
舒城县18229739811: (53) 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 - -----. A. cedba B. acb - ?
永爬辰立: (53)[答案]A [考点]数据结构与算法 [评析] 后序又叫后根,一次递归过程是先左再右最后根;中序是先左再根最后右.比如下图:前序是:abc 中序是:bac 后序是:bca 题中据后序遍历序列,一眼得知c结点是根,那么据中序deba结点都在一边,...