binary-tree - 从给定的中序和前序遍历中获取后序 BT 遍历

Question

谁能帮我把后序遍历作为gven两次遍历的输出：

按顺序：A、B、C、D、E、F、G、H、J、K、L、M、P、Q、N。

预购：C、D、E、B、G、H、F、K、L、P、Q、M、N、J、A。

如果答案是图形的，那将更有帮助。

Answer 1

非递归算法；如何计算中序和前序之间的变化 ؟؟

#include<stdio.h>                          
#include<conio.h>
#include <iostream>
using namespace std;
int find(int *p,int s,int f)
{
    int k=0;
    if (f==0)
        return -1;
    for(;k<s;k++)
        if(*(p+k)==f)
            return k;
    return -1;
}

int main()
{
    int n=15;
    int in[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'P', 'Q', 'N'};
    int pre[] = {'C', 'D','E','B', 'G', 'H', 'F', 'K', 'L', 'P', 'Q', 'M', 'N', 'J', 'A'};
    int i,k,hed,chld,s=0;
    int *j=(int *)malloc(sizeof(int)*n);
    int *p=(int *)malloc(sizeof(int)*n);
    for(k=0;k<n;k++)
       j[k]=1;
          for(k=0;k<n;k++){
        chld=find(in,n,pre[k]);
        if(1!=j[chld])
        {
            int o=chld,t=chld;
            while(j[chld]==j[--t])
                j[t]=j[chld]*2;
            while(j[chld]==j[++o])
                j[o]=j[chld]*2+1;
        }
                  else{
            int t;
            for(t=0;t<n;t++)
                if(t<chld)
                    j[t]++;
                else if(t>chld)
                    j[t]+=2;
                     }
    }
    k=1,s=0;
    while(1){   hed=find(j,n,k);
    if(s>0&&*(p+s-1)==k)
    {
        for(chld=0;chld<n;chld++)
            if(j[chld]==k)
                break;
        cout<<(char)in[chld]<<" ";
        if(k==1)
            break;
        s--;
        hed=-1;
    }
    if(hed>-1)
    {
        *(p+s)=k;
        s++;
        k*=2;
    }
    else if(k%2==0)
    { 
        k++;
        continue;
    }
    else {
        k=k/2;
        continue;
    }
    }
    getch();
    return 0;
}