二叉树搜索和跟踪

Question

我有一个包含整数和char的节点的二叉树。我正在研究Huffman Coding，我想获得节点的二进制表示。每个左分支的字符串附加'0'，每个右分支附加'1'。

我正在寻找一个字符但追踪它的分支，如果它不在左边的节点中，请删除附加到字符串的最后'0'并返回并检查是否正确。 这看起来很繁重。有没有另外一种方式让我跟踪节点？编辑： 我不得不使用二叉树。

Answer 1

听起来像一个堆栈数据结构：

• Wikipedia
• C++ reference

你跟踪你在树枝上，通过以这种方式使用的堆栈：

• path = std::stack<int>
• 拉升父== pop()
• 移动到左子== push(0)
• 右移孩子== push(1)

编辑：

您可能需要实际使用std::vector<int>与改为push_back和pop_back。它仍然像堆栈一样，但如果使用矢量，则可以在最后得到整个0和1的列表。

Answer 2

你说的是编码霍夫曼输出吗？

您需要为每个可能的输入字符建立一个输出代码和长度表 - 不要在每个输入字符上遍历树。