当前位置:网站首页>二叉树的序列化和反序列化
二叉树的序列化和反序列化
2022-08-09 12:00:00 【爱敲代码的Harrison】
- 可以用先序或者中序或者后序或者按层遍历,来实现二叉树的序列化
- 用了什么方式序列化,就用什么样的方式反序列化
- 但是,二叉树无法通过中序遍历的方式实现序列化和反序列化
- 所以,二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化,
- 不同的两棵树,可能得到同样的中序序列,即便补了空位置也可能一样。比如如下两棵树,补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
// __2
// /
// 1
// 和
// 1__
// \
// 2
package com.harrison.class07;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/** * @author Harrison * @create 2022-03-09-14:58 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。 */
public class Code04_SerializeAndReconstructBT {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value=v;
}
}
// 先序序列化
public static Queue<String> preSerial(Node head){
Queue<String> ans=new LinkedList<>();
pres(head,ans);
return ans;
}
public static void pres(Node head,Queue<String> ans){
if(head==null){
ans.add(null);
}else{
ans.add(String.valueOf(head.value));
pres(head.left,ans);
pres(head.right,ans);
}
}
// 先序重建
public static Node buildByPreQueue(Queue<String> preList){
if(preList==null || preList.size()==0){
return null;
}
return preb(preList);
}
public static Node preb(Queue<String> preList){
String value=preList.poll();
if(value==null){
return null;
}
Node head=new Node(Integer.valueOf(value));
head.left=preb(preList);
head.right=preb(preList);
return head;
}
// 后序序列化
public static Queue<String> posSerial(Node head){
Queue<String> ans=new LinkedList<>();
poss(head,ans);
return ans;
}
public static void poss(Node head,Queue<String> ans){
if(head==null){
ans.add(null);
}else{
poss(head.left,ans);
poss(head.right,ans);
ans.add(String.valueOf(head.value));
}
}
// 后序重建 左右根 -》 根右左
public static Node buildByPosQueue(Queue<String> posList){
if(posList==null || posList.size()==0){
return null;
}
Stack<String> stack=new Stack<>();
while(!posList.isEmpty()){
stack.push(posList.poll());
}
return posb(stack);
}
public static Node posb(Stack<String> posStack){
String value=posStack.pop();
if(value==null){
return null;
}
Node head=new Node(Integer.valueOf(value));
head.right=posb(posStack);
head.left=posb(posStack);
return head;
}
// 按层序列化
public static Queue<String> levelSerial(Node head){
Queue<String> ans=new LinkedList<>();
if(head==null){
ans.add(null);
}else{
ans.add(String.valueOf(head.value));
Queue<Node> queue=new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
head=queue.poll();
if(head.left!=null){
ans.add(String.valueOf(head.left.value));
queue.add(head.left);
}else{
ans.add(null);
}
if(head.right!=null){
ans.add(String.valueOf(head.right.value));
queue.add(head.right);
}else{
ans.add(null);
}
}
}
return ans;
}
// 按层重建
public static Node buildByLevelQueue(Queue<String> levelList){
if(levelList==null || levelList.size()==0){
return null;
}
Queue<Node> queue=new LinkedList<>();
Node head=generateNode(levelList.poll());
if(head!=null){
queue.add(head);
}
Node node=null;
while(!queue.isEmpty()){
node=queue.poll();
node.left=generateNode(levelList.poll());
node.right=generateNode(levelList.poll());
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
return head;
}
public static Node generateNode(String value){
if(value==null){
return null;
}
return new Node(Integer.valueOf(value));
}
public static Node generate(int level,int maxLevel,int maxValue){
if(level>maxLevel || Math.random()<0.5){
return null;
}
Node head=new Node((int)(Math.random()*maxValue));
head.left=generate(level+1,maxLevel,maxValue);
head.right=generate(level+1,maxLevel,maxValue);
return head;
}
public static Node generateRandomBST(int maxLevel,int maxValue){
return generate(1,maxLevel,maxValue);
}
public static boolean isSameValueStructure(Node head1, Node head2) {
if (head1 == null && head2 != null) {
return false;
}
if (head1 != null && head2 == null) {
return false;
}
if (head1 == null && head2 == null) {
return true;
}
if (head1.value != head2.value) {
return false;
}
return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
Queue<String> pre = preSerial(head);
Queue<String> pos = posSerial(head);
Queue<String> level = levelSerial(head);
Node preBuild = buildByPreQueue(pre);
Node posBuild = buildByPosQueue(pos);
Node levelBuild = buildByLevelQueue(level);
if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
System.out.println("Oops!");
}
}
System.out.println("test finish!");
}
}
边栏推荐
猜你喜欢
WPF implements a MessageBox message prompt box with a mask
WeChat side: what is consistent hashing, usage scenarios, and what problems does it solve?
防止数据冒用的方法
已解决IndentationError: unindent does not match any oute r indentation Level
Too much volume... Tencent was asked on the side that the memory was full, what would happen?
放下手机吧:实验表明花20分钟思考和上网冲浪同样快乐
900页数学论文证明旋转的黑洞不会爆炸,丘成桐:30多年来广义相对论首次重大突破...
00后写个暑假作业,被监控成这笔样
字符串 | 反转字符串 | 双指针法 | leecode刷题笔记
研发需求的验收标准应该怎么写? | 敏捷实践
随机推荐
proto3-2 syntax
微信小程序支付及退款整体流程
发明时代,「幂集创新」事关你我
全面了解什么是TPS、QPS以及两者的区别
1-hour live broadcast recruitment order: industry big names share dry goods, and enterprise registration opens丨qubit·viewpoint
荣耀携手Blue Yonder,加快企业战略增长
用皮肤“听”音乐,网友戴上这款装备听音乐会:仿佛住在钢琴里
900页数学论文证明旋转的黑洞不会爆炸,丘成桐:30多年来广义相对论首次重大突破...
Experiment record: the process of building a network
鹅厂机器狗花式穿越10m梅花桩:前空翻、单桩跳、起身作揖...全程不打一个趔趄...
Senior told me that the giant MySQL is through SSH connection
脱光衣服待着就能减肥,当真有这好事?
放下手机吧:实验表明花20分钟思考和上网冲浪同样快乐
ThreadLocal的简单理解
罗振宇折戟创业板/ B站回应HR称用户是Loser/ 腾讯罗技年内合推云游戏掌机...今日更多新鲜事在此...
读写分离后,性能居然提升100%了呀
Adalvo收购其首个品牌产品Onsolis
Two ways to enter the Oracle database
AQS同步组件-FutureTask解析和用例
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository