首页 > 试题广场 >

已知一个二叉树的前序遍历结果是(ACDEFHGB) ,中序遍

[单选题]
已知一个二叉树的前序遍历结果是(ACDEFHGB) ,中序遍历结果是(DECAHFBG),请问后续遍历结果是()。
  • HGFEDCBA
  • EDCHBGFA
  • BGFHEDCA
  • EDCBGHFA
  • BEGHDFCA
  • BGHFEDCA
推荐
答案:B
根据前序遍历可以确定根节点为A,
再根据中序遍历可以确定A的左侧为左子树DEC,A的右侧为右子树HFBG
再根据前序遍历得到左子树的根节点为C,右子树的根节点为F,然后递归下去就能恢复二叉树
然后后续遍历得到结果
C代码如下:
typedef struct Tnode
{
    struct Tnode * left;
    struct Tnode * right;
    char elem;
} TreeNode;
//根据先序,中序遍历,返回二叉树
void * getByPreInOrder(char * preorder, char * inorder, int length)
{
    if(length<1)
        return NULL;
    TreeNode * node=malloc(sizeof(TreeNode));
    node->elem=*preorder;//根节点
    int rootIndex=0;
    while(rootIndex<length && inorder[rootIndex]!=node->elem)
        rootIndex++;//查找中序遍历根节点索引
    //递归恢复左右子树
    node->left=getByPreInOrder(preorder+1, inorder, rootIndex);
    node->right=getByPreInOrder(preorder+rootIndex+1,inorder+rootIndex+1, length-rootIndex-1);
    return node;
}
//后序遍历
void postOrder(void * root)
{
    if(root==NULL)
        return;
    TreeNode* node=(TreeNode*)root;
    postOrder(node->left);
    postOrder(node->right);
    printf("%c",node->elem);
}
void main()
{
    char * pre="ACDEFHGB";
    char * in="DECAHFBG";   
    void * tree=getByPreInOrder(pre,in,strlen(in));    
    postOrder(tree);
}

编辑于 2015-01-30 15:52:40 回复(0)
选B
根据已知条件得到树结构如下:

发表于 2015-03-11 16:50:59 回复(1)
前序为根左右,中序为左根右,后序为左右根(可以根据根的位置进行记忆)
在前序中可得根,将中序分为左子树(DEC)根(A)右子树(HFBG)
左子树(DEC)中由前序可得C为根,DE是左子树;同理可得其它
结果为B
编辑于 2015-07-04 00:05:36 回复(2)
前序:A CDEFHGB
中序:DEC A HFBG
首先A肯定是根节点,所以DEC是左边的,HFGB是右边的
然后
左:前:CDE,中:DEC,在左子树中,C是根,然后就剩下E和C很好推。
右边也是一样的办法可以推出
发表于 2017-09-14 17:09:46 回复(0)
HaQ头像 HaQ
根据前序遍历ACDEFHGB确定A为根节点,中序遍历DECAHFBG确定(DEC)为左子树,(HFBG)为右子树;则由前序遍历ACDEFHGB根左右规则得左子树(CDE)中C为根节点,(FHGB)中F为根节点;又有中序遍历DECAHFBG规则左根右,左子树 (DEC)C为根得DE为C左子树且E不可能为D的左子树; (HFBG)F为根得H为F左子树则BG为其右子树;此时继续看下前序遍历 ACDEFHGB根左右注意 (CDE) DE为C左子树, D在E前又为前序则D为E的根节点,又由中序遍历( DEC)左右根得D左为空 E为D的右子树;再看前序遍历 (FHGB) G B 为F右子树,前序遍历G在B前则由根左右得G为B根节点,又由中序遍历 HFBG )左根右得G右为空B为G左子树;得图 (LZ懒--摘自:大明白)可得后序遍历左右根为EDCHBGFA选B
发表于 2015-11-02 23:38:08 回复(0)
B
先序用于判断每棵树的根节点,中序用于判断左右子树
发表于 2017-03-02 15:51:37 回复(0)
前序为根左右,中序为左根右,后序为左右根
发表于 2016-03-21 11:40:41 回复(0)
B 先根据先序遍历确定根节点,然后在中序遍历中根据根节点将树分成左右子树,然后依次递归左右子树。
发表于 2015-04-09 16:33:37 回复(1)
B 递归方法。前序的第一个结点是根节点,在中序中以根节点为轴,左边是左子树,右边是右子树。每一个子树再以同样的方法判断
发表于 2015-03-25 22:01:57 回复(0)
复制下别人的评论,做个笔记 根据前序遍历ACDEFHGB确定A为根节点,中序遍历DECAHFBG确定(DEC)为左子树,(HFBG)为右子树;则由前序遍历ACDEFHGB根左右规则得左子树(CDE)中C为根节点,(FHGB)中F为根节点;又有中序遍历DECAHFBG规则左根右,左子树 (DEC)C为根得DE为C左子树且E不可能为D的左子树; (HFBG)F为根得H为F左子树则BG为其右子树;此时继续看下前序遍历 ACDEFHGB根左右注意(CDE) DE为C左子树, D在E前又为前序则D为E的根节点,又由中序遍历( DEC)左右根得D左为空 E为D的右子树;再看前序遍历 (FHGB) G B 为F右子树,前序遍历G在B前则由根左右得G为B根节点,又由中序遍历 ( HFBG )左根右得G右为空B为G左子树;得图
编辑于 2019-04-04 19:22:32 回复(0)
b
发表于 2018-03-14 21:20:56 回复(0)
B,很显然
发表于 2016-07-18 14:06:09 回复(0)
B,前序遍历找根节点,终须遍历通过根节点将左右子树分开
发表于 2015-08-19 22:15:33 回复(0)
先序,按根左右的顺序排列,可以想象成,先序的节点都是根, 中序判断根的左子树和右子树,在中序遍历中,根左就为左子树,右边就为右子树
发表于 2015-08-13 23:08:38 回复(0)
前序遍历结果是(ACDEFHGB) ,中序遍历结果是(DECAHFBG)
前序遍历第一个是根节点,中序遍历,根节点的左子叶在左边,右子叶在右边
所以A是根节点,DEC是左子叶,HFBG是右子叶
CDE的前序遍历是CDE中序遍历是DEC,所以DE是C的左子叶,D是E父节点
        A
       C
      D
       E
FHGB前序遍历,HFBG中序遍历,F是右子叶的根节点
        F
       H B
          G
或者
        F
       H G
        B
两种情况都符合中序遍历,第一种不符合前序遍历,所以右子节点为第二种情况,所以整个二叉树为
            A
        C       F
    D       H      G
        E       B
所以整个的后序遍历为
EDCHBGFA,选B
发表于 2015-06-07 13:52:47 回复(0)
选B:
根据前序遍历和中序遍历得到树的结果是:
                A
              /   \ 
            C       F
          /       /   \
        D       H       G
         \             /
          E           B    

因此后序遍历的结果是EDCHBGFA     
发表于 2015-05-01 22:50:51 回复(0)
前序遍历 第一个节点为根节点, 以这个节点在中序遍历的结果中作为划分,这个节点左侧的是左子树的节点,右侧是右子树节点。依次递归下去就可构造二叉树,就可知道后续遍历。
发表于 2015-04-08 11:26:32 回复(0)
B 按前序和中序、后序的规则
发表于 2015-04-07 10:18:33 回复(0)
B
发表于 2015-04-02 18:26:15 回复(0)
B
前序遍历找到根节点,中序遍历找到左右子树,依次循环。
发表于 2015-04-02 08:10:25 回复(0)
B
发表于 2015-04-01 21:49:00 回复(0)