网站开发的毕业设计论文框架,网站自动推广,免费分销平台有哪些,电子商务网站建设优势题目
请设计一个算法将二叉树序列化成一个字符串#xff0c;并能将该字符串反序列化出原来二叉树的算法。
分析
先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点#xff0c;每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉…题目
请设计一个算法将二叉树序列化成一个字符串并能将该字符串反序列化出原来二叉树的算法。
分析
先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉树最适合序列化。如果采用前序遍历的顺序那么二叉树的根节点最先序列化到字符串中然后是左子树最后是右子树。这样做的好处是在反序列化时最方便从字符串中读出的第1个数值一定是根节点的值。
实际上只把节点的值序列化到字符串中是不够的。首先要用一个分隔符如逗号把不同的节点分隔开。其次还要考虑如何才能在反序列化的时候构建不同结构的二叉树。 尽管null节点通常没有在图上画出来但它们对树的结构是至关重要的。因此应该把null节点序列化成一个特殊的字符串。如果把null节点序列化成“那么图8.3a中的二叉树用前序遍历将被序列化成字符串66666”而图8.3b中的二叉树将被序列化成字符串66666。
解
public class Test {public static void main(String[] args) {TreeNode node6 new TreeNode(6);TreeNode node66 new TreeNode(6);TreeNode node666 new TreeNode(6);TreeNode node6666 new TreeNode(6);TreeNode node66666 new TreeNode(6);node6.left node66;node6.right node666;node66.left node6666;node66.right node66666;String result serialize(node6);System.out.println(result);TreeNode deserialize deserialize(result);System.out.println(deserialize);}public static String serialize(TreeNode root) {if (root null) {return #;}String leftStr serialize(root.left);String rightStr serialize(root.right);return root.val , leftStr , rightStr;}public static TreeNode deserialize(String data) {String[] nodeStrs data.split(,);int[] array {0};return dfs(nodeStrs, array);}private static TreeNode dfs(String[] strs, int[] array) {String str strs[array[0]];array[0];if (str.equals(#)) {return null;}TreeNode node new TreeNode(Integer.valueOf(str));node.left dfs(strs, array);node.right dfs(strs, array);return node;}
}
