Вот мой ответ. Извините за огромное количество кода!
Сначала немного struct с
// contains the whole line as well as the series for ease of id
struct _Payload
{
char *line; // the line of text
int series; // the number in [ ] at the end of that line
int numElements; // the number of elements in the line
};
// a tree sorted by the series of the Payloads within
struct _PayloadTree
{
struct _Payload *payload;
struct _PayloadTree *left;
struct _PayloadTree *right;
};
// a tree sorted by the number of elements in the PayloadTree subtrees
struct _Tree
{
int numElements; // for sorting
struct _PayloadTree *payloadTree;
struct _Tree *left;
struct _Tree *right;
};
typedef struct _Payload Payload;
typedef struct _PayloadTree PayloadTree;
typedef struct _Tree Tree;
Далее, некоторые вспомогательные функции:
Payload *createPayload(char *line, int series, int numElements)
{
Payload * payload = (Payload *)malloc(sizeof(Payload));
payload->line = line;
payload->series = series;
payload->numElements = numElements;
return payload;
}
PayloadTree *createPayloadTree(Payload *p)
{
PayloadTree * payloadTree = (PayloadTree *)malloc(sizeof(PayloadTree));
payloadTree->payload = p;
payloadTree->left = payloadTree->right = NULL;
return payloadTree;
}
Tree *createTree(int numElements)
{
Tree * tree = (Tree *)malloc(sizeof(Tree));
tree->numElements = numElements;
tree->payloadTree = NULL;
tree->left = tree->right = NULL;
return tree;
}
Теперь, чтобы добавить вещи в дерево. Сначала мы находим количество элементов корзины, затем в этом месте в соответствующей серии блоков (PayloadTree)
void addPayloadToPayloadTree(Payload *p, PayloadTree *payloadTree)
{
// these are sorted according to the value in 'series'
if(payloadTree == NULL) return;
PayloadTree *pt = payloadTree;
while(pt != NULL)
{
// should this happen?
if(p->series == pt->payload->series) break;
else if(p->series < pt->payload->series)
{
if(pt->left == NULL) pt->left = createPayloadTree(p);
else pt = pt->left;
}
else
{
if(pt->right == NULL) pt->right = createPayloadTree(p);
else pt = pt->right;
}
}
}
// Main way to add a line to the tree
void addPayload(Payload *p, Tree **tree)
{
if(*tree == NULL) *tree = createTree(p->numElements);
Tree *t = *tree;
while(t != NULL)
{
if(t->numElements == p->numElements) break;
else if(t->numElements > p->numElements)
{
// look left
if(t->left == NULL)
{
t->left = createTree(p->numElements);
break;
}
t = t->left;
}
else
{
// look right
if(t->right == NULL)
{
t->right = createTree(p->numElements);
break;
}
t = t->right;
}
}
// now t points to the right bucket
if(t->payloadTree == NULL) t->payloadTree = createPayloadTree(p);
addPayloadToPayloadTree(p, t->payloadTree);
}
Наконец методы печати. Печать справа налево:
void printPayloadTree(PayloadTree *pt)
{
if(pt == NULL) return;
printPayloadTree(pt->right);
printf("%s\n", pt->payload->line);
printPayloadTree(pt->left);
}
void printTree(Tree *t)
{
if(t == NULL) return;
printTree(t->right);
printPayloadTree(t->payloadTree);
printTree(t->left);
}
Я пропустил функции clear и реализацию main, потому что это, конечно, решать вам. Вот метод, который я использовал для разбора строки. Вы бы назвали его с parseLine(theLine, &series, &numElements), где вы ранее объявили series и numElements типа int.
void parseLine(char *line, int *series, int *numElements)
{
char *tok = strtok(line, " ");
int n = 0;
while(tok != NULL)
{
if(tok[0] == '[')
{
// found the series
tok[ strlen(tok) - 2 ] = '\0';
*series = atoi(tok + 1);
}
else
{
n++;
}
tok = strtok(NULL, " ");
}
*numElements = n;
}