博客

Java实现二叉树的序列化与反序列化

数据结构

class BinTree {
    String value;
    BinTree left;
    BinTree right;
    BinTree(String value) {
        this.value = value;
    }
}

二叉树的序列化

二叉树的序列化是指将二叉树的遍历结果按照一定的格式保存为字符串，使得程序在内存中生成的二叉树得以保存，从而实现二叉树的持久化的过程。

二叉树可以通过前序，中序，后序，层次等遍历方式进行遍历输出序列化字符串，结果字符串规定“/”表示一个结点值的结束，以“#/”表示空结点。本文以前序遍历的方式实现序列化。

    public static String preSerialization(BinTree binTree){
    	//用来保存二叉树序列化结果的字符串
        StringBuffer sb = new StringBuffer();
        preSerialization(binTree , sb);
        return sb.toString();
    }
    public static void preSerialization(BinTree binTree ,StringBuffer sb){
        if(binTree == null){
            sb.append("#/");
        }else {
            sb.append(binTree.value + "/");
            preSerialization(binTree.left, sb);
            preSerialization(binTree.right, sb);
        }
    }

二叉树的反序列化

二叉树的反序列化是指将序列化后的二叉树字符串重新创建二叉树的过程

字符串通过分割字符“/”进行分割，通过前序遍历的规则，以根，左子树，右子树的特点重构二叉树。

	static int i = 0;
    public static BinTree preDeserialization(String str){

        String[] split = str.split("/");
        i = -1;
        return preDeserialization(split);
    }

    private static BinTree preDeserialization(String[] split){
        BinTree binTree;
        if( split[++i].equals("#")){
            binTree = null;
        }else{
            binTree = new BinTree(split[i]);
            binTree.left = preDeserialization( split );
            binTree.right = preDeserialization( split );
        }

        return binTree;
    }

测试代码与运行结果

二叉树前序遍历的打印方法：

    public static void preOrder(BinTree binTree){
        if(binTree == null)
            return;
        System.out.print(binTree.value + " ");
        preOrder(binTree.left);
        preOrder(binTree.right);
    }

测试代码：

        String test = "a/b/c/#/d/#/#/e/f/#/#/#/g/#/#/";
        BinTree binTree = preDeserialization(test);
        System.out.println("反序列化");
        preOrder(binTree);
        System.out.println();
        String seq = preSerialization(binTree);
        System.out.println("序列化：");
        System.out.println(seq);

运行结果：