二叉樹搜索和跟蹤

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

你說的是編碼霍夫曼輸出嗎？

您需要爲每個可能的輸入字符建立一個輸出代碼和長度表 - 不要在每個輸入字符上遍歷樹。