Почему рекурсия вовремя не останавливается?

Question

[Narts]

По этому уроку пытаюсь написать функцию генерации дерева Хаффмана. Считывание, получение алфавита и частот реализовал, все работает. Но вот с деревом встал в тупик.

Вот код:

...

struct SYM // представление символа
{
	unsigned char ch; // ASCII-код
	float freq; // частота встречаемости
	char code[256]; // массив для нового кода
	struct SYM *left; // левый потомок в дереве
	struct SYM *right; // правый потомок в дереве
};

...

struct SYM* buildTree(struct SYM *psym[], int N)
{
	// создаём временный узел
	struct SYM *temp = (struct SYM*)malloc(sizeof(struct SYM));
	// в поле частоты записывается сумма частот
	// последнего и предпоследнего элементов массива psym
	temp->freq = psym[N - 2]->freq + psym[N - 1]->freq;
	// связываем созданный узел с двумя последними узлами
	temp->left = psym[N - 1];
	temp->right = psym[N - 2];
	temp->code[0] = '\0';
	if (N == 2) // мы сформировали корневой элемент с частотой 1.0
		return temp;

	for (int i = 0; i < N; i++)
		if (temp->freq>psym[i]->freq)
		{
			for (int j = N - 1; j>i; j--)
				psym[j] = psym[j - 1];

			psym[i] = temp;
			break;
		}
		return buildTree(psym, N - 1);
}

void makeCodes(struct SYM *root)
{
	if (root->left)
	{
		strcpy(root->left->code, root->code);
		strcat(root->left->code, "12");
		makeCodes(root->left);
	}
	if (root->right)
	{
		strcpy(root->right->code, root->code);
		strcat(root->right->code, "45");
		makeCodes(root->right);
	}
}


void division(struct alphabet *alphabetLetter, int groupCount)
{
	int psysms[256];
	struct SYM str[256];

	for (int i = 0; i < alphabetLen; i++) {

		// Пысы: в массиве структур alphabetLetter как раз находится наш алфавит, с 						 
  		частотами

		psysms[i] = &alphabetLetter[i];

		str[i].ch = alphabetLetter[i].letter;
		str[i].code[0] = '\0';
		str[i].freq = alphabetLetter[i].probability;
		str[i].left = NULL;
		str[i].right = NULL;

	}

	struct SYM *root = buildTree(psysms, alphabetLen);
	makeCodes(root);

}

...

int main() {

division(alphabetLetter, alphabetLen); // alphabetLetter - массив структур алфавита (символ, частота, код)

}

При компиляции выдает ошибку:


Методом научного тыка понял что процедура makeCodes выполняется больше раз, чем нужно, видимо проверки if (root->left) и if (root->right) не работают.
Чего я только не перепробовал, какие только проверки не сооружал, все равно процедура выполняется больше нужного количества раз.

Заранее спасибо за помощь

Comments

[res2001]

Почему у вас SYM->freq типа float? Разве частота встречаемости данного символа (количество вхождений данного символа в заданный текст) - это вещественное число?
Зачем вам для code массив char? Хватит и обычного int или uint. Вообще code можно генерировать в процессе обхода дерева на лету.
Избавьтесь от рекурсии.
Где определение struct alphabet и как формируется alphabetLetter.
Метод научного тыка замените на отладчик.

Answer 1

[jcmvbkbc]

При компиляции выдает ошибку

А на скрине -- отладчик не может найти исходник для функции strcat. Т.е. всё с компиляцией нормально.

struct SYM* buildTree(struct SYM *psym[], int N)
...

void division(struct alphabet *alphabetLetter, int groupCount)
{
  int psysms[256];
...
  psysms[i] = &alphabetLetter[i];
...
  struct SYM *root = buildTree(psysms, alphabetLen);
...
}

Тут происходит что-то фееричное с типами: сначала указатели записываются в массив int, потом этот массив передаётся в buildTree который ожидает совсем другое.