java - 序列化和反序列化类似 Trie 的数据结构
问题描述
我正在尝试序列化和反序列化一个类似 Trie 的数据结构,它在每个节点中都有数据/字符。所以要形成一个完整的词,需要从根到叶节点的遍历。
序列化和反序列化应该在前序遍历中,即在 DFS 方法中处理子进程。
#
标记该节点的遍历结束,即类似 trie 的节点不再有任何子节点。
这是我尝试过的。
public class SerializeDeserialize {
public static void main(String[] args) {
// prepare TrieNode Tree
TrieNodeSD root = buildTrienodeTree();
StringBuilder sb = new StringBuilder();
serialize(root, sb);
sb.deleteCharAt(sb.length()-1);
System.out.println(sb.toString());
System.out.println();
TrieNodeSD newRoot = deserialize(sb.toString().split(","), new int[] {0});
StringBuilder newsb = new StringBuilder();
serialize(newRoot, newsb);
newsb.deleteCharAt(newsb.length()-1);
System.out.println(newsb.toString());
}
private static void serialize(TrieNodeSD node, StringBuilder sb) {
if (node == null) return;
sb.append(node.character + ",");
if (node.characters != null && node.characters.size() > 0) {
for (Character c : node.characters.keySet()) {
serialize(node.characters.get(c), sb);
}
}
sb.append("#,");
}
// DOESN'T WORK!!
private static TrieNodeSD deserialize(String[] data, int[] t) {
if (t[0] >= (data.length-1) || data[t[0]].equals("#")) return null;
TrieNodeSD node = new TrieNodeSD(data[t[0]].charAt(0));
t[0] = t[0] + 1;
TrieNodeSD child = deserialize(data, t);
if (child != null) node.characters.put(child.character, child);
return node;
}
private static TrieNodeSD buildTrienodeTree() {
TrieNodeSD root = new TrieNodeSD('A');
root.characters.put('B', new TrieNodeSD('B'));
root.characters.get('B').characters.put('E', new TrieNodeSD('E'));
root.characters.get('B').characters.put('F', new TrieNodeSD('F'));
root.characters.get('B').characters.get('F').characters.put('K', new TrieNodeSD('K'));
root.characters.put('C', new TrieNodeSD('C'));
root.characters.put('D', new TrieNodeSD('D'));
root.characters.get('D').characters.put('G', new TrieNodeSD('G'));
root.characters.get('D').characters.put('H', new TrieNodeSD('H'));
root.characters.get('D').characters.put('I', new TrieNodeSD('I'));
root.characters.get('D').characters.put('J', new TrieNodeSD('J'));
return root;
}
}
class TrieNodeSD {
Map<Character, TrieNodeSD> characters;
char character;
public TrieNodeSD(char c) {
this.characters = new HashMap<Character, TrieNodeSD>();
this.character = c;
}
@Override
public String toString() { return this.character + ""; }
}
序列化以预购格式提供输出(例如A,B,E,#,F,K,#,#,#,C,#,D,G,#,H,#,I,#,J,#,#,#
)。
PROBLEM:
在反序列化期间,代码不会正确处理所有子级,并且不会将它们与正确的父级关联。
有人可以建议如何修复deserialize
方法中的处理或帮助我指出我缺少什么吗?
解决方案
终于找到了对Trie-Like数据结构的预序列化形式进行反序列化的方法。
import java.util.HashMap;
import java.util.Map;
/**
* A<br>
* / | \<br>
* B C D<br>
* / \ / / \ \<br>
* E F G H I J<br>
* |<br>
* K<br>
*
*
*/
public class SerializeDeserialize {
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
StringBuilder newsb = new StringBuilder();
// prepare TrieNode Tree
TrieNodeSD root = buildTrienodeTree();
// serialize tree into string
serialize(root, sb);
sb.deleteCharAt(sb.length() - 1);
System.out.println(sb.toString());
System.out.println();
// construct tree again from serialized string
TrieNodeSD newRoot = deserialize(sb.toString().split(","), new int[] { 0 });
// Verify : again serialize above de-serialized tree to match both
// trees serialized format.
serialize(newRoot, newsb);
newsb.deleteCharAt(newsb.length() - 1);
System.out.println(newsb.toString());
}
private static void serialize(TrieNodeSD node, StringBuilder sb) {
if (node == null) return;
sb.append(node.character + ",");
if (node.characters != null && node.characters.size() > 0) {
for (Character c : node.characters.keySet()) {
serialize(node.characters.get(c), sb);
}
}
sb.append("#,");
}
private static TrieNodeSD deserialize(String[] data, int[] t) {
if (t[0] >= (data.length - 1) || data[t[0]].equals("#")) return null;
TrieNodeSD node = new TrieNodeSD(data[t[0]].charAt(0));
while (true) {
t[0] = t[0] + 1;
TrieNodeSD child = deserialize(data, t);
if (child != null) node.characters.put(child.character, child);
else break;
}
return node;
}
private static TrieNodeSD buildTrienodeTree() {
TrieNodeSD root = new TrieNodeSD('A');
root.characters.put('B', new TrieNodeSD('B'));
root.characters.get('B').characters.put('E', new TrieNodeSD('E'));
root.characters.get('B').characters.put('F', new TrieNodeSD('F'));
root.characters.get('B').characters.get('F').characters.put('K', new TrieNodeSD('K'));
root.characters.put('C', new TrieNodeSD('C'));
root.characters.put('D', new TrieNodeSD('D'));
root.characters.get('D').characters.put('G', new TrieNodeSD('G'));
root.characters.get('D').characters.put('H', new TrieNodeSD('H'));
root.characters.get('D').characters.put('I', new TrieNodeSD('I'));
root.characters.get('D').characters.put('J', new TrieNodeSD('J'));
return root;
}
}
class TrieNodeSD {
Map<Character, TrieNodeSD> characters;
char character;
public TrieNodeSD(char c) {
this.characters = new HashMap<Character, TrieNodeSD>();
this.character = c;
}
@Override
public String toString() {
return this.character + "";
}
}
示例运行:先序遍历序列化给定的Trie-Like数据结构,使用序列化的字符串构造Trie-Like数据结构,即反序列化,最后再次序列化,验证序列化后的形式是否与实际树匹配。
A,B,E,#,F,K,#,#,#,C,#,D,G,#,H,#,I,#,J,#,#,#
A,B,E,#,F,K,#,#,#,C,#,D,G,#,H,#,I,#,J,#,#,#
推荐阅读
- flutter - 如何仅在 Flutter 中的特定页面上更改状态栏颜色
- python - 获取 QMessageBox addButton 函数的按下按钮的值
- angular - 为什么 app.component.html 无法识别 server-element,server-element 的内容不会显示在浏览器中?
- java - 在没有 Java Mail API 或任何第三方 API 的情况下用 Java 编写 SMTP 客户端
- matlab - 如何在 Matlab 中删除不间断的前导空格?
- typescript - 什么意思:枚举声明只能与命名空间或其他枚举声明合并
- reactjs - 尝试导入错误:“./ErrorFallback”不包含默认导出(导入为“ErrorFallback”)
- angular - 防止在 Angular 中打开新选项卡
- java - 将 JNOSQL(CDI 库)与 Spring Boot 一起使用 - 找不到 Bean
- java - 1 个 EditText 的 2 个 TextWatchers