霍夫曼解碼樹的奇怪問題

Question

我早先對算法和實現提出了一個問題，但遇到了一個我無法解決的問題。

我能夠從文本文件採取的前綴，並讓他們進入一個載體，例如：

a 0 
b 100 
c 101 
d 11 

。

[0, a, 1, 0, 0, b, 1, 0, 1, c, 1, 1, d] 

所以我的代碼：

• 開始於根節點
• 迭代通過向量。如果我們得到一個0，取當前節點並讓它的指針指向一個新節點。如果我們得到1，則取當前節點並將其正確的指針指向新節點。如果是字母，則將該字符存儲到當前節點並從根開始。

（一個節點只包含一個值和具有左右指針）

void Foo:: build(vector<char> v) { 
    node* root = new node; 

    vector<char>:: iterator itr; 

    node* current = root; 
    cout << " *" << endl; 

    for(itr = v.begin(); itr != v.end(); itr++) { 
     cout << "(" << *itr << ")" << endl; 

     if (!isdigit(*itr)) { 
      current->value = *itr; 
      current = root; 
      cout << "*" << endl; 
     } 
     if (*itr == '0') { 
      cout << "<-" << endl; 
      current->left = new node; 
      current = current->left; 
     } 
     if (*itr == '1') { 
      cout << "->" << endl; 
      current->right = new node; 
      current = current->right; 
     } 
    } 

    nodeVector.push_back(*root); 
} 

。 如果你對cout好奇，*表示在根。因此對於'a'，它將從根*開始，遇到0並且轉到< - 向左放置該'節點'，然後從根*開始。我只是這樣做，看看它是否應該像是應該的那樣左右移動，而且看起來沒問題。

* 
(0) 
<- 
(a) 
* 
(1) 
-> 
(0) 
<- 
(0) 
<- 
(b) 
* 
(1) 
-> 
(0) 
<- 
(1) 
-> 
(c) 
* 
(1) 
-> 
(1) 
-> 
(d) 
* 

我遇到的問題很奇怪。唯一可以工作的字母是'a'和'd'。例如，root->left->value會給我'a'，root->right->right->value會給'd'，但root->right->left->right->value應該是'c'似乎並不像它曾經放在節點位置。當我嘗試獲取此值時，我的程序崩潰。當我嘗試解碼一串比特時，該消息是不正確的，因爲它只能執行'd'和'a'。這讓我懷疑這是樹的建築。任何建議將不勝感激！

Answer 1

6502是正確的。

每次你的迭代循環通過，你正在構建一個新路徑在樹上。左邊的那個很好，因爲它從來沒有被覆蓋（但是如果你有一個節點和兩個葉子，而不是自己的葉子，它也會失敗）。每次重新分配右側路徑並覆蓋創建的前一個節點，因此只有最後一個「d」條目可見。換句話說，創建了「b」和「c」，但每次創建新權限條目時，指向它們的指針都會丟失（覆蓋）。

正如6502指出的那樣，您需要檢查節點是否已經創建。但是你的代碼可能會失敗，因爲空指針沒有初始化爲0，因此代碼就像節點存在一樣繼續進行，但事實並非如此。對於每new node你必須如果你打算測試它們的內容，則初始化空指針left和right。例如：

if (*itr == '0') { 
    cout << "<-" << endl; 
    if (current->left) current = current->left; 
    else 
    { 
     current = (current->left = new node); 
     current->left = 0; // initialize your empty pointers! 
     current=>right = 0; // initialize your empty pointers! 
    } 
} 

注意，一個更好的地方放指針初始化是在new構造。

Answer 2

在分配新節點之前，您需要檢查之前是否已經分配了該路徑。例如

if (*itr == '0') { 
    cout << "<-" << endl; 
    if (current->left) current = current->left; 
        else current = (current->left = new node); 
}