保存一個二進制樹到一個文件

Question

我有一個非平衡的（不是二進制搜索）二叉樹 需要incode（和後來解碼）到txt文件。 如何以有效的方式做到這一點？

我發現這個link 其中談到了類似的（相同）的問題，但對我來說

Answer 1

請看this on LeetCode很明顯。

我喜歡這個解決方案，因爲它相對高效並且生成光輸出文件。

假設你有樹這樣的：

_30_ 
/ \  
    10 20 
/ /\ 
50 45 35 

該解決方案可以讓你把它序列化到這樣的輸出文本文件：

30 10 50 # # # 20 45 # # 35 # # 

要做到這一點，足以進行簡單預先遍歷樹：

void writeBinaryTree(BinaryTree *p, ostream &out) { 
    if (!p) { 
    out << "# "; 
    } else { 
    out << p->data << " "; 
    writeBinaryTree(p->left, out); 
    writeBinaryTree(p->right, out); 
    } 
} 

正如你所看到的，一個# sym bol用來表示空節點。

反序列化這個字符串變成一棵樹，你可以使用：

void readBinaryTree(BinaryTree *&p, ifstream &fin) { 
    int token; 
    bool isNumber; 
    if (!readNextToken(token, fin, isNumber)) 
    return; 
    if (isNumber) { 
    p = new BinaryTree(token); 
    readBinaryTree(p->left, fin); 
    readBinaryTree(p->right, fin); 
    } 
} 

正如我前面所說，這種方法產生的二叉樹的輕量級表示。

當然，它有一個嚴重的缺點：它需要一個符號來表示空節點。

如果樹的節點是可以包含此符號本身的字符串，則可能會導致潛在問題。