- cook the code

Thursday 22 June 2017


Construct Full Binary Tree from given preorder and postorder traversals



#include <iostream>
#include <stdlib.h>
using namespace std;

 // A binary tree node
struct node
{
    int data;
    struct node* left, *right;
};

// Utility function to allocate memory for a new node
struct node* newnode(int data)
{
    struct node* node = new(struct node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

void inorder(struct node * root)
{
    if(root)
    {
        inorder(root -> left);
        printf("%d ", root -> data);
        inorder(root -> right);
    }
}

struct node * make(int pre[], int post[], int *s, int *e, int *preIndex)
{
    struct node * root = newnode(pre[*preIndex]);
    (*preIndex)++;
    if(root -> data == post[*s])
    {
        (*s)++;
        return root;
    }
    root -> left = make(pre, post, s, e, preIndex);
    root -> right = make(pre, post, s, e, preIndex);
    (*s)++;
    return root;
}

int main ()
{
    int pre[] = {1, 2, 4, 5, 3, 6, 7}; //{1, 2, 4, 8, 9, 5, 3, 6, 7};
    int post[] = {4, 5, 2, 6, 7, 3, 1};  //{8, 9, 4, 5, 2, 6, 7, 3, 1};
    int size = sizeof( pre ) / sizeof( pre[0] );
   
     int s = 0, e = size - 1, preIndex = 0;
    struct node *root = make(pre, post, &s, &e, &preIndex);

    printf("Inorder traversal of the constructed tree: \n");
    inorder(root);

    return 0;
}

No comments:

Post a Comment