1

Can anyone help me out to get postorder traversal as output from gven two traversals:

In-order :A, B, C, D, E, F, G, H, J, K, L, M, P, Q, N.

Pre-order : C, D, E, B, G, H, F, K, L, P, Q, M, N, J, A.

It will be more helpfull if the answere is graphical.

4
  • Are you sure your inorder and preorder example is correct? Looks strange to me
    – alestanis
    Oct 24, 2012 at 19:22
  • We do not solve homeworks. The answer how to do that is avaiable on Wikipedia. Oct 24, 2012 at 19:23
  • @Vash I'm a bit confused about the Postorder output because I have been given a sample I/O as Postorder : E, D, C, H, G, Q, P, N, M, L, K, J, F, B, A .But i'm not sure if it is write or not. thanks. Oct 24, 2012 at 19:30
  • @HammrerEngineer, As alestanis sad, your input are incorect. The C is on the top from pre-order so everything in inorder before C should be on the left side. But in Pre-orde next element is D. That is after C in in-order. And this is imposible. Oct 24, 2012 at 19:45

1 Answer 1

0

Non-Recursive Algorithm ;How to Calculate change Between inorder and preorder ؟؟

#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;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.