Я построил двоичное дерево (дерево Хаффмана), используя приведенный ниже код, который принимает отсортированный в возрастающем порядке связанный список, однако, когда он завершает работу, он печатает битовые шаблоны, а некоторые из узлов, которые должны быть в дереве, не .
Код по сути:
устанавливает родительский узел так, чтобы он указывал на два самых нижних узла
назначает внутреннюю частоту родительского узла
указывает, что начало списка теперь находится в узлах 2 от того места, где оно было (чтобы избежать повторного использования узлов)
вставляет новый родительский узел в правильную позицию в дереве
получает длину дерева
распечатать все узлы, оставшиеся в списке
повторяется до тех пор, пока не останется один узел (который является корнем).
Любые идеи относительно того, почему он «теряет» узлы по пути?
void build_tree(pqueue *list)
{
node *temp;
node* parent_node;
int min_1, min_2, ind = 0, counter = 0, length = 2, head;
int characters[CHARACTERS];
temp = new_node();
while (length > 1)
{
min_1 = 0;
min_2 = 0;
temp = list->start;
parent_node = new_node();
parent_node->letter = '#';
min_1 = temp->frequency;
parent_node->left = temp;
temp = temp->next;
min_2 = temp->frequency;
parent_node->right = temp;
parent_node->frequency = min_1 + min_2;
list->start = temp->next;
while (ind == 0) /* inserting a node to the correct place */
{
if (temp != NULL && temp->next != NULL)
{
temp = temp->next;
if (temp->frequency >= parent_node->frequency) /* in the middle */
{
parent_node->next = temp->next;
temp->next = parent_node;
ind = 1;
}
else if (temp->next == NULL) /* at the end */
{
temp->next = parent_node;
parent_node -> next = NULL;
ind = 1;
}
}
}
ind = 0;
temp = list->start;
while (temp->next != NULL) /* get number of nodes left to insert into tree */
{
temp = temp->next;
counter++;
printf("%c : %d\n", temp->letter, temp->frequency);
}
printf("----------------------------------------------\n");
length = counter;
counter = 0;
}
printf("Found root with value of: %d\n", temp->frequency);
head = 0;
BitPatterns(temp, characters, head);
temp = list->start;
deallocate(temp, list);
}
void BitPatterns(node* root, int characters[], int head)
{
if (root->left)
{
characters[head] = 0;
BitPatterns(root->left, characters, head +1);
}
if (root->right)
{
characters[head] = 1;
BitPatterns(root->right, characters, head +1);
}
if (isLeaf(root))
{
printf("'%c' : ", root->letter);
GetChars(characters, head);
}
}
void GetChars(int characters[], int n)
{
int i, counter = 0;
for (i = 0; i < n; ++i)
{
printf("%d", characters[i]);
counter++;
}
printf(" (%d * \n", counter);
}
int isLeaf(node* root)
{
return !(root->left) && !(root->right) ;
}
BitPatterns()
- person user007   schedule 12.12.2015return !(root->left) && !(root->right) ;
- person Finlandia_C   schedule 12.12.2015