Building an incomplete binary tree

Question

I'm trying to build an incomplete binary tree from data provided in a text file

2
3 8
2 10 0 12
1 8 0 0 4 0

which would form a tree like this:

I know roughly what I need to do, I think:

read in from the file line-by-line.
pass an array to the build function.
As it's building the tree, the tree data type will keep track of the last nodes that it added in an array of pointers (eg, if we just finished adding the 3rd row of the text file, the a previous nodes array would look like pointers to the nodes containing [2 10 12]
as we start adding the 4th line, we create an array of 3*2=6 length to store pointers to the nodes as we add them.
we go through the array of pointers from the previous run (containing [2 10 12]) and create left and right children nodes for any non-zero keys that got passed through. We put pointers to those nodes in our 6-long array.
when we get a blank line, we're done.

The problem I'm running into is, I'm not sure how to store a array of pointers to nodes that changes size each time I call the build function and is a class variable (for the Tree class). Am I going about this the right way? Is there an easier way to approach this?

Is efficiency a concern? You certainly don't need your array of pointers unless you are trying to be efficient. You could just use the position of each integer within it's line to tell you where to add that integer. — john
– john, Commented Sep 9, 2015 at 5:52
Another way would be to build the tree from the leaves up (instead of the root down), that would require reading the whole file before starting to build the tree but it would be pretty simple. — john
– john, Commented Sep 9, 2015 at 5:54
No, I'm not worried about efficiency. If the information in the text file described a complete tree (ie if row n had 2^n values), then I could just use the position to know where to put the value. However, each row of the text file only has information if the previous row's node was non-null so it isn't all that easy to use position to tell where which should be the parent node. — RagingRoosevelt
– RagingRoosevelt, Commented Sep 9, 2015 at 5:56
I'm not seeing what the problem is when it's an incomplete tree. I'm assuming that only the last row would be incomplete (like your example), are you sure that's not the case? — john
– john, Commented Sep 9, 2015 at 5:57
But even if each row could be imcomplete, then you have to make an assumption that only the left most nodes will be created (otherwise the problem is ambiguous) so I still don't see the problem. — john
– john, Commented Sep 9, 2015 at 6:00

Sakib Ahammed · Accepted Answer · 2015-09-09 07:27:10Z

1

Like 2D array, array[row][column], you can use 2D vector ie. vector< vector<int> > V is a vector of vectors.

In vector< vector<int> > V, inside vector indicate row, and outside vector indicate column (for your understanding I just tell).

Here 2D vector is resize able. Not necessary that every column size will be equal. You can handle push, pop and you can store data according your memory size.

Example:

You can resize like of that:

int num_of_col = 5;
int num_of_row = 9;
double init_value = 3.14;

vector< vector<double> > matrix;
//now we have an empty 2D-matrix of size (0,0). Resizing it with one single command:
matrix.resize( num_of col , vector<double>( num_of_row , init_value ) );
// and we are good to go ...

You can learn here vector

answered Sep 9, 2015 at 7:27

Sakib Ahammed

2,4802 gold badges26 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sneftel · Accepted Answer · 2015-09-10 15:47:02Z

1

Why don't you use a std::vector instead of array? It behaves exactly like an array but is resizable.

Example of usage:

using namespace std;
Node *a = new Node;
vector<Node*> vec;
vec.push_back(a);

edited Sep 10, 2015 at 15:47

Sneftel

41.9k13 gold badges78 silver badges112 bronze badges

answered Sep 9, 2015 at 7:03

Jobin Jose

1941 gold badge3 silver badges15 bronze badges

8 Comments

Sneftel Over a year ago

Because when a vector grows, it may move in memory, invalidating existing pointers.

Jobin Jose Over a year ago

How does the vector moving in memory invalidate existing pointers? Could you kindly explain that?

Sneftel Over a year ago

Because pointers between nodes in the vector will no longer point to the same nodes.

Jobin Jose Over a year ago

So you are basically saying that the values of the Node* objects being stored in the vector will change each time the vector changes its size? If so, then i highly disagree

Sneftel Over a year ago

When the vector was expanded, the Node*s held by the Nodes would no longer point into allocated memory.

|

Collectives™ on Stack Overflow

Building an incomplete binary tree

2 Answers 2

Comments

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related