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