分类
代码

树结构的存储

面试题:

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

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

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

运行结果:

二叉树的存储-demo-效果
二叉树的存储-demo-效果

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


保存的文件内容是:

二叉树的存储-demo-保存的文件的内容
二叉树的存储-demo-保存的文件的内容

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

参考:


“树结构的存储”上的3条回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

[/鼓掌] [/难过] [/调皮] [/白眼] [/疑问] [/流泪] [/流汗] [/撇嘴] [/抠鼻] [/惊讶] [/微笑] [/得意] [/大兵] [/坏笑] [/呲牙] [/吓到] [/可爱] [/发怒] [/发呆] [/偷笑] [/亲亲]