'Creating a tree with Breadth-First Search
I'm trying to generate a tree from string in which this tree is "coded" in Breadth-First Search way. My structures:
/* declaration for queue structure */
typedef struct node node;
/* queue structure for algorithms */
typedef struct queue {
node *item;
struct queue *nextItem;
} queue;
/* tree node */
typedef struct node {
int value;
int numOfChildren; // to avoid the necessity of creating "dummy nodes" at the end of children array
struct node **children;
} node;
Examples:
For input "20." there should be a tree:
20
For input "20. 10 30 40 50." there should be a tree:
20
10 30 40 50
And for input "20. 10 30 40 50. . 31 32. . 51 52." there should be a tree:
20
10 30 40 50
31 32 51 52
So the tree is "coded" with numbers, spaces and dots. And I have a problem with trees generating. Here's my UNFINISHED initTree(char *) function:
void initTree(char *strTree) {
queue *queueStart = NULL;
queue *queueEnd = NULL; // to speed up adding items to queue...
queue *queuePointer = NULL;
int numOfChildren = 0;
while(*strTree != '\0') {
if(*strTree == '.') {
if(queueStart == queueEnd) { // first dot
if(ROOT == NULL)
ROOT = queueStart->item;
} else if(*(strTree-1) == ' ' && numOfChildren == 1) {
queueStart = queueStart->nextItem;
} else { // queueStart != queueEnd && numOfChildren > 0
queueStart->item->children = childrenConstructor(numOfChildren);
queueStart->item->numOfChildren = numOfChildren;
if(queueStart == queuePointer)
queuePointer = queueStart->nextItem;
int i;
for(i=0; i<numOfChildren; ++i) {
queueStart->item->children[i] = nodeConstructor(queuePointer->item->value);
queuePointer = queuePointer->nextItem;
}
// REMEMBER TO DELETE QUEUE ITEM
// queue *tmp = queueStart;
queueStart = queueStart->nextItem;
}
numOfChildren = 0;
} else if(*strTree == ' ') {
++numOfChildren;
} else { // *strTree >= '0' && *strTree <= '9'
if(queueStart == NULL) {
queueStart = queueEnd = strToInt(&strTree);
queuePointer = queueStart;
} else {
queueEnd->nextItem = strToInt(&strTree);
queueEnd = queueEnd->nextItem;
}
if(numOfChildren == 1)
queuePointer = queueEnd;
}
++strTree;
}
// REMEMBER TO DELETE A QUEUE
}
So, what's the matter? Well, when I'm trying to print that tree in simple way (only for testing purposes), with input "20. 10 30 40 50. . 31 32. . 51 52.", the second "level" of the tree is not "visible". As if children haven't been added to the tree. Here's my print function:
void simpleRecursiveTreePrint(node *n) {
if(n == NULL)
return;
printf("value %d (num of children: %d)\n", n->value, n->numOfChildren);
int i;
for(i=0; i<n->numOfChildren; ++i)
simpleRecursiveTreePrint(n->children[i]);
return;
}
And output (for mentioned input):
value 20 (num of children: 4)
value 10 (num of children: 0)
value 30 (num of children: 0)
value 40 (num of children: 0)
value 50 (num of children: 0)
So, well, it looks like the nodes were lost... But in vscode, when I'm debbuging, nodes 31, 32, 51 and 52 are processed in function initTree(char *). Hm, maybe there's a problem with pointers assignment? Or in allocating a memory? I really don't know... And I got headache from this coding :D
Anyone?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
