给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)

本文介绍二叉树的前序、中序和后序遍历的基本概念,并通过一个示例程序展示了如何根据给定的前序和中序遍历结果重构二叉树并输出后序遍历结果。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

二叉树的前序、中序、后序遍历的定义:

 前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树; 

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;

 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 

 

样例输入:
ABC
BAC
FDXEAG
XDEFAG
样例输出:
B C A
X E D G A F

示例代码:

#include <iostream>
#include <string.h>
using namespace std;

typedef struct BinTree
{
    char data;
    BinTree* lchild;
    BinTree* rchild;
} BinTree;

void RebuildTree(BinTree* &Tree,char *pre,char *in,int len)
{
    Tree = new BinTree;
    if(Tree!=NULL)
    {
        if(len<=0)//递归截止条件
        {
            Tree = NULL;
            return ;
        }
        int index = 0;
        while(index<len&&*(pre)!=*(in+index))
        {
            //寻找当前的root结点(包含子树)
            index++;
        }
        Tree->data = *(pre);
        RebuildTree(Tree->lchild,pre+1,in,index);//去掉root结点
        RebuildTree(Tree->rchild,pre+1+index,in+1+index,len-(index+1));//去掉左边和根节点
    }
    return ;
}

void PostOrderTravese(BinTree* Tree)
{
    //后序遍历输出
    if(Tree==NULL)
        return;
    PostOrderTravese(Tree->lchild);
    PostOrderTravese(Tree->rchild);
    cout<<Tree->data<<" ";
}


int main()
{
    char pre[101];  //string pre;
    char in[101];   //string in;
    while(cin>>pre>>in)
    {
        BinTree* tree;
        int length = strlen(pre);
        RebuildTree(tree,pre,in,length);
        PostOrderTravese(tree);
        cout<<endl;
    }
    return 0;
}

 

 

 

 

 

 

 

评论 1
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值