c++ 二叉树遍历

题目描述

二叉树是每个内部结点最多只有两个子结点且两个子结点有序的树。如下图就是一棵二叉树：

对于一棵二叉树，有三种基本遍历方式：
1.前序遍历：先访问根结点，然后再前序遍历左子树，最后前序遍历右子树；

2.中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树；

3.后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根结点。

对于上图，前序遍历的结果是ABDEHCFGI。中序遍历的结果是DBEHAFCIG，后序遍历的结果是DHEBFIGCA。

现在给出二叉树的前序和中序遍历，请输出相应的后序遍历。

输入

第一行前序遍历的结果

第二行中序遍历的结果

都是大写字母，且结点的标识不重复，最多只有100个结点。

输出

输出后序遍历的结果

样例输入

ABDEHCFGI
DBEHAFCIG

样例输出

DHEBFIGCA

Source Code

#include <iostream>
#include <string.h>
using namespace std;
char a[110],b[110];//a[]是前序遍历的结果  b[]是中序遍历的结果
void dfs(int f1,int e1,int f2,int e2)
{
    if(f1>e1) return;//如果找不到子节点就退出(起点大于终点)
    int rt=f1;//rt是根节点
    int p = 0;
    //计算出左子树或者右子树的下一层根节点
    for(int i=f2;i<=e2;i++)
        if(b[i]==a[rt])//如果找到了顶点
        {
            p=i;//p代表顶点在b[]里面的位置  即b[p]
            break;
        }
    int ls=p-1-f2+1;//ls表示长度
    //int rs=e2-(p+1)+1;
    dfs(f1+1,f1+1+ls-1,f2,p-1);//递归处理左子树
    //f1+1:a[]的左子树的起点  f1+1+ls-1:a[]的左子树的终点
    //f2:b[]的左子树的起点  p-1:b[]的左子树的终点
    dfs(f1+1+ls-1+1,e1,p+1,e2);//递归处理右子树
    //f1+1+ls-1+1:a[]的右子树的起点  e1:a[]的右子树的终点
    //p+1:b[]的右子树的起点  e2:b[]的右子树的终点
    printf("%c",a[rt]);//如果这是一个叶节点(既没有左子树,也没有右子树),就输出它
}
int main()
{
    //scanf("%s%s",a,b);
    cin >> a >> b;
    dfs(0,int(strlen(a))-1,int(strlen(b))-1);//起点
    cout << endl;
    return 0;
}
/*
 思路总结:
 先以a为顶点,递归寻找a的左子树  如果a有左子树,先判断下一个节点b是否为顶点 (判断b是否为顶点:判断b是否有左右子树)
 找到b的左子树的下一个节点d 再继续判断d是否有左右子树  如果没有,d为叶节点
 在找到b的右子树的下一个节点e 判断e的左右子树 如果有,继续判断下一个节点h是否有左右子树 直到找到h叶子节点
 在找到a的右子树的下一个节点c 判断c的左右子树 如果有,继续判断下一个节点 f和g 是否有左右子树 直到找到i叶子节点
 每次找到叶子节点就输出
*/