Использование дерева Хаффмана для декодирования двоичного текста

Question

Фрагмент ниже не возвращает правильный текст.Код получает указатель на корневой узел дерева кода Хаффмана и двоичный текст, который затем преобразует.Тем не менее, каждый раз, когда он возвращает одну букву повторяется.

string decode(Node *root, string code) {
    string d = ""; char c; Node *node = root;
    for (int i = 0; i < code.size(); i++) {
        node = (code[i] == '0') ? node->left_child : node->right_child;
        if ((c = node->value) < 128) {
            d += c;
            node = root;
        }
    }
    return d;
}

Код для объекта Node:

class Node {
public:
  Node(int i, Node *l = nullptr, Node *r = nullptr) {
      value = i;
      left_child = l;
      right_child = r;
  }
  int value;
  Node *left_child;
  Node *right_child;
};

Код для построения дерева:

Node* buildTree(vector<int> in, vector<int> post, int in_left, int in_right, int *post_index) {
    Node *node = new Node(post[*post_index]);
    (*post_index)--;

    if (in_left == in_right) {
        return node;
    }

    int in_index;
    for (int i = in_left; i <= in_right; i++) {
        if (in[i] == node->value) {
            in_index = i;
            break;
        }
    }

    node->right_child = buildTree(in, post, in_index + 1, in_right, post_index);
    node->left_child = buildTree(in, post, in_left, in_index - 1, post_index);

    return node;
}

Пример дерева:

        130
       /   \
     129    65
    /   \
  66     128
        /   \
      76     77 

Пример ввода / вывода: ввод: 101010010111 вывод: A�A�A��A�AAA

Символы ромба - это числа больше 128.

Answer 1

Вы помещаете значение в char, которое для большинства компиляторов C ++ подписано.Но не все - независимо от того, является ли char подписанным или неподписанным, определяется реализацией.Число знаков со знаком находится в диапазоне от –128 до 127, поэтому всегда меньше 128. (Ваш компилятор должен был предупредить вас об этом.)

Вам необходимо использовать int c;вместо char c; в decode() и сделайте d += (char)c;.Тогда ваш первый фрагмент кода будет правильно возвращать ALABAMA.

Кстати, в decode() должна быть проверка ошибок, подтверждающая, что вы выходите из цикла с node, равным root.В противном случае были предоставлены некоторые биты, которые заканчивались в середине кода и поэтому не были декодированы в символ.