输入前序和中序输出后序

当你有二叉树的前序遍历（Preorder Traversal，即根节点 -> 左子树 -> 右子树）和中序遍历（Inorder Traversal，即左子树 -> 根节点 -> 右子树），你可以通过这两个序列重建出原始的后序遍历（Postorder Traversal，即左子树 -> 右子树 -> 根节点）。后序遍历的过程可以这样操作：

1. 遍历完成后序序列，找到最后一个元素。这个元素通常是右子树的最深节点，因为在中序遍历中它会出现在所有左子节点之后。
2. 从后序序列中移除该节点，然后在剩余的序列中寻找前序序列的第一个元素。这将是当前节点的左子树的根节点。
3. 接着，在剩下的后序序列中，你会看到前序序列中左子树剩余部分的后序顺序，这部分构成了新的子问题，继续步骤1和2直到序列为空。

简单来说，你可以通过匹配前序和中序序列来确定每个节点的位置，然后按照“左、右、根”的顺序构建后序序列。如果你需要具体的代码实现，我可以提供一个示例。

相关问题

二叉树输入前序和中序怎么输出后序.c

这是一个二叉树遍历的问题。如果已知二叉树的前序遍历和中序遍历，可以通过递归的方式构造出该二叉树并输出后序遍历。

具体步骤如下：

1. 根据前序遍历确定二叉树的根节点；
2. 在中序遍历中找到根节点的位置，根节点左侧的部分即为左子树的中序遍历，右侧的部分即为右子树的中序遍历；
3. 根据左子树的中序遍历和左子树的前序遍历递归构造左子树；
4. 根据右子树的中序遍历和右子树的前序遍历递归构造右子树；
5. 后序遍历即为左子树后序遍历 + 右子树后序遍历 + 根节点。

具体代码实现如下：

#include<iostream>
using namespace std;
const int N=505;
int pre[N],in[N],post[N],n;
void build(int il,int ir,int pl,int pr,int &k)
{
    if(il>ir) return;
    int root=pre[pl],mid;
    for(int i=il;i<=ir;i++)
        if(root==in[i])
        {
            mid=i;
            break;
        }
    build(il,mid-1,pl+1,pl+mid-il,&k);
    build(mid+1,ir,pl+mid-il+1,pr,&k);
    post[k++]=root;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>pre[i];
    for(int i=0;i<n;i++)
        cin>>in[i];
    int k=0;
    build(0,n-1,0,n-1,k);
    for(int i=0;i<n;i++)
        cout<<post[i]<<" ";
    cout<<endl;
    return 0;
}

该算法的时间复杂度为O(n^2)，因为每次构建二叉树时需要在中序遍历中查找根节点的位置，可以通过使用哈希表优化到O(n)。

C语言创建完二叉树后输出二叉树的前序，中序和后序遍历

好的，根据您的问题，我来给您讲解一下如何实现。

二叉树的遍历方式有前序遍历、中序遍历和后序遍历。这里我们可以利用递归的方式实现。

具体实现步骤如下：

1. 定义二叉树结构体

typedef struct BiTNode
{
    char data;              // 结点值
    struct BiTNode *lchild; // 左孩子
    struct BiTNode *rchild; // 右孩子
}BiTNode, *BiTree;

2. 编写建立二叉树的函数

// 创建二叉树
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c", &ch);

    if (ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

3. 编写前序遍历函数

// 前序遍历
void PreOrder(BiTree T)
{
    if (T == NULL)
    {
        return;
    }
    printf("%c ", T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

4. 编写中序遍历函数

// 中序遍历
void InOrder(BiTree T)
{
    if (T == NULL)
    {
        return;
    }
    InOrder(T->lchild);
    printf("%c ", T->data);
    InOrder(T->rchild);
}

5. 编写后序遍历函数

// 后序遍历
void PostOrder(BiTree T)
{
    if (T == NULL)
    {
        return;
    }
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%c ", T->data);
}

6. 调用建立二叉树的函数并输出遍历结果

int main()
{
    BiTree T = NULL;
    printf("请输入先序遍历序列：\n");
    CreateBiTree(&T);
    printf("前序遍历结果：");
    PreOrder(T);
    printf("\n中序遍历结果：");
    InOrder(T);
    printf("\n后序遍历结果：");
    PostOrder(T);
    printf("\n");
    return 0;
}

这样就可以根据输入的先序遍历序列建立一棵以二叉链表表示的二叉树，并输出这棵树的前序、中序和后序遍历结果了。