Java与C++二叉树序列化
明朗晨光 人气:01、什么是二叉树的序列化与反序列化
二叉树就是节点在内存区域中串联起来的,但是如果掉电,内存上的数据就没有了。为了保存这种结构,将二叉树用字符串的形式保存到硬盘中,这就是序列化;从字符串形式转换为二叉树,这就是反序列化。
唯一的字符串会对应唯一的结构,唯一的结构也会对应唯一的字符串,即字符串和二叉树是一一对应的。
【思路】首先认为 NULL
是不可忽略的,遇到 NULL
就用 #
或者其他字符代替。且每访问结束一个节点,用分隔符隔开。
2、先序方式序列化和反序列化
【例子】
上图红色数字就是先序遍历的顺序,所以得到的字符串就是 “1,1,#,1,#,#,#”。
之所以要用分隔符隔开,是为了防止二义性,比如如下两棵树:
【代码实现】
//先序序列化二叉树 void preS(TreeNode *root, queue<string> &ans) { if (root == nullptr) ans.push("#"); else { //每个节点转成的字符串保存到队列中 ans.push(to_string(root->value)); preS(root->lchild, ans); preS(root->rchild, ans); } } queue<string> preOrderSerial(TreeNode *root) { queue<string> ans; preS(root, ans); return ans; } TreeNode *preb(queue<string> &prelist) { string value = prelist.front(); prelist.pop(); //空树 if (value == "#") return nullptr; TreeNode *root = new TreeNode(stoi(value)); //每个节点字符串转成整数 root->lchild = preb(prelist); root->rchild = preb(prelist); return root; } //以先序序列化还原二叉树, 即反序列化 TreeNode *buildByPreQueue(queue<string> &prelist) { if (prelist.size() == 0) return nullptr; return preb(prelist); }
3、后序方式序列化和反序列化
//后序序列化 void posS(TreeNode *root, queue<string> &ans) { if (root == nullptr) ans.push("#"); else { posS(root->lchild, ans); posS(root->rchild, ans); ans.push(to_string(root->value)); } } queue<string> posOrderSerial(TreeNode *root) { queue<string> ans; posS(root, ans); return ans; } //后序反序列化 TreeNode *posB(stack<string> &posstack) { string value = posstack.top(); posstack.pop(); if (value == "#") return nullptr; TreeNode *root = new TreeNode(stoi(value)); root->rchild = posB(posstack); root->lchild = posB(posstack); return root; } TreeNode *buildByPosQueue(queue<string> &poslist) { if (poslist.size() == 0) return nullptr; stack<string> sta; //栈中的顺序为:中右左 while (!poslist.empty()) { sta.push(poslist.front()); poslist.pop(); } return posB(sta); }
4、层序方式序列化和反序列化
//层序序列化 queue<string> levelSerial(TreeNode *root) { queue<string> ans; if (root == nullptr) { ans.push("#"); } else { ans.push(to_string(root->value)); //准备队列,用于层序遍历 queue<TreeNode *> que; que.push(root); while (!que.empty()) { TreeNode *cur = que.front(); que.pop(); if (cur->lchild != nullptr) { ans.push(to_string(cur->lchild->value)); que.push(cur->lchild); } else { ans.push("#"); } if (cur->rchild != nullptr) { ans.push(to_string(cur->rchild->value)); que.push(cur->rchild); } else { ans.push("#"); } } } return ans; } //层序反序列化 TreeNode *generateTreeNode(string str) { if (str == "#") return nullptr; return new TreeNode(stoi(str)); } TreeNode *buildByLevelQueue(queue<string> &levelList) { if (levelList.size() == 0) { return nullptr; } TreeNode *root = generateTreeNode(levelList.front()); levelList.pop(); queue<TreeNode *> que; if (root != nullptr) { que.push(root); } TreeNode *cur = nullptr; while (!que.empty()) { cur = que.front(); que.pop(); cur->lchild = generateTreeNode(levelList.front()); levelList.pop(); cur->rchild = generateTreeNode(levelList.front()); levelList.pop(); if (cur->lchild != nullptr) { que.push(cur->lchild); } if (cur->rchild != nullptr) { que.push(cur->rchild); } } return root; }
5、完整代码 C++ 版
/************************************************************************* > File Name: 029.二叉树的序列化与反序列化.cpp > Author: Maureen > Mail: Maureen@qq.com > Created Time: 一 6/20 17:40:56 2022 ************************************************************************/ #include <iostream> #include <cstring> #include <queue> #include <ctime> #include <stack> using namespace std; /* * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化, * 以下代码全部实现了。 * 但是,二叉树无法通过中序遍历的方式实现序列化和反序列化 * 因为不同的两棵树,可能得到同样的中序序列,即便补了空位置也可能一样。 * 比如如下两棵树 * __2 * / * 1 * 和 * 1__ * \ * 2 * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null} * * */ class TreeNode { public: int value; TreeNode *lchild; TreeNode *rchild; TreeNode(int data) : value(data) {} }; //先序序列化二叉树 void preS(TreeNode *root, queue<string> &ans) { if (root == nullptr) ans.push("#"); else { //每个节点转成的字符串保存到队列中 ans.push(to_string(root->value)); preS(root->lchild, ans); preS(root->rchild, ans); } } queue<string> preOrderSerial(TreeNode *root) { queue<string> ans; preS(root, ans); return ans; } //以先序序列化还原二叉树, 即反序列化 TreeNode *preb(queue<string> &prelist) { string value = prelist.front(); prelist.pop(); //空树 if (value == "#") return nullptr; TreeNode *root = new TreeNode(stoi(value)); //每个节点字符串转成整数 root->lchild = preb(prelist); root->rchild = preb(prelist); return root; } TreeNode *buildByPreQueue(queue<string> &prelist) { if (prelist.size() == 0) return nullptr; return preb(prelist); } //后序序列化 void posS(TreeNode *root, queue<string> &ans) { if (root == nullptr) ans.push("#"); else { posS(root->lchild, ans); posS(root->rchild, ans); ans.push(to_string(root->value)); } } queue<string> posOrderSerial(TreeNode *root) { queue<string> ans; posS(root, ans); return ans; } //后序反序列化 TreeNode *posB(stack<string> &posstack) { string value = posstack.top(); posstack.pop(); if (value == "#") return nullptr; TreeNode *root = new TreeNode(stoi(value)); root->rchild = posB(posstack); root->lchild = posB(posstack); return root; } TreeNode *buildByPosQueue(queue<string> &poslist) { if (poslist.size() == 0) return nullptr; stack<string> sta; //栈中的顺序为:中右左 while (!poslist.empty()) { sta.push(poslist.front()); poslist.pop(); } return posB(sta); } //层序序列化 queue<string> levelSerial(TreeNode *root) { queue<string> ans; if (root == nullptr) { ans.push("#"); } else { ans.push(to_string(root->value)); //准备队列,用于层序遍历 queue<TreeNode *> que; que.push(root); while (!que.empty()) { TreeNode *cur = que.front(); que.pop(); if (cur->lchild != nullptr) { ans.push(to_string(cur->lchild->value)); que.push(cur->lchild); } else { ans.push("#"); } if (cur->rchild != nullptr) { ans.push(to_string(cur->rchild->value)); que.push(cur->rchild); } else { ans.push("#"); } } } return ans; } //层序反序列化 TreeNode *generateTreeNode(string str) { if (str == "#") return nullptr; return new TreeNode(stoi(str)); } TreeNode *buildByLevelQueue(queue<string> &levelList) { if (levelList.size() == 0) { return nullptr; } TreeNode *root = generateTreeNode(levelList.front()); levelList.pop(); queue<TreeNode *> que; if (root != nullptr) { que.push(root); } TreeNode *cur = nullptr; while (!que.empty()) { cur = que.front(); que.pop(); cur->lchild = generateTreeNode(levelList.front()); levelList.pop(); cur->rchild = generateTreeNode(levelList.front()); levelList.pop(); if (cur->lchild != nullptr) { que.push(cur->lchild); } if (cur->rchild != nullptr) { que.push(cur->rchild); } } return root; } //for test TreeNode *generate(int level, int maxLevel, int maxValue) { if (level > maxLevel || rand() % 100 < 0.5) return nullptr; TreeNode *root = new TreeNode(rand() % maxValue); root->lchild = generate(level + 1, maxLevel, maxValue); root->rchild = generate(level + 1, maxLevel, maxValue); return root; } TreeNode *generateRandomBST(int maxLen, int maxVal) { return generate(1, maxLen, maxVal); } bool isSameValueStructure(TreeNode *root1, TreeNode *root2) { if (root1 == nullptr && root2 != nullptr) return false; if (root1 != nullptr && root2 == nullptr) return false; if (root1 == nullptr && root2 == nullptr) return true; if (root1->value != root2->value) return false; return isSameValueStructure(root1->lchild, root2->lchild) && isSameValueStructure(root1->rchild, root2->rchild); } string getSpace(int num) { string space = ""; for (int i = 0; i < num; i++) { space += " "; } return space; } void printInOrder(TreeNode *root, int height, string to, int len) { if (root == nullptr) return ; printInOrder(root->rchild, height + 1, "v", len); string val = to + to_string(root->value) + to; int lenM = val.length(); int lenL = (len - lenM) / 2; int lenR = len - lenM - lenL; val = getSpace(lenL) + val + getSpace(lenR); cout << getSpace(height * len) + val << endl; printInOrder(root->lchild, height + 1, "^", len); } void printTree(TreeNode *root) { cout << "Binary Tree:" << endl; printInOrder(root, 0, "H", 7); cout << endl; } int main() { srand(time(0)); int maxLevel = 5; int maxValue = 100; int testTime = 1000000; cout << "test begin" << endl; for (int i = 0; i < testTime + 1; i++) { TreeNode *root = generateRandomBST(maxLevel, maxValue); queue<string> pre = preOrderSerial(root); queue<string> post = posOrderSerial(root); queue<string> level = levelSerial(root); TreeNode *preBuild = buildByPreQueue(pre); TreeNode *posBuild = buildByPosQueue(post); TreeNode *levelBuild = buildByLevelQueue(level); /*bool isPreBuildisSuccess = isSameValueStructure(root, preBuild); bool isPosBuildisSuccess = isSameValueStructure(root, posBuild); bool isLevelBuildSuccess = isSameValueStructure(root, levelBuild); cout << isPreBuildisSuccess << ", " << isPosBuildisSuccess << ", " << isLevelBuildSuccess << endl;*/ if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) { cout << "Oops!" << endl; break; } if (i && i % 100 == 0) cout << i << " cases passed!" << endl; } cout << "test finish!" << endl; return 0; }
Java 版
package class11; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Code02_SerializeAndReconstructTree { /* * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化, * 以下代码全部实现了。 * 但是,二叉树无法通过中序遍历的方式实现序列化和反序列化 * 因为不同的两棵树,可能得到同样的中序序列,即便补了空位置也可能一样。 * 比如如下两棵树 * __2 * / * 1 * 和 * 1__ * \ * 2 * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null} * * */ 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 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 Node buildByPosQueue(Queue<String> poslist) { if (poslist == null || poslist.size() == 0) { return null; } // 左右中 -> stack(中右左) 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<Node>(); queue.add(head); while (!queue.isEmpty()) { head = queue.poll(); // head 父 子 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; } 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 val) { if (val == null) { return null; } return new Node(Integer.valueOf(val)); } // for test public static Node generateRandomBST(int maxLevel, int maxValue) { return generate(1, maxLevel, maxValue); } // for test 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; } // for test 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); } // for test public static void printTree(Node head) { System.out.println("Binary Tree:"); printInOrder(head, 0, "H", 17); System.out.println(); } public static void printInOrder(Node head, int height, String to, int len) { if (head == null) { return; } printInOrder(head.right, height + 1, "v", len); String val = to + head.value + to; int lenM = val.length(); int lenL = (len - lenM) / 2; int lenR = len - lenM - lenL; val = getSpace(lenL) + val + getSpace(lenR); System.out.println(getSpace(height * len) + val); printInOrder(head.left, height + 1, "^", len); } public static String getSpace(int num) { String space = " "; StringBuffer buf = new StringBuffer(""); for (int i = 0; i < num; i++) { buf.append(space); } return buf.toString(); } 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!"); } }
加载全部内容