從二分搜索樹構建哈夫曼樹

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

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不爲空。

考慮根節點有m_ch == 0和m_ls == NULL的情況。您將採取if分支和解除引用b4Current。

您需要初始化b4Current與NULL並在任何解除引用之前檢查它。

你還需要確保root本身是delMin初始化current = *root或間接引用它huffman

這些都應該被初始化爲NULL

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

，這是可能的，再之前非空，永遠不會進入while循環，並且在您返回其值時，將tempRoot取消設置，導致huffman調用方中潛在的segFault。