文字列からJavaバイナリツリーを逆シリアル化する

Question

私の質問は、私が見つけた結果とは少し異なり、かなりの時間（初心者）でJavaを使用していないので、いくつかの説明が必要です。

基本的に、私の実装はほとんど正しいと私は確信しています、私はちょうど私がやっていたことにいくつかのバックストーリーを与えたいと思います。

だから、私の本当の問題は、私は文字列にバイナリツリーを直列化していることである：よう

 1 
    2  3 
4 5 

：

＃はちょうどヌルノードです

1 2 4 # # 5 # # 3 # # 

。

文字列から再構築しようとしているときに問題が発生します。私はかなりの時間をかけていくつかの掘削をしてきましたが、私はそれを過度に複雑化していると思います。

最初の要素は1なので、それをintに変更して、それを要素とするノードを作成します。次は2ですから、同じことをしてから4をしてください。次は＃なので、葉などがないので無視します。

次に、文字列の残りの部分前から既に読み込まれている）を再帰呼び出しに変換します。

要約すると、私の質問は基本的には「説明したように解析し、残りの文字列を再帰呼び出しに送るのが最も簡単な方法は何ですか？」文字列にツリーをシリアライズするとき

Answer 1

私は、括弧を使用します。

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

は木を記述します。

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

あなたが言うことができないので、あなただけの一人の子供を持っているいくつかのあいまいさがあります子供が左か右の子供であるかどうか。それを解析する際に、あなたは現在のノードの子を見ている左括弧に遭遇するたびに、そう

1(2(3 4) 5(# 6))  //6 is the right child 
1(2(3 4) 5(6 #))  //6 is the left child 

：その場合は、明示的な「ノー子」の文字を持つことができます。閉じ括弧に遭遇すると、あなたはそのノードの子どもたちが終わったことを知っているので、前のレベルに戻ることができます。

Answer 2

私は単なる文字列からScannerを作成し、hasInt()/nextInt()とnext()を使用

（空白文字で区切られた）のような文字列を読み込むための最も簡単な方法を知っておく必要があります。このような何か：

Scanner s = new Scanner(inputString); 
    s.setDelimiters("\\s+"); 
    ... 

    if (s.hasInt()) { 
     int = s.nextInt(); 
     // ... create a node and recurse twice to populate its children 
    } else if (s.next().equals("#")) { 
     // ... this is a null node 
    } else { 
     // ... syntax error 
    } 

Answer 3

使用しますが、文字列配列を持つmethod..considerこのJava ...

private static Tree<Integer> deserialize(Tree<Integer> tree, 
     String[] stringArray) { 
    // TODO Auto-generated method stub 
    if(index>=stringArray.length) 
     return null; 
    if(stringArray[index].equals("#")){ 
     index++; 
     return null; 

    } 
    int value=Integer.parseInt(stringArray[index]); 
    tree=new Tree<Integer>(value); 
    index++; 
    tree.left=deserialize(tree.left, stringArray); 
    tree.right=deserialize(tree.right, stringArray); 
    return tree; 
} 

Answer 4

は以下のバイナリをシリアル化し、バイナリツリーをデシリアライズするために私のコードです。 ツリーをプリオーダして文字列にダンプするだけです。 ここでは、Rahulのコードを使用しましたが、より簡潔になるように修正しました。

public class DeSerializationBinaryTree { 
    public static String serialize(Node root) { 
     if (root == null) 
      return "# "; 
     else { 
      return root.val + " " + serialize(root.left) + serialize(root.right); 
     } 
    } 

    public static Node deserialize(String res) { 
     String[] tokens = res.trim().split("\\s+"); 
     return deserialize(tokens); 
    } 

    static int index = 0; 

    private static Node deserialize(String[] stringArray) { 
     if (index >= stringArray.length) 
      return null; 
     if (stringArray[index].equals("#")) { 
      index++; 
      return null; 
     } 

     int value = Integer.parseInt(stringArray[index]); 
     Node tree = new Node(value); 
     index++; 
     tree.left = deserialize(stringArray); 
     tree.right = deserialize(stringArray); 
     return tree; 
    } 

    private static void inorder(Node root) { 
     if (root != null) { 
      inorder(root.left); 
      System.out.println(root.val); 
      inorder(root.right); 
     } 
    } 

    public static void main(String[] args) { 
     Node root = new Node(30); 
     Node node1 = new Node(10); 
     Node node2 = new Node(20); 
     Node node3 = new Node(50); 
     Node node4 = new Node(45); 
     Node node5 = new Node(35); 
     root.left = node1; 
     root.right = node2; 
     node1.left = node3; 
     node2.left = node4; 
     node2.right = node5; 

     System.out.println(serialize(root)); 
     Node node = deserialize("30 10 50 # # # 20 45 # # 35 # # "); 
     inorder(node); 
    } 
} 

Answer 5

private int index =0; 

/** 
* Saves this tree to a file. 
* @param filename the name of the file in which to save this tree; 
*    if null, uses default file name 
* @return <code>true</code> if successful save 
*   <code>false</code> otherwise 
* @throws IOException if unexpected IO error 
*/ 

public final boolean save(String filename) throws IOException{ 
    List<String> sbtList = new ArrayList<>(); 
    sbtList = preOrderSerialize(this, sbtList); 
    for (String sbtList1 : sbtList) { 
     System.out.println(sbtList1); 
    } 
    try{ 
     OutputStream file = new FileOutputStream (filename); 
     OutputStream buffer = new BufferedOutputStream(file); 
     output = new ObjectOutputStream(buffer); 
     output.writeObject(sbtList); 

    }catch (IOException e){ 
     System.err.println("Save not successful" + e); 
     return false; 
    } 
    finally { 
     output.close(); 
    } 
    return true; 
} 
/** 
* The pre-order traversal to serialize a binary tree 
* @param sbt 
* @return 
* @throws IOException 
*/ 
private List<String> preOrderSerialize(StringBinaryTree sbt, List<String> myList){ 
    if (sbt == null){ 
     myList.add("# "); 
    }   
    else{ 
     //sbt.add(this.value + ""); 
     myList.add(this.value + " "); 
     preOrderSerialize(sbt.leftNode, myList); 
     preOrderSerialize(sbt.rightNode, myList); 
    } 
    return myList; 
} 

/** 
* Restores this tree from a file. 
* @param filename the name of the file from which to restore the tree; 
* if <code>null</code>, uses default file name. 
* @return <code>true</code> if successful restore 
*   <code>false</code> otherwise 
* @throws IOException if there is an IO issue 
*/ 
public final boolean restore(String filename) throws IOException{ 
    try { 
     InputStream file = new FileInputStream (filename); 
     InputStream buffer = new BufferedInputStream (file); 
     input = new ObjectInputStream(buffer); 
     try{ 
      List <String> restoreSBT = (List<String>)input.readObject(); 
      StringBinaryTree root = deSerialize (restoreSBT); 
     } finally { 
      input.close(); 
     } 
    } 
    catch(IOException ex){ 
     System.err.println("File Not Restored" + ex); 
     return false; 
    } 
    catch (ClassNotFoundException e){ 
     System.err.println("Cannot read file: Class Not Found"+ e); 
     return false; 
    } 
    return true; 
} 

private StringBinaryTree deSerialize(List<String> restoreSBT){ 
    if (index >= restoreSBT.size()){ 
     return null; 
    } 
    if (restoreSBT.get(index).equals("#")){ 
     index ++; 
     return null; 
    } 
    StringBinaryTree root = new StringBinaryTree (restoreSBT.get(index)); 
    index++; 
    root.leftNode = deSerialize(restoreSBT); 
    root.rightNode = deSerialize(restoreSBT); 
    return root; 
}