二叉树的序列化和反序列化

简介: 二叉树的序列化和反序列化

可以用先序或者中序或者后序或者按层遍历,来实现二叉树的序列化

用了什么方式序列化,就用什么样的方式反序列化

但是,二叉树无法通过中序遍历的方式实现序列化和反序列化

所以,二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化,

不同的两棵树,可能得到同样的中序序列,即便补了空位置也可能一样。比如如下两棵树,补足空位置的中序遍历结果都是{ 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;
public class Code05_SerializeAndReconstruct {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  // 先序方式序列化二叉树。中序,后序方式类似,只是结点序列化顺序不一样
  // 能懂递归方式遍历二叉树,这里就很好理解
  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 Queue<String> inSerial(Node head) {
    Queue<String> ans = new LinkedList<>();
    ins(head, ans);
    return ans;
  }
  public static void ins(Node head, Queue<String> ans) {
    if (head == null) {
      ans.add(null);
    } else {
      ins(head.left, ans);
      ans.add(String.valueOf(head.value));
      ins(head.right, ans);
    }
  }
  // 后序方式序列化二叉树
  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 builtByPreQueue(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 Node builtByPosQueue(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> possStack) {
    String value = possStack.pop();
    if (value == null) {
      return null;
    }
    // 左右跟 --> 根右左
    Node head = new Node(Integer.valueOf(value));
    head.right = posb(possStack);
    head.left = posb(possStack);
    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<Node>();
      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 builtByLevelQueue(Queue<String> levelList) {
    if (levelList == null || levelList.size() == 0) {
      return null;
    }
    Node head = generateNode(levelList.poll());
    Queue<Node> queue = new LinkedList<Node>();
    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 generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  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 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 testTimes = 1000000;
    int maxLevel = 5;
    int maxValue = 100;
    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 preBuilt = builtByPreQueue(pre);
      Node posBuilt = builtByPosQueue(pos);
      Node levleBuilt = builtByLevelQueue(level);
      if (!isSameValueStructure(preBuilt, posBuilt) || !isSameValueStructure(posBuilt, levleBuilt)) {
        System.out.println("oops");
      }
    }
    System.out.println("finish");
  }
}
相关文章
|
23天前
|
JSON 数据格式 索引
Python中序列化/反序列化JSON格式的数据
【11月更文挑战第4天】本文介绍了 Python 中使用 `json` 模块进行序列化和反序列化的操作。序列化是指将 Python 对象(如字典、列表)转换为 JSON 字符串,主要使用 `json.dumps` 方法。示例包括基本的字典和列表序列化,以及自定义类的序列化。反序列化则是将 JSON 字符串转换回 Python 对象,使用 `json.loads` 方法。文中还提供了具体的代码示例,展示了如何处理不同类型的 Python 对象。
|
1月前
|
存储 安全 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第22天】在Java的世界里,对象序列化和反序列化是数据持久化和网络传输的关键技术。本文将带你了解如何在Java中实现对象的序列化与反序列化,并探讨其背后的原理。通过实际代码示例,我们将一步步展示如何将复杂数据结构转换为字节流,以及如何将这些字节流还原为Java对象。文章还将讨论在使用序列化时应注意的安全性问题,以确保你的应用程序既高效又安全。
|
2月前
|
存储 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第9天】在Java的世界里,对象序列化是连接数据持久化与网络通信的桥梁。本文将深入探讨Java对象序列化的机制、实践方法及反序列化过程,通过代码示例揭示其背后的原理。从基础概念到高级应用,我们将一步步揭开序列化技术的神秘面纱,让读者能够掌握这一强大工具,以应对数据存储和传输的挑战。
|
2月前
|
存储 安全 Java
Java编程中的对象序列化与反序列化
【10月更文挑战第3天】在Java编程的世界里,对象序列化与反序列化是实现数据持久化和网络传输的关键技术。本文将深入探讨Java序列化的原理、应用场景以及如何通过代码示例实现对象的序列化与反序列化过程。从基础概念到实践操作,我们将一步步揭示这一技术的魅力所在。
|
1月前
|
存储 缓存 NoSQL
一篇搞懂!Java对象序列化与反序列化的底层逻辑
本文介绍了Java中的序列化与反序列化,包括基本概念、应用场景、实现方式及注意事项。序列化是将对象转换为字节流,便于存储和传输;反序列化则是将字节流还原为对象。文中详细讲解了实现序列化的步骤,以及常见的反序列化失败原因和最佳实践。通过实例和代码示例,帮助读者更好地理解和应用这一重要技术。
33 0
|
3月前
|
JSON 安全 编译器
扩展类实例的序列化和反序列化
扩展类实例的序列化和反序列化
37 1
|
3月前
|
JSON fastjson Java
niubility!即使JavaBean没有默认无参构造器,fastjson也可以反序列化。- - - - 阿里Fastjson反序列化源码分析
本文详细分析了 Fastjson 反序列化对象的源码(版本 fastjson-1.2.60),揭示了即使 JavaBean 沲有默认无参构造器,Fastjson 仍能正常反序列化的技术内幕。文章通过案例展示了 Fastjson 在不同构造器情况下的行为,并深入探讨了 `ParserConfig#getDeserializer` 方法的核心逻辑。此外,还介绍了 ASM 字节码技术的应用及其在反序列化过程中的角色。
86 10
|
3月前
|
存储 XML JSON
用示例说明序列化和反序列化
用示例说明序列化和反序列化
21 1
|
3月前
|
存储 Java 开发者
Java编程中的对象序列化与反序列化
【9月更文挑战第20天】在本文中,我们将探索Java编程中的一个核心概念——对象序列化与反序列化。通过简单易懂的语言和直观的代码示例,你将学会如何将对象状态保存为字节流,以及如何从字节流恢复对象状态。这不仅有助于理解Java中的I/O机制,还能提升你的数据持久化能力。准备好让你的Java技能更上一层楼了吗?让我们开始吧!
|
3月前
|
XML Dubbo Java
分布式-序列化,反序列化
分布式-序列化,反序列化