面试题：
怎样把一棵树存到文件中，然后读入恢复为原来的树。以二叉树为例。
在面试官提示了“把树变成一维”后我尝试用非递归遍历结果还是没写出来（真是自己作死，干嘛要用非递归呢）
回到学校看了一下学数据结构时书上的代码。首先需要创建一棵树，书上是设置了一个不可能出现在树中的值作为结束符，用先根序列输入创建树。比如
1 / \ 2 3 / \ 4 5
可以用(-1,[1,2,4,-1,-1,5,-1,-1,3,-1,-1])来创建。
恩，那就简单了，存储时只需要把这个序列和结束符存起来就行了呗。写完后才发现这题这么简单……
数据结构教材上创建树是用cin读取输入，我改成了从数组读入。
首先是节点的定义：
package com.youthlin.treesave;
/**
* Created by lin on 16-4-16.
*/
public class BinTreeNode<T> {
private BinTreeNode<T> left, right;
T data;
public BinTreeNode<T> getLeft() {
return left;
}
public void setLeft(BinTreeNode<T> left) {
this.left = left;
}
public BinTreeNode<T> getRight() {
return right;
}
public void setRight(BinTreeNode<T> right) {
this.right = right;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinTreeNode() {
this(null, null, null);
}
public BinTreeNode(T data) {
this(data, null, null);
}
public BinTreeNode(T data, BinTreeNode<T> left, BinTreeNode<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
@Override
public boolean equals(Object o) {
if (o instanceof BinTreeNode) {
BinTreeNode another = (BinTreeNode) o;
if (this.data.equals(another.data)) {
return true;
}
}
return false;
}
@Override
public String toString() {
return super.toString() + "(" + data.toString() + ")";
}
}
然后是树的定义：
package com.youthlin.treesave;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created by lin on 16-4-16.
*/
public class BinTree<T> {
private BinTreeNode<T> root;
private T stop;
private int i = 0;
private List<T> list;
private Class<T> clazz;
public List<T> getList() {
return list;
}
public BinTreeNode<T> getRoot() {
return root;
}
public void setRoot(BinTreeNode<T> root) {
this.root = root;
}
public T getStop() {
return stop;
}
public void setStop(T stop) {
this.stop = stop;
clazz = (Class<T>) (stop).getClass();
//System.out.println(clazz.getName());
}
/*根据前序创建二叉树(-1,[1,2,4,-1,-1,5,-1,-1,3,-1,-1])
* <pre>
* 1
* / \
* 2 3
* / \
* 4 5
* </pre>
* */
public void buildTree(T stop, T[] dataArray) {
setStop(stop);
list = new ArrayList<>(Arrays.asList(dataArray));
i = 0;
root = create(dataArray);
}
private BinTreeNode<T> create(T[] dataArray) {
BinTreeNode<T> node;
int index = i++;
if (dataArray[index].equals(stop)) return null;
node = new BinTreeNode<>(dataArray[index]);
node.setLeft(create(dataArray));
node.setRight(create(dataArray));
return node;
}
public void preOrder(BinTreeNode<T> node) {
if (node == null) return;
System.out.print(node.data + " ");
preOrder(node.getLeft());
preOrder(node.getRight());
}
public void inOrder(BinTreeNode<T> node) {
if (node != null) {
inOrder(node.getLeft());
System.out.print(node.getData() + " ");
inOrder(node.getRight());
}
}
public void postOrder(BinTreeNode<T> node) {
if (node != null) {
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.print(node.getData() + " ");
}
}
public boolean writeToFile(File file) throws IOException {
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(clazz.getName());
oos.writeObject(stop);
oos.writeObject(list.toArray());
return true;
}
public boolean buildTreeFromFile(File file) throws IOException, ClassNotFoundException, ClassCastException {
ObjectInputStream ois = new ObjectInputStream(new FileInputStream(file));
String name = (String) ois.readObject();
if (!name.equals(clazz.getName())) {
throw new ClassCastException("The file which saved is another type of tree!");
}
T s = (T) ois.readObject();
buildTree(s, (T[]) ois.readObject());
return true;
}
// BinTree() {
//
// }
BinTree(T stop) {
//java获取泛型参数类型 [问题点数：20分]
//http://bbs.csdn.net/topics/390696766/#post-396622043
//在构造时保存泛型里参数T的类型
setStop(stop);
}
BinTree(T stop, T[] data) {
buildTree(stop, data);
}
public static void main(String[] args) {
BinTree<String> tree = new BinTree<>("0",
new String[]{"aaa", "bbb", "ddd", "0", "0", "e", "0", "0", "c", "0", "0"});
System.out.println("PreOrder");
tree.preOrder(tree.getRoot());
System.out.println("\nInOrder");
tree.inOrder(tree.getRoot());
System.out.println("\nPostOrder");
tree.postOrder(tree.getRoot());
System.out.println();
File file = new File("save.tree");
try {
tree.writeToFile(file);
} catch (IOException e) {
e.printStackTrace();
}
BinTree<Integer> tree1 = new BinTree<>(-1);
try {
tree1.buildTreeFromFile(file);
} catch (ClassCastException e) {
e.printStackTrace();
} catch (ClassNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
System.out.println("new Tree:");
tree1.preOrder(tree1.getRoot());
System.out.println();
tree1.inOrder(tree1.getRoot());
System.out.println();
tree1.postOrder(tree1.getRoot());
System.out.println();
BinTree<BinTreeNode<Character>> t = new BinTree<>(new BinTreeNode<>('z'),
new BinTreeNode[]{new BinTreeNode<>('a'), new BinTreeNode<>('z'), new BinTreeNode<>('z')});
t.inOrder(t.getRoot());
System.out.println("\n" + t.getRoot() + "\n");
}
}
运行结果：
PreOrder aaa bbb ddd e c InOrder ddd bbb e aaa c PostOrder ddd e bbb c aaa java.lang.ClassCastException: The file which saved is another type of tree! at com.youthlin.treesave.BinTree.buildTreeFromFile(BinTree.java:102) at com.youthlin.treesave.BinTree.main(BinTree.java:144) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:483) at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144) new Tree: com.youthlin.treesave.BinTreeNode@60e53b93(a) com.youthlin.treesave.BinTreeNode@5e2de80c(com.youthlin.treesave.BinTreeNode@60e53b93(a))
保存的文件内容是：
00000000 ac ed 00 05 74 00 10 6a 61 76 61 2e 6c 61 6e 67 |....t..java.lang| 00000010 2e 53 74 72 69 6e 67 74 00 01 30 75 72 00 13 5b |.Stringt..0ur..[| 00000020 4c 6a 61 76 61 2e 6c 61 6e 67 2e 4f 62 6a 65 63 |Ljava.lang.Objec| 00000030 74 3b 90 ce 58 9f 10 73 29 6c 02 00 00 78 70 00 |t;..X..s)l...xp.| 00000040 00 00 0b 74 00 03 61 61 61 74 00 03 62 62 62 74 |...t..aaat..bbbt| 00000050 00 03 64 64 64 71 00 7e 00 01 71 00 7e 00 01 74 |..dddq.~..q.~..t| 00000060 00 01 65 71 00 7e 00 01 71 00 7e 00 01 74 00 01 |..eq.~..q.~..t..| 00000070 63 71 00 7e 00 01 71 00 7e 00 01 |cq.~..q.~..| 0000007b
原来没有clazz那个变量保存泛型参数的类型，这样的话，保存的任意类型都可以读入到任意参数类型的树中，因为运行时泛型都擦除为了Object。所以增加了一个clazz变量保存泛型参数的类型，在恢复时检查是否类型匹配。
参考：
声明
- 本作品采用署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。除非特别注明， 霖博客文章均为原创。
- 转载请保留本文(《树结构的存储》)链接地址： https://youthlin.com/?p=1220
- 订阅本站：https://youthlin.com/feed/
“树结构的存储”上的3条回复
不明觉厉
(-1,[1,2,4,-1,-1,5,-1,-1,3,-1,-1])
这这。。。什么遍历方法？为什么成这串数字？这是关键技术，貌似没讲。。
沙发……
完全不懂……
Btree已经搞得我快崩溃了……