tags:

views:

127

answers:

2

The inforamtion below is given in a file, and You have to make a function to rebuild the binary tree in C++..

node   leftchild  rtchild

1       2   4
2       $   5
5       6   7
6       $   $
7       $   $
4       $     8
8       $   $

$- Empty

Can anyone suggest some idea to rebuild the binary tree...???

I have done:-

void rebuild_btree(node *tree) 
{
    ifstream fin("data.txt");
    string a;

    if (!fin)
        cout << "\nError in opening file.." << endl;
    else
        cout << "\nFile is successfully opened.." << endl;

    while (!fin.eof()) 
    {
        fin >> a;
        tree = insert(tree, a);
    }
    fin.close();
}

node* insert(node *root, string &dat)
{
    if(dat != "$")
    { 
       if(root == NULL)
       {
          root = new node;
          strcpy(root->data, dat);
          root->left = root->right = NULL;
       }
       else if (root->left == NULL)
            root->left = insert(root->left, dat);
       else
            root->right = insert(root->right, dat);
       return root;
    }
    return root;
}

This is not working..I think there is some mistake which i'm not getting...If you can catch then suggest me ....

A: 

First impression: you are mixing C and C++ idioms all over: you declare char a[20], pass it to insert() as a string (with implicit conversion), then compare it using strcmp() (which should not even work, as it expects a const char*, not a string). Instead, you should declare it as string right from the start, pass it as a const string& to avoid unnecessary copying, and compare it using ==.

You also seem to be inserting the same value into the tree over and over, by recursively calling insert(). You should instead read tuples of 3 values from the file at once, then insert this as a subtree once, at the correct place.

Btw "not working" is a really vague description - please give details about what happens on execution. Do you get wrong results, a crash, an infinite loop, ...?

Péter Török
This is not a big mistake..I expect to find some logical mistake..which i'm not getting..
Abhi
@Abhi, see my update. Btw mixing C and C++ is definitely a big problem in general, which can bite you in more ways you can count :-(
Péter Török
Ok...i have corrected that..but still some logical mistake..:( :(
Abhi
@Abhi, if you post your updated code (and the exact result of execution), you have a better chance of getting help :-)
Péter Török
@Abhi, you still haven't solved the logical issue I describe in the 2nd paragraph of my answer.
Péter Török
Its gets run successfully...but does not show any result...
Abhi
@Abhi: I see no code to display the results.
Martin York
+1  A: 

Problem 1:

Don't do this: (It is wrong). The EOF flag is not set until you try and read past the EOF, while the last successful read reads up-to (but not past) the EOF. So you are entering the loop one more time than required.

while (!fin.eof()) 
{
    fin >> a;
    tree = insert(tree, a);
}

It should be written like this: This works because the operator>> returns a reference to a stream. When a stream is used in a boolean context (like the conditional of a while) it is converted into an object that is convertible to bool with a value that is true if non of the error flags are set. Therefore if the read succeeded then the loop is entered otherwise it is not.

while (fin >> a) 
{
    tree = insert(tree, a);
}

Problem 2:

This obviously does not compile as String is not a standard type.
The type is string (lowercase s) and it is in the std:: namespace. So please use std::string.

If this is a type you have defined then we need to know what it is to understand how this line works:

fin >> a;

Problem 3:

The function insert() does not return a value if the passed String is "$". A C++ function must always return a value (unless the return type is void). Otherwise it is 'Undefined Behavior'.

Problem 4:

Insert() is obviously not going to work.

  • You do not try and distinguish the three different input types:
    could be an 'integer index' a '$ or a ','.
  • You do not corrolate the input positions to the structure of the tree.

Problem 5:

You should think about a different input format for a binary tree. This is particularly hard to parse and re-build as it requires two passes. You need a first pass to read all the nodes. Then you need a second pass to re-build the tree structure.

This is obviously homework!

Hint:

Read a line at a time and parse the line correctly:

std::string  line;
std::getline(fin, line);

Parse the whole line in one go and build an object to represent the node. Unfortunately you can built the real node as this input format requires two passes.

struct TmpNode { int value; std::string left; std::string right; }  tmp;
std::istringstream data(line);

data >> tmp.value >> tmp.left >> tmp.right;

Since you need a two phase build 1) read 2) build tree. You need to store the TmpNode objects until you have them all and can build the tree.

std::map<int,TmpNode>  nodes;
nodes[boost::lexical_cast<int>(tmp.value)] = tmp;

Once you have all the TmpNodes stored in the map. You can now easily iterate over the map and build your tree.

node* buildTree(std::string const& nodeID)
{
    if (nodeID == "$") { return NULL;}

    TmpNode& n = nodes[boost::lexical_cast<int>(nodeID)];
    return new node(nodeID, buildTree(n.left), buildTree(n.right));
}
Martin York
Hey thanx martin..:)
Abhi
+1 You put lots of work into it, so definitely deserve an upvote :-) @Abhi, you should upvote too, adhering to [the SO conventions](http://stackoverflow.com/faq).
Péter Török