編碼哈夫曼二叉樹

Question

我正在嘗試編寫一個函數，它需要一個霍夫曼樹和一個字符。然後它應該對角色進行編碼並將其返回。

至今代碼：

string encode(NodePtr root, char letter) 
{ 
    string encode_str; //a string which will store the encoded string 
    NodePtr tempNode = root; //Initialize a new Huffman to be used in this function 
    NodePtr tempLeft = root->left; 
    NodePtr tempRight = root->right; 

     //A while loop that goes on until we find the letter we want 
     while((tempLeft->letter != letter) || (tempRight->letter != letter)) 
     { 
     if((tempRight->is_leaf()) && (tempRight->letter == letter)) //check if is leaf and is letter 
     { 
       encode_str = encode_str + '1'; 
     } 
     else if ((tempLeft->is_leaf()) && (tempLeft->letter == letter)) //check if is leaf and is letter 
     { 
      encode_str = encode_str + '0'; 
     } 
     else if ((tempRight->is_leaf()) && (tempRight->letter != letter)) //check if is leaf and is NOT letter 
     { 
      tempNode = root->left; 
      tempLeft = tempNode->left; 
      tempRight = tempNode->right; 
      encode_str = encode_str + '0'; 
     } 
      else if ((tempLeft->is_leaf()) && (tempLeft->letter != letter)) //check if is leaf and is NOT letter 
     { 
      tempNode = root->right; 
      tempLeft = tempNode->left; 
      tempRight = tempNode->right; 
      encode_str = encode_str + '1'; 
     } 
     }  

    return encode_str; 
} 

這至今還沒有工作，調試並沒有幫助我滿意。任何人都可以幫助我，或者至少告訴我我的想法是否正確。

Answer 1

如果沒有tempLeft也不tempRight是葉，你有一個無限循環：

while((tempLeft->letter != letter) || (tempRight->letter != letter)) 
    { 
     if((tempRight->is_leaf()) && 
      (tempRight->letter == letter)) 
     { 
      // no 
     } 
     else if ((tempLeft->is_leaf()) && 
       (tempLeft->letter == letter)) 
     { 
      // no 
     } 
     else if ((tempRight->is_leaf()) && 
       (tempRight->letter != letter)) 
     { 
      // no 
     } 
     else if ((tempLeft->is_leaf()) && 
       (tempLeft->letter != letter)) 
     { 
      // no 
     } 
    } 

必須有你想要的情況下做的節點在哪裏並不令人不滿意。也許遞歸？

（根據註釋）您可能正在使用哈夫曼樹的變體，您可以在其中確保每個節點都是葉子或有一個葉子。如果你可以保證這一點，那麼上面的內容並不重要（如果它發生，拋出異常是很好的）。然而，現實世界的霍夫曼樹沒有這個屬性。

---

當一個孩子是葉，另一種是不是你的目標字母，您嘗試設置一個新的tempNode，tempLeft和tempRight周邊循環的下圍棋。

else if ((tempRight->is_leaf()) && 
      (tempRight->letter != letter)) 
    { 
     tempNode = root->left; 
     tempLeft = tempNode->left; 
     tempRight = tempNode->right; 
     encode_str = encode_str + '0'; 
    } 

但是，因爲你永遠不修改root，tempNode = root->left將始終設置tempNode同一節點。

您可能想要tempNode = tempNode->left。

---

爲了避免碼重複，你可以移動

tempLeft = tempNode->left; 
tempRight = tempNode->right; 

...是這種情況發生在while()循環的第一件事。

---

你說，調試並沒有幫助。你真的在調試器中運行它嗎？

編寫一個單元測試，設置你的樹;驗證樹實際上包含你打算的內容;並用一個字母調用該函數。決定你認爲執行應該如何進行。現在在調試器中運行代碼，逐步完成它。當它停止了你認爲應該做的事時，你就能夠推斷出原因。

---

實現霍夫曼編碼的一種常見方式是有葉節點的數組，這樣你就可以通過簡單的數組訪問到達節點：

NodePtr nodeA = nodes[0]; 

...並且在每個節點中都有一個指向父節點的指針，並且有一個字段指示它是左側還是右側的子節點，以便您可以輕鬆遍歷樹，從葉到樹，構建代碼（反向）：

string code = ""; 
    NodePtr node = nodeA; 
    while(node->parent != NULL) { 
     code = node->code + code; 
     node = node->parent; 
    }