二叉树在构建树时丢失节点
Binary tree is losing nodes while building the tree
我已经使用下面的代码构建了一个二叉树(霍夫曼树),它接受一个按升序排序的链表,但是当它完成时 运行 它会打印位模式和一些节点应该在树上的不是。
代码本质上:
设置父节点指向两个最低节点
分配父节点的内部频率
将列表的开头指向现在位于其原位置的节点 2(以避免重复使用节点)
将新的父节点插入树中的正确位置
获取树的长度
打印列表中剩余的所有节点
迭代直到剩下一个节点(即根节点)。
关于其 'losing' 个节点的任何想法?
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) ;
}
好的!调试起来很困难。但是,我想我已经找到了问题所在。问题出在 while
循环中,您可以在其中找到列表的长度,留待处理。由于 while
循环中的条件是 temp->next != NULL
,因此,考虑您的列表的大小为 2,类似于这样的 ::
3 --> 4 --> NULL (Numbers represent the sum of frequencies of some nodes)
list->start
指向 3。您将测量此列表的长度为 1 而不是 2,因为您正在检查 temp->next != NULL
。
因此你错过了列表中关键的第二个节点,而你 运行 BitPatterns()
只在第一个节点上,你错过了几个节点。
一个可能的解决方案是在函数的开头插入一个while
循环来测量一次长度,并且可以在[=11的每个连续迭代中递减1 =] 循环,在这里你组合两个节点,因为你总是删除两个节点并向列表中添加一个节点,你只需要将 length
减 1。这也会节省很多额外的计算,你每次都在列表的末尾做计算列表的长度。
像这样::
temp = list->start;
while(temp != NULL) {
length++;
temp = temp->next;
}
编辑::
此外,我在您的代码中看到了另一个逻辑错误::
认为初始列表是这样的::
1 --> 2 --> 4 --> 5 --> NULL
将前两个节点组合起来,让该节点暂时称为 A (with freq = 3)
,list_start
指向 4
。因此,当您在列表中插入节点时,看起来像这样 ::
4 --> A --> 5 --> NULL
虽然列表看起来像这样::
A --> 4 --> 5
这不会影响代码的运行,但可能会导致一些未优化的霍夫曼代码结果。
我已经使用下面的代码构建了一个二叉树(霍夫曼树),它接受一个按升序排序的链表,但是当它完成时 运行 它会打印位模式和一些节点应该在树上的不是。
代码本质上:
设置父节点指向两个最低节点
分配父节点的内部频率
将列表的开头指向现在位于其原位置的节点 2(以避免重复使用节点)
将新的父节点插入树中的正确位置
获取树的长度
打印列表中剩余的所有节点
迭代直到剩下一个节点(即根节点)。
关于其 'losing' 个节点的任何想法?
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) ;
}
好的!调试起来很困难。但是,我想我已经找到了问题所在。问题出在 while
循环中,您可以在其中找到列表的长度,留待处理。由于 while
循环中的条件是 temp->next != NULL
,因此,考虑您的列表的大小为 2,类似于这样的 ::
3 --> 4 --> NULL (Numbers represent the sum of frequencies of some nodes)
list->start
指向 3。您将测量此列表的长度为 1 而不是 2,因为您正在检查 temp->next != NULL
。
因此你错过了列表中关键的第二个节点,而你 运行 BitPatterns()
只在第一个节点上,你错过了几个节点。
一个可能的解决方案是在函数的开头插入一个while
循环来测量一次长度,并且可以在[=11的每个连续迭代中递减1 =] 循环,在这里你组合两个节点,因为你总是删除两个节点并向列表中添加一个节点,你只需要将 length
减 1。这也会节省很多额外的计算,你每次都在列表的末尾做计算列表的长度。
像这样::
temp = list->start;
while(temp != NULL) {
length++;
temp = temp->next;
}
编辑:: 此外,我在您的代码中看到了另一个逻辑错误::
认为初始列表是这样的::
1 --> 2 --> 4 --> 5 --> NULL
将前两个节点组合起来,让该节点暂时称为 A (with freq = 3)
,list_start
指向 4
。因此,当您在列表中插入节点时,看起来像这样 ::
4 --> A --> 5 --> NULL
虽然列表看起来像这样::
A --> 4 --> 5
这不会影响代码的运行,但可能会导致一些未优化的霍夫曼代码结果。