序列化BST樹

Question

我試圖序列化一個BST，以便它可以被另一個程序讀入。輸出有節點，其次是所有的孩子和他們的孩子的孩子等。如果沒有額外的孩子，隨後括號括起來。

我的方法輸出

(4 (2 (1)) (3)) (6 (5)) (7)) 




public String serializePrefix(){ 
     StringBuilder str = new StringBuilder(); 
     serializePrefix (root, str, " "); 
     return str.toString(); 
    } 


    private void serializePrefix (Node t, StringBuilder str, String sep){ 
     int ID = 1; 
     if (t == null) 
      str.append(")"); 
     else{ 


       str.append("(" + t.data.toString()); 
       str.append(sep); 
       serializePrefix (t.left, str, sep); 
       serializePrefix (t.right, str, sep); 

     } 

     ID++; 

    } 

我需要出去放是

(4 (2 (1) (3)) (6 (5) (7)))) 

  4 
    /\ 
     2 6 
    /\/\ 
    1 3 5 7 

Answer 1

你的第一個問題的情況是，當你發現一個這將創建樹葉：你所有的右括號（) ）加倍，因爲你試圖向左和向右的鏈接前進，但你會發現null s，這會觸發代碼中的結束括號。

private void serializePrefix (Node t, StringBuilder str, String sep){ 
    int ID = 1; 
    if (t == null) 
     //ERROR: if empty node found, apply close bracket 
     str.append(")"); 
    else{ 
     str.append("(" + t.data.toString()); 
     str.append(sep); 

     //this is the problem part, for example for node number 1: 
     serializePrefix (t.left, str, sep); //this writes ")" first time 
     serializePrefix (t.right, str, sep); //this writes ")" second time 

    } 

    ID++; 

} 

的第二個問題是，在最後一個分支，你的括號不會得到適當的，因爲它的步驟關閉，因爲當你的算法「退後」去根，它不關閉打開的支架退一萬個......

修復建議：

private void serializePrefix (Node t, StringBuilder str, String sep){ 
    int ID = 1; 
    if (t == null) 
     // do nothing! 
     // str.append(")"); 
    else{ 
     str.append("(" + t.data.toString()); 
     str.append(sep); 

     //this is the problem part, for example for node number 1: 
     serializePrefix (t.left, str, sep); //this writes ")" first time 
     serializePrefix (t.right, str, sep); //this writes ")" second time 

     //close opened bracket 
     str.append(")"); 
    } 

    ID++; 

} 

（順便說一下，這是試圖關閉你從你打開它的可視距離開一般建議...這有助於控制泄漏來源如數據庫連接等）