序列化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++; 

} 

（顺便说一下，这是试图关闭你从你打开它的可视距离开一般建议...这有助于控制泄漏来源如数据库连接等）