树结构的存储

面试题：

怎样把一棵树存到文件中，然后读入恢复为原来的树。以二叉树为例。

在面试官提示了“把树变成一维”后我尝试用非递归遍历结果还是没写出来（真是自己作死，干嘛要用非递归呢）回到学校看了一下学数据结构时书上的代码。首先需要创建一棵树，书上是设置了一个不可能出现在树中的值作为结束符，用先根序列输入创建树。比如

可以用(-1,[1,2,4,-1,-1,5,-1,-1,3,-1,-1])来创建。恩，那就简单了，存储时只需要把这个序列和结束符存起来就行了呗。写完后才发现这题这么简单…… 数据结构教材上创建树是用cin读取输入，我改成了从数组读入。首先是节点的定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


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() + ")";
    }
}

然后是树的定义：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164


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");
    }
}

运行结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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))

保存的文件内容是：

1
2
3
4
5
6
7
8
9


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变量保存泛型参数的类型，在恢复时检查是否类型匹配。参考：

#java #二叉树 #树 #泛型

3 comments