This thing has been driving me crazy for a while now.
I need to create and traverse (post order) a general tree where each node (a structure) is added by the user via console.
I am NOT allowed to use STL.
The user specifies how many nodes will be added, and how many 'child' nodes it can hold (number) and the name of the node (string). Example input:
5
1 A
2 B
1 C
1 D
3 E
The above means that 5 nodes will be added. The first one (A) can accept one 'child' node, (B) can accept 2 such nodes and (C) can accept 1 etc. The newly added nodes have to always be added to the 'highest' possible node from the top (if it still can accept a new 'child' node, if not possible you go to the next one).
The idea is to create an array (I know how many nodes will be added in total) and put those nodes specified by the user there and 'link' them accordingly using array of pointers inside of a structure.
The output of given example should be: E C D B A
I have written the whole thing as follows but I am unable to traverse the tree:
structure:
struct node {
string name = "";
int noChildrenAdded = 0;
int possibleNoChildren = 0;
int childrenFreeSlots = 0;
node* children = nullptr;
node* father = nullptr;
};
traverse function that's not working
void traverse(node* father)
{
cout << father->name << endl;
if (father == nullptr) {
return;
}
for (int i = 0; i < father->possibleNoChildren; i++) {
if (&father->children[i] == nullptr) {
continue;
}
traverse(&father->children[i]);
}
cout << father->name << "\n";
}
main
int main() {
int n = 0;
short g = 0;
string name;
cin >> n;
node* tree = new node[n];
node* tmp = nullptr;
//adding children to tree array
for (int i = 0; i < n; i++) {
cin >> g >> name;
tree[i].possibleNoChildren = tree[i].childrenFreeSlots = g;
tree[i].name = name;
tree[i].noChildrenAdded = 0;
tree[i].children = new node[1];
}
// making connections between nodes
for (int son = 1; son < n; son++) {
for (int father = 0; father < son; father++) {
if (tree[father].childrenFreeSlots > 0) {
//resizing array
if (tree[father].noChildrenAdded == 0) {
tree[father].children[0] = tree[son];
}
else {
int added = tree[father].noChildrenAdded;
tmp = new node[added + 1];
for (int i = 0; i < added; i++) {
tmp[i] = tree[father].children[i];
}
delete[] tree[father].children;
tree[father].children = nullptr;
tree[father].children = tmp;
tree[father].children[added] = tree[son];
tmp = nullptr;
}
tree[father].noChildrenAdded++;
tree[father].childrenFreeSlots -= 1;
break;
}
}
}
//this is how it should be
cout << "Father: " << tree[1].name << "\tchildren added: " << tree[1].noChildrenAdded << endl;
//tree[0].children[0] is holding pointer to drzewo[1] so the below should give me the same answer as above.
//this is giving me wrong answer
node* ptr = &tree[0].children[0];
cout << "Father: " << ptr->name << "\tchildren added: " << ptr->noChildrenAdded << endl;
//traverse(&tree[0]);
delete[] tree;
}
THE PROBLEMS
I am unable to access details of a structure (for example noChildrenAdded) - I am getting zero, despite the fact that noChildrenAdded is populated. When I access it via tree array I am getting the correct number but when I do it via pointer inside of a struct I am getting 0.
Example:
This is correct: cout << "Father: " << tree[1].name << "\tchildren added: " << tree[1].noChildrenAdded << endl;
But this is not (despite both should be giving the same number/answer):
//tree[0].children[0] is holding pointer to tree[1] so the below should give me the same answer as above.
//this is giving me wrong answer
node* ptr = &tree[0].children[0];
cout << "Father: " << ptr->name << "\tchildren added: " << ptr->noChildrenAdded << endl;
I expect I have messed up assigning children to the *children array inside of a struct. The name seems to be accessible fine but not the noChildren.
Both should be giving the same answer but they are not:
Any help would be greatly appreciated!
PS: when I use this code with static array of children everything is ok, traversal works fine but when I get a dynamic array it's broken. Static array alas won't do as it taking too much memory and takes way too long so my program fails the requirements.
Just as @igor-tandetnik suggested, using an array of node* pointers solved the problem. In my case solution was to use node** children not node *children.
