0

我正在开发一个 c++ 程序和我的团队，我无法弄清楚如何使用 inOrder 遍历生成前缀代码的逻辑。我们已经构建了 PrefixCode Tree，我们希望从中生成代码。

由于我们遇到了逻辑问题，我不知道是否需要提供任何代码。如果你需要任何让我知道。

谢谢。

4

1 回答 1

1

正如评论的那样，我不确定是否理解。买我试试...

首先，我假设您已经正确构建了树。

其次，每个叶子都包含一个要编码的符号。每个符号的代码由从根到叶的路径定义。最初，当您位于根目录时，代码是空的。如果您向左走，则将 a 连接0到代码。对称地，如果你向右走，那么你连接1。

第三，我假设您想要对列表<symbol, code>。symbol是一个字符，code是一个包含前缀代码的字符串。结果是由树表示的所有符号及其代码的列表。

现在，生成该列表的算法将使用堆栈来存储从根到当前节点的前缀。每次到达叶子时，代码都会进入堆栈，但会反转。这样的算法可以如下：

void codes(Node * root, stack<char> & s)
{
  if (is_leaf(root))
    {
      auto symbol = // symbol stored in the node
      string code = // the reversed stack content; that is the code of current leaf
      cout << symbol << " = " << code << endl;
    }

  s.push('0');
  codes(LLINK(root), s);
  s.pop();

  s.push('1');
  codes(RLINK(root), s);
  s.pop();
}

我建议使用堆栈，因为它是用于存储从根到节点的部分路径的“自然”数据结构。但是，也许它会更好vector<char>。在这种情况下，您应该替换push()bypush_back()和pop()by pop_back()。但优点是您可以使用反向迭代器构建代码。

cout ...此外，您可以使用列表或向量来代替指令，并在其中插入一对。之后，如果您愿意，可以对其进行排序。或者，您可以使用“自然排序”的数据结构，例如二叉搜索树，避免排序。如果您感兴趣的话，所有这一切当然是产生一个按符号排序的输出。

我希望它有所帮助

于 2015-10-23T02:05:59.363 回答