3-CNF

Reconstruction of preorder from inorder,postorder

#include <iostream>
#include <map>
#include <vector>
#include <stdio.h>

using namespace std;

typedef map<int, int> IntIntMap;
typedef vector<int> IntVector;

IntVector inVector;
IntVector postVector;
IntIntMap inMap;
IntIntMap postMap;
IntVector preVector;

/*
This is the source of data:
http://en.wikipedia.org/wiki/Tree_traversal

Depth-first

    Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
    Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right)
    Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)
    */

void init()
{
    size_t i;
    inVector.push_back('A');
    inVector.push_back('B');
    inVector.push_back('C');
    inVector.push_back('D');
    inVector.push_back('E');
    inVector.push_back('F');
    inVector.push_back('G');
    inVector.push_back('H');
    inVector.push_back('I');

    postVector.push_back('A');
    postVector.push_back('C');
    postVector.push_back('E');
    postVector.push_back('D');
    postVector.push_back('B');
    postVector.push_back('H');
    postVector.push_back('I');
    postVector.push_back('G');
    postVector.push_back('F');
    for (i = 0; i < postVector.size(); i ++)
    {
        postMap.insert(make_pair(postVector[i], i));
    }
}

// find the biggest index in post and return its value
int findRoot(const IntVector& inSubTree)
{
    size_t index = 0;
    for (size_t i = 0; i < inSubTree.size(); i ++)
    {
        size_t pos = postMap[inSubTree[i]];
        if (pos > index)
        {
            index = pos;
        }
    }
    return postVector[index];
}

void process(int root, IntVector inOrderVector)
{
    if (inOrderVector.size() > 0)
    {
        preVector.push_back(root);
    }
    else
    {
        return;
    }
    int index;
    for (index = 0; index < inOrderVector.size(); index ++)
    {
        if (inOrderVector[index] == root)
        {
            //split vector to left/right sub tree
            IntVector left(inOrderVector.begin(), inOrderVector.begin()+index);
            if (left.size()>0)
            {
                int leftRoot = findRoot(left);
                process(leftRoot, left);
            }
            IntVector right(inOrderVector.begin() + index+1, inOrderVector.end());
            if (right.size()>0)
            {
                int rightRoot = findRoot(right);
                process(rightRoot, right);
            }
        }

    }
}

int main()
{
    init();
    int root = postVector[postVector.size()-1];
    process(root, inVector);
    for (int i = 0; i < preVector.size(); i ++)
    {
        char ch = preVector[i];
        printf("%c,", ch);
    }
    printf("\n");
    return 0;
}