我的問題與我發現的結果有點不同，並且我在相當長一段時間（新手）中沒有使用過Java，所以我需要一些說明。從字符串反序列化Java二進制樹
基本上，我很確定我的實現大部分是正確的，我只是想給我一些背後的故事，我正在做什麼。
所以，我的真正的問題是，我已經序列化二叉樹爲字符串：
1
2 3
4 5
爲：
1 2 4 # # 5 # # 3 # #
其中＃只是空節點。
我試圖從字符串重建它時出現問題。我已經做了幾個小時的挖掘工作，但我認爲我已經過分了。我只需要知道讀取字符串的最簡單方式（用空格分隔）：
第一個元素是1，因此我們將其更改爲int並將其作爲元素創建一個節點。接下來是2，所以相同，然後4.接下來是一個＃，所以我們忽略，因爲沒有葉等
然後，我需要發送字符串的其餘部分（減去什麼已經從前面讀取）轉換爲遞歸調用。
總之，我的問題基本上是「按照描述解析它，最簡單的方法是什麼，並將剩餘的字符串發送到遞歸調用？」
序列化樹的字符串時，我會用括號：
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
所以，當你遇到你看當前節點的孩子的左括號：在這種情況下，你可以有一個明確的「無子」字。當你遇到一個右括號時，你知道你已經完成了該節點的子節點，所以你可以回到以前的級別。
我只需要知道讀字符串作爲這樣的（由空格分隔）
從字符串一個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
}
使用這個Java method..consider你有字符串數組...
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;
}
下面是我的代碼序列化的二進制和反序列化二叉樹。 我們只是將預先訂購的樹轉儲到一個字符串中。 在這裏，我使用Rahul的代碼，但我修改它更簡潔。如果你作爲OP在他的問題描述解釋它
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);
}
}
這是什麼點在這裏 –
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;
}
代碼只答案不允許在Stackoverflow –
現有的語法是明確的。它基本上是一個預先序列深度優先遍歷，每遇到一個空值就輸出'＃'。 –
@StephenC是的，如果你有一個指定的遍歷順序，那麼沒有歧義。 –