Consider a representation to store a binary tree in a file in which the whole tree is represented within two brackets in the following format. First print the root in brackets, and then within those brackets print the left subtree in its own brackets, and then the right subtree in its own brackets. Recursively follow this format for the left and right subtrees. Empty tree is represented as ( ). For example, following tree shall be represented as: (A (B (D) ( )) (C ( ) ( ))) A / \ B C / D Write a program to construct a binary tree from a given file “tree.txt” which contains bracket representation of a binary tree.

#include <stdio.h>
#include <fcntl.h>
#include <stdexcept>
#include <iostream>
#include <stdlib.h>

struct Node
{
Node *left;
Node *right;
char val;

};

typedef Node * Tree;

using namespace std;

Tree construct(int fd)
{
char c;

if(read(fd, &c, 1) == -1)
throw runtime_error("Can't read from file");

if(c == '(') //beginning of node
{
if(read(fd, &c, 1) == -1)
throw runtime_error("Can't read from file");

if(c == ')') //empty node
{
return NULL;
}

Node * n = (Node *)calloc(1, sizeof(Node));

n->val = c;
n->left = construct(fd);
n->right = construct(fd);

if(read(fd, &c, 1) == -1)
throw runtime_error("Can't read from file");

if(c == ')') //end of node
{
return n;
}

throw runtime_error("Incorrect format");
}

throw runtime_error("Incorrect format");
}

void preorder(Tree t)
{
if(t == NULL) return;

printf("%c ", t->val);
preorder(t->left);
preorder(t->right);
}

int main()
{
int fd = open("tree.txt", O_RDONLY);
if(fd == -1)
return -1;

try{
Tree t = construct(fd);

preorder(t);

printf("\n");
}catch(runtime_error &e)
{
cout<<"Exception "<<e.what()<<endl;
}
}
Advertisements

One thought on “Consider a representation to store a binary tree in a file in which the whole tree is represented within two brackets in the following format. First print the root in brackets, and then within those brackets print the left subtree in its own brackets, and then the right subtree in its own brackets. Recursively follow this format for the left and right subtrees. Empty tree is represented as ( ). For example, following tree shall be represented as: (A (B (D) ( )) (C ( ) ( ))) A / \ B C / D Write a program to construct a binary tree from a given file “tree.txt” which contains bracket representation of a binary tree.

  1. Hi Sambasiva.. there is some problem with the code. Here the implementation in C.. check there just one condition is missing.#include #include #include #include struct node { char val; struct node * left; struct node * right;};struct node* createTreeFromFile(int fd);void printTree(struct node *);int main(){ int fd; struct node * root; fd = open("binaryTreeFile.txt", O_RDONLY); if ( fd == -1 ) printf("\nFailed to open the file"); root = createTreeFromFile(fd); printf("\n\n"); printTree(root); printf("\n\n"); return 0;}struct node * createTreeFromFile(int fd){ struct node * root; char ch; read(fd,&ch,1); if (ch == '(' ) { read(fd,&ch,1); if(ch == ')') return NULL; else { root = (struct node *) malloc( sizeof(struct node)); root->val= ch; read(fd,&ch,1); if ( ch == ')' ) { root->left = NULL; root->right = NULL; return root; } else { lseek(fd,-1,SEEK_CUR); } root->left = createTreeFromFile(fd); root->right = createTreeFromFile(fd); read(fd,&ch,1); if ( ch == ')' ) { return root; } } } else { return NULL; } return root;}void printTree(struct node * root ){ if ( root == NULL ) return; printf("%c ", root->val); printTree(root->right); }

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