Декодирование дерева Хаффмана

Question

Я пытаюсь расшифровать дерево Хаффмана формы:

001A1C01E01B1D 

Я использую реализацию здесь: Efficient way of storing Huffman tree закодировать дерево в форме выше и декодировать его, а также ,

Это моя реализация этого:

HuffmanNode* HuffmanTree::decodeTree(string tree, int idx) { 
    cout << idx << endl; 
    if (tree[idx] == '1') { 
     idx += 2; 
     return new HuffmanNode(tree[idx - 1]); 
    } 
    else { 
     if (idx != tree.length() - 1) { 
      idx++; 
      HuffmanNode* leftChild = decodeTree(tree, idx); 
      idx++; 
      HuffmanNode* rightChild = decodeTree(tree, idx); 
      return new HuffmanNode(leftChild, rightChild); 
     } 
     else 
      return new HuffmanNode(tree[idx]); 
    } 
} 

Я получаю нарушение прав доступа, написание местоположение, когда функция раскручивается (On "вернуть новый HuffmanNode (дерево [IDX - 1]);"), и я надеюсь, что окончательное возвращение будет корнем дерева, но при дальнейшей проверке это, похоже, не так. Может ли кто-нибудь дать мне несколько указателей? (Каламбур не предназначен)

Answer 1

Проблема с вашим кодом в том, что idx не изменяется внутри рекурсивных трасс. Передайте его в функцию, как int &: HuffmanNode* HuffmanTree::decodeTree(string tree, int &idx)

Существует и еще одна ошибка в коде, что делает его сегментации: вместо

if (tree[idx] == '1') { 
    idx += 2; 
    return new HuffmanNode(tree[idx - 1]); 
} 

вы должны иметь

if (tree[idx] == '1') { 
    ++idx; 
    return new HuffmanNode(tree[idx]); 
} 

Другой 1 является добавляется к индексу во втором блоке:

idx++; 
HuffmanNode* leftChild = decodeTree(tree, idx); 
idx++; 
HuffmanNode* rightChild = decodeTree(tree, idx); 

Также подумайте о том, чтобы сделать что-то похожее на пример, с которым вы связались: передать ссылку на итератор строки (или istringstream или какой-либо другой поток) и не передавать индекс: HuffmanNode* HuffmanTree::decodeTree(std::string::const_iterator &tree).

Кроме того, вам не нужно делать проверки, такие как if (idx != tree.length() - 1), если дерево хорошо сформировано. Вы все еще можете сделать это в начале функции, чтобы проверить наличие ошибок на вашем входе, а также проверить, что текущий символ равен '0' или '1'.