c - 从二叉搜索树构建哈夫曼树

Question

我正在尝试用二叉搜索树构建霍夫曼树。遗憾的是，我的代码崩溃了(段错误(核心已转储))。

struct 是这样定义的:

struct Node
{
  unsigned char m_ch;
  int m_freq;
  struct Node *m_ls,*m_rs;
  struct Node *m_hls,*m_hrs;
};

delMin 被传递一个指向二叉搜索树的双指针，并从中删除最左边的叶子，除非它到达具有 m_ch==0 的节点并返回删除的节点

我找不到我的错误

struct Node *delMin(struct Node **root)
{
    struct Node *current = *root;
    struct Node *b4Current;

    if (current == NULL)
        return NULL;

    while (current->m_ls != NULL)
    {
        if (current->m_ch == 0)
            break;

        b4Current = current;
        current = current->m_ls;
    }

    if (current->m_ch == 0)
        b4Current->m_ls = NULL;
    else
    {
        if (b4Current == NULL)
            *root = current->m_rs;
        else
            b4Current->m_ls = current->m_rs;
    }

    return current;
}


struct Node *huffman(struct Node *root)
{
    struct Node *left;
    struct Node *right;
    struct Node *tempRoot;
    struct Node *huffmanTree;

    while (root->m_ch != 0)
    {
        left = delMin(&root);
        right = delMin(&root);
        tempRoot = createNode((left->m_freq) + (right->m_freq), 0);
        tempRoot->m_hls = left;
        tempRoot->m_hrs = right;
        insertTree(&root, tempRoot);
    }

    huffmanTree = tempRoot;
    return huffmanTree;
}

编辑:为 Huffman 调用的 insertTree 函数添加了代码

void insertTree(struct Node **root,struct Node *n)
{
  if (!*root)
  {
    *root=n;
    return;
  }
  if(n->m_freq<(*root)->m_freq)
  {
    insertTree(&((*root)->m_ls),n);
  }
  else
  {
    insertTree(&((*root)->m_rs),n);
  }
}

Answer 1

在delMin这段代码中

if (current->m_ch == 0)
    b4Current->m_ls = NULL;
else
{
    if (b4Current == NULL)
        *root = current->m_rs;
    else
        b4Current->m_ls = current->m_rs;
}

不能保证 b4Current 不为 NULL。

考虑根节点有 m_ch == 0 和 m_ls == NULL 的情况。您将采用 if 分支并取消引用 b4Current。

您需要使用 NULL 初始化 b4Current 并在取消引用之前检查它。

在 delMin 中初始化 current = *root 或在 中取消引用之前，您还需要确保 root 本身是非空的霍夫曼

这些都应该初始化为NULL

struct Node *left;
struct Node *right;
struct Node *tempRoot;
struct Node *huffmanTree;

并且有可能永远不会进入 while 循环，让 tempRoot 未设置，当您返回它的值时，会在 huffman 的调用者中导致潜在的 segFault。