首页 > 代码库 > 二叉树序列化
二叉树序列化
普通二叉树的序列化和反序列化：
先序遍历，null节点用特殊符号标记。
import java.io.File;import java.io.FileNotFoundException;import java.io.PrintStream;import java.util.Scanner;public class Solution { public static void serialize(TreeNode root, PrintStream ps) { if (root == null) ps.print("# "); else { ps.print(root.val + " "); serialize(root.left, ps); serialize(root.right, ps); } } public static TreeNode deserialize(Scanner cin) { String token = cin.next(); if (token.equals("#")) return null; int val = Integer.parseInt(token); TreeNode root = new TreeNode(val); root.left = deserialize(cin); root.right = deserialize(cin); return root; } public static void main(String[] args) throws FileNotFoundException { TreeNode root = new TreeNode(30); root.left = new TreeNode(20); root.left.left = new TreeNode(10); root.right = new TreeNode(40); root.right.left = new TreeNode(35); root.right.right = new TreeNode(50); PrintStream ps = new PrintStream(new File("serialize.txt")); serialize(root, ps); Scanner cin = new Scanner(new File("serialize.txt")); TreeNode back = deserialize(cin); System.out.println(back.val); }}
BST的序列化和反序列化：
序列化：直接先序遍历输出
反序列化：根据先序遍历构造。O(n)时间。
import java.io.FileNotFoundException;import java.util.Scanner;public class Solution { private static int curVal; public static TreeNode deserializeBSTfromInorder(Scanner cin) { if (!cin.hasNext()) return null; else { curVal = cin.nextInt(); return deserialize(cin, Integer.MIN_VALUE, Integer.MAX_VALUE); } } private static TreeNode deserialize(Scanner cin, int min, int max) { if (curVal > min && curVal < max) { int val = curVal; TreeNode root = new TreeNode(val); if (cin.hasNext()) { curVal = cin.nextInt(); root.left = deserialize(cin, min, val); root.right = deserialize(cin, val, max); } return root; } else return null; } public static void main(String[] args) throws FileNotFoundException { String s = "30 20 10 40 35 50"; Scanner cin = new Scanner(s); TreeNode back = deserializeBSTfromInorder(cin); System.out.println(back.val); }}
从数组度数据：
public class Solution { private int curr; public TreeNode deserialize(int[] preorder) { curr = 0; return deserialize(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE); } public TreeNode deserialize(int[] preorder, int min, int max) { if (curr >= preorder.length || preorder[curr] <= min || preorder[curr] >= max) { return null; } int val = preorder[curr++]; TreeNode root = new TreeNode(val); root.left = deserialize(preorder, min, val); root.right = deserialize(preorder, val, max); return root; } public static void main(String[] args) { int[] pre = new int[] { 30, 20, 10, 40, 35, 50 }; TreeNode root = new Solution().deserialize(pre); System.out.println(root); }}
参考：
http://leetcode.com/2010/09/saving-binary-search-tree-to-file.html
http://leetcode.com/2010/09/serializationdeserialization-of-binary.html
二叉树序列化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。