c++ - 二叉树搜索和跟踪

Question

我有一个包含整数和字符的节点二叉树。我正在研究霍夫曼编码，我想获得节点的二进制表示。'0' 被附加到每个左分支的字符串中，'1' 被附加到每个右分支。

我正在考虑搜索 char 但跟踪其分支，如果它不在左侧节点中，请删除附加到字符串的最后一个 '0' 并返回并检查右侧。这看起来非常有任务。我还有其他方法可以跟踪节点吗？

编辑：我必须使用二叉树。

Answer 1

您是在谈论对霍夫曼输出进行编码吗？

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

Answer 2

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

• 维基百科
• C++ 参考

您可以通过以下方式使用堆栈来跟踪您在树中的位置：

• 路径 =std::stack<int>
• 向上移动到父级 ==pop()
• 移动到左孩子 ==push(0)
• 移动到右孩子 ==push(1)

编辑：

您可能希望实际使用std::vector<int>with push_backandpop_back来代替。它仍然表现得像一个堆栈，但如果你使用向量，你可以在最后得到整个 0 和 1 的列表。