Binary tree constructing

Hi ! Following is an input files, which states the information of each node in a binary tree :

9

1 e 0 0 
2 z 0 0 
3 e 1 2 
4 i 0 0 
5 e 0 0 
6 h 0 0 
7 a 3 4
8 w 5 6 
9 f 7 8

The first number in the file(ie 9) means the number of nodes in this tree.
Each line stands for a node, with the first number meaning the ID of the node, second character means the data it stores, third and forth number mean its left and right children's ID, respectively.

The question is, how should I read in this file and construct a binary tree using the information in it?

Thx in advance !


Last edited on
The first step is always the same, make sure you can parse the data reliably before doing anything else.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;

int main()
{
  ifstream inf("foo.txt");
  int numNodes;
  inf >> numNodes;
  for ( int i = 0 ; i < numNodes ; i++ ) {
    int nodeNum, left, right;
    char data;
    while ( inf >> nodeNum >> ws >> data >> left >> right ) {
      cout << "N=" << nodeNum
           << ", C=" << data
           << ", L=" << left
           << ", R=" << right
           << endl;
    }
  }
  return 0;
}


$ g++ foo.cpp
$ ./a.out 
N=1, C=e, L=0, R=0
N=2, C=z, L=0, R=0
N=3, C=e, L=1, R=2
N=4, C=i, L=0, R=0
N=5, C=e, L=0, R=0
N=6, C=h, L=0, R=0
N=7, C=a, L=3, R=4
N=8, C=w, L=5, R=6
N=9, C=f, L=7, R=8


After that, it looks like a http://www.cplusplus.com/reference/queue/queue/ of nodes would be a good thing.
1
2
3
struct node{
   node *parent, *left_child, *right_child;
};
┬┐do you actually care about your parent?
if you use a vector to store the node, then you can use indices instead of pointers
How should I connect each node by using a vector container?
Is there any example?
Registered users can post here. Sign in or register to post.