Ronzii's Blog

Just your average geek's blog

Create Tree from Postorder, Preorder and Level Order Traversals

#include <iostream>
#include <queue>
using namespace std;

class Tree
{
    class TreeNode
    {
    public:
        int value;
        TreeNode* left;
        TreeNode* right;
    } ;
public:
    static void preorderTraversal(TreeNode* current)
    {
        cout<<current->value<<" ";
        if(current->left)
        {
            preorderTraversal(current->left);
        }
        if(current->right)
        {
            preorderTraversal(current->right);
        }
    }
    static void inorderTraversal(TreeNode* current)
    {
        if(current->left)
        {
            inorderTraversal(current->left);
        }
        cout<<current->value<<" ";
        if(current->right)
        {
            inorderTraversal(current->right);
        }
    }
    static void postorderTraversal(TreeNode* current)
    {
        if(current->left)
        {
            postorderTraversal(current->left);
        }
        if(current->right)
        {
            postorderTraversal(current->right);
        }
        cout<<current->value<<" ";
    }
    static void levelorderTraversal(TreeNode* current)
    {
        queue<TreeNode*> q;
        q.push(current);
        TreeNode* temp;
        while(!q.empty())
        {
            temp = q.front();
            q.pop();
            cout<<temp->value<<" ";
            if(temp->left)
            {
                q.push(temp->left);
            }
            if(temp->right)
            {
                q.push(temp->right);
            }
        }
    }
    static int search(int x[],int start, int end,char value)
    {
        for(int i=start; i<end; i++)
        {
            if(x[i]==value)
            {
                return i;
            }
        }
    }
    static TreeNode* createTreeFromPreOrder(int inorder[],int preorder[], int start, int end)
    {
        static int position = 0;
        if(start>end)
        {
            return NULL;
        }
        TreeNode* temp = new TreeNode();
        temp->value = preorder[position++];
        if(start==end)
        {
            return temp;
        }
        int mid = search(inorder,start,end,temp->value);
        temp->left = createTreeFromPreOrder(inorder,preorder,start, mid-1);
        temp->right = createTreeFromPreOrder(inorder,preorder,mid+1,end);
        return temp;
    }
    static TreeNode* createTreeFromPostOrder(int inorder[],int postorder[], int start, int end)
    {
        static int position = end;
        if(start>end)
        {
            return NULL;
        }
        TreeNode* temp = new TreeNode();
        temp->value = postorder[position--];
        if(start==end)
        {
            return temp;
        }
        int mid = search(inorder,start,end,temp->value);
        temp->right = createTreeFromPostOrder(inorder,postorder,mid+1,end);
        temp->left = createTreeFromPostOrder(inorder,postorder,start, mid-1);
        return temp;
    }
    static TreeNode* createTreeFromLevelOrder(int inorder[],int levelorder[], int start, int end,int level)
    {
        if(start>end)
        {
            return NULL;
        }
        TreeNode* temp = new TreeNode();
        temp->value = levelorder[level-1];
        if(start==end)
        {
            return temp;
        }
        int mid = search(inorder,start,end,temp->value);
        temp->left = createTreeFromLevelOrder(inorder,levelorder,start, mid-1,2*level);
        temp->right = createTreeFromLevelOrder(inorder,levelorder,mid+1,end,2*level+1);
        return temp;
    }
};
int main()
{
    int inorder[] = {5,2,7,1,8,3,9};
    int preorder[] = {1,2,5,7,3,8,9};
    int postorder[] = {5,7,2,8,9,3,1};
    int levelorder[] = {1,2,3,5,7,8,9};
    int len = sizeof(inorder)/sizeof(inorder[0]);
    Tree::preorderTraversal(Tree::createTreeFromPreOrder(inorder,preorder,0,len-1));
    cout<<endl;
    Tree::postorderTraversal(Tree::createTreeFromPostOrder(inorder,postorder,0,len-1));
    cout<<endl;
    Tree::levelorderTraversal(Tree::createTreeFromLevelOrder(inorder,levelorder,0,len-1,1));
    return 0;
}
Advertisements

July 25, 2011 - Posted by | C++ | , ,

1 Comment »

  1. Much appreciated!

    Comment by vps uk | August 3, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s