二叉树被记录为文件的过程叫作二叉树的序列化,通过文件内容重建原来二叉树的过程叫作二叉树的反序列化,给定一颗二叉树,请将该二叉树先序序列化和层序序列化。
假设序列化的结果字符串为 str,初始时 str = "",遍历二叉树时,遇到 null 节点,则在 str 的末尾加上 "#!",否则加上"当前的节点值!"。
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
输出两行分别表示该二叉树的先序序列化和层序序列化
2 1 1 2 0 2 0 0
1!2!#!#!#! 1!2!#!#!#!
#include <stdio.h> #include <stdlib.h> typedef int Id; typedef struct { Id id; Id l_child, r_child; } TreeNodeInfo, *INFO; void preorder(INFO infos, Id root_id) { if (!root_id) { fprintf(stdout, "#!"); return; } fprintf(stdout, "%d!", root_id); preorder(infos, infos[root_id].l_child); preorder(infos, infos[root_id].r_child); } void levelOrder(INFO infos, Id root_id) { // corner case if (!root_id) return; Id* q = (Id*) malloc(2E6 * sizeof(Id)); if (!q) exit(0); size_t front = 0, rear = 0; *(q + rear++) = root_id; Id cur; while (front < rear) { cur = *(q + front++); if (cur) { fprintf(stdout, "%d!", cur); *(q + rear++) = infos[cur].l_child; *(q + rear++) = infos[cur].r_child; } else fprintf(stdout, "#!"); } } int main(const int argc, const char* const argv[]) { int n, root_id; fscanf(stdin, "%d %d", &n, &root_id); INFO infos = (INFO) malloc ((n + 1) * sizeof(TreeNodeInfo)) ; Id fa, l_ch, r_ch; while (n--) { fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch); infos[fa].id = fa; infos[fa].l_child = l_ch; infos[fa].r_child = r_ch; } preorder(infos, root_id), fputc(10, stdout), levelOrder(infos, root_id); return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Queue; import java.util.LinkedList; class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } public class Main { public static StringBuilder preOrder = new StringBuilder(); public static StringBuilder levelOrder = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().trim().split(" "); int n = Integer.parseInt(params[0]); int rootVal = Integer.parseInt(params[1]); TreeNode root = new TreeNode(rootVal); // 建树,同时得到先序序列 buildTree(br, root, n); // 得到层次序列 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); levelOrder.append(root.val + "!"); while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(node.left != null){ levelOrder.append(node.left.val + "!"); queue.offer(node.left); }else levelOrder.append("#!"); if(node.right != null){ levelOrder.append(node.right.val + "!"); queue.offer(node.right); }else levelOrder.append("#!"); } System.out.println(preOrder); System.out.println(levelOrder); } private static void buildTree(BufferedReader br, TreeNode root, int n) throws IOException { if(root != null){ preOrder.append(root.val + "!"); }else preOrder.append("#!"); if(n == 0) return; String[] params = br.readLine().trim().split(" "); int leftVal = Integer.parseInt(params[1]), rightVal = Integer.parseInt(params[2]); if(leftVal != 0){ root.left = new TreeNode(leftVal); buildTree(br, root.left, n--); }else preOrder.append("#!"); if(rightVal != 0){ root.right = new TreeNode(rightVal); buildTree(br, root.right, n--); }else preOrder.append("#!"); } }
// 直接打印或者使用string直接拼接都会超时,只能使用stringBuilder import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); br.readLine(); TreeNode root = createTree(br); StringBuilder sb = new StringBuilder(); serialByPre(root,sb); System.out.println(sb); sb.delete(0, sb.length()); serialByLevel(root,sb); System.out.println(sb); br.close(); } public static StringBuilder serialByPre(TreeNode head,StringBuilder sb){ if(head==null){ return sb.append("#!"); } sb.append(head.val+"!"); serialByPre(head.left,sb); serialByPre(head.right,sb); return sb; } public static StringBuilder serialByLevel(TreeNode head,StringBuilder sb){ if(head==null){ return sb.append("#!"); } Queue<TreeNode> queue=new LinkedList<TreeNode>(); queue.add(head); while(!queue.isEmpty()){ head = queue.poll(); if (null == head) { sb.append("#!"); } else { sb.append(head.val+"!"); queue.offer(head.left); queue.offer(head.right); } } return sb; } private static TreeNode createTree(BufferedReader br) throws IOException { String[] rawInput = br.readLine().trim().split(" "); int rootVal = Integer.parseInt(rawInput[0]); int leftVal = Integer.parseInt(rawInput[1]); int rightVal = Integer.parseInt(rawInput[2]); TreeNode root = new TreeNode(rootVal); if (0 != leftVal) { root.left = createTree(br); } if (0 != rightVal) { root.right = createTree(br); } return root; } } class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static Node[] nodes; public static int n; public static int root; public static StringBuffer res = new StringBuffer(""); public static class Node { int val; int left, right; Node(int val, int left, int right) { this.val = val; this.left = left; this.right = right; } } public static void serializeViaPreOrder(int index) { if (index != 0) { res.append(String.valueOf(nodes[index].val)).append("!"); serializeViaPreOrder(nodes[index].left); serializeViaPreOrder(nodes[index].right); } else { res.append("#!"); } } public static void serializeViaLevelOrder(int index) { Queue<Integer> queue = new LinkedList<>(); queue.offer(index); while (!queue.isEmpty()) { int front = queue.poll(); if (front != 0) { res.append(nodes[front].val).append("!"); queue.offer(nodes[front].left); queue.offer(nodes[front].right); } else { res.append("#!"); } } } public static void main(String[] args) { Scanner input = new Scanner(System.in); n = input.nextInt(); root = input.nextInt(); nodes = new Node[n+1]; for (int i = 0; i < n; i++) { int val = input.nextInt(); int left = input.nextInt(); int right = input.nextInt(); nodes[val] = new Node(val, left, right); } serializeViaPreOrder(root); System.out.println(res.toString()); res = new StringBuffer(""); serializeViaLevelOrder(root); System.out.println(res.toString()); } }
#include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode* lch; TreeNode* rch; TreeNode(int x):val(x),lch(NULL),rch(NULL){} }; void createTree(TreeNode* root,int& cnt) { if(cnt==0) return; int p,l,r; cin>>p>>l>>r; if(l!=0) { TreeNode* lch = new TreeNode(l); root->lch = lch; createTree(root->lch, --cnt); } if(r!=0) { TreeNode* rch = new TreeNode(r); root->rch = rch; createTree(root->rch, --cnt); } } void preserial(TreeNode* root) { if(root==NULL) return; stack<TreeNode*> pstack; pstack.push(root); while(!pstack.empty()) { TreeNode* cur = pstack.top(); pstack.pop(); if(cur!=NULL) { cout<<cur->val<<"!"; pstack.push(cur->rch); pstack.push(cur->lch); }else { cout<<"#!"; } } cout<<endl; return; } void layerserial(TreeNode* root) { if(root==NULL) return; queue<TreeNode*> pqueue; pqueue.push(root); while(!pqueue.empty()) { TreeNode* cur = pqueue.front(); pqueue.pop(); if(cur!=NULL) { cout<<cur->val<<"!"; pqueue.push(cur->lch); pqueue.push(cur->rch); } else { cout<<"#!"; } } cout<<endl; return; } int main() { int n,root_val; cin>>n>>root_val; TreeNode* root = new TreeNode(root_val); for(int i=0;i<n;i++) { createTree(root,n); } preserial(root); layerserial(root); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); br.readLine(); TreeNode root = createSearchTree(br); br.close(); fun(root); } private static void fun(TreeNode root) { System.out.println(preOrder(root)); System.out.println(levelOrder(root)); } private static String preOrder(TreeNode root){ if(root == null) return "#!"; String res = root.val+"!"; res+= preOrder(root.left); res+=preOrder(root.right); return res; } private static String levelOrder(TreeNode root){ if(root == null) return "#!"; Deque<TreeNode> queue = new LinkedList<>(); StringBuilder sb = new StringBuilder(); sb.append(root.val+"!"); queue.offer(root); while(!queue.isEmpty()){ TreeNode cur = queue.poll(); if(cur.left != null){ queue.offer(cur.left); sb.append(cur.left.val+"!"); }else{ sb.append("#!"); } if(cur.right != null){ queue.offer(root.right); sb.append(cur.right.val+"!"); }else{ sb.append("#!"); } } return sb.toString(); } // 递归创建二叉树 private static TreeNode createSearchTree(BufferedReader br) { try { String[] rawInput = br.readLine().trim().split(" "); int value = Integer.parseInt(rawInput[0]); int left = Integer.parseInt(rawInput[1]); int right = Integer.parseInt(rawInput[2]); TreeNode treeNode = new TreeNode(value); if (0 != left) { treeNode.left = createSearchTree(br); } if (0 != right) { treeNode.right = createSearchTree(br); } return treeNode; } catch (IOException e) { return null; } } } class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int value) { this.val = value; this.left = null; this.right = null; } }
#include <iostream> #include <vector> #include <string> #include <queue> #include <stack> using namespace std; int v[1000001][2]; string res, str; void Inorder(int root) { stack<int>s; s.push(root); while(!s.empty()){ int top = s.top(); s.pop(); if(top != 0){ res += to_string(top)+"!"; Inorder(v[root][0]); Inorder(v[root][1]); }else{ res += "#!"; } } return; } void Level(int root) { if(root ==0){ str+="!#"; return; } queue<int>que; que.push(root); while (!que.empty()) { int top = que.front(); que.pop(); if (top == 0) { str += "#!"; } else { str += to_string(top) + "!"; que.push(v[top][0]); que.push(v[top][1]); } } } int main() { int n, root; cin >> n >> root; for (int i = 0; i < n; ++i) { int p; cin >> p; cin >> v[p][0]; cin >> v[p][1]; } Inorder(root); Level(root); cout << res << endl; cout << str << endl; return 0; }
#include <iostream> #include <string> #include <queue> #include <stack> using namespace std; struct TreeNode { int val; string str_mode; struct TreeNode *left; struct TreeNode *right; TreeNode(int val) { this->val = val; str_mode = to_string(val); this->left = NULL; this->right = NULL; } }; void BuildTree_In(struct TreeNode *temp,stack<struct TreeNode *> &stk) { while(1) { int root_val,left_val,right_val; cin >> root_val >> left_val >> right_val; if(right_val != 0) { temp->right = new struct TreeNode (right_val); stk.push(temp->right); } if(left_val != 0) { temp->left = new struct TreeNode (left_val); temp = temp->left; } else { break; } } } struct TreeNode * BuildTree() { int root_val; cin >> root_val >> root_val; //节点个数不需要 可以直接覆盖 stack<struct TreeNode *> stk; struct TreeNode *root = new struct TreeNode (root_val); BuildTree_In(root,stk); while(!stk.empty()) { struct TreeNode *temp = stk.top(); stk.pop(); BuildTree_In(temp,stk); } return root; } void VisitAlongLeftBranch(struct TreeNode *pnode,string &str,stack< struct TreeNode*> &stk) { while(pnode) { string temp = to_string(pnode->val); str += temp; str += "!"; stk.push(pnode->right); pnode = pnode->left; } str += "#!"; } void preoder(struct TreeNode* root) { stack< struct TreeNode*> stk; string str; stk.push(root); while(!stk.empty()) { TreeNode *temp = stk.top(); stk.pop(); VisitAlongLeftBranch(temp,str,stk); } cout << str <<endl; } void bfs(struct TreeNode* root) { queue <struct TreeNode*> qe; string str; qe.push(root); while(!qe.empty()) { TreeNode * temp = qe.front(); qe.pop(); if(temp == NULL) { str += "#!"; } else { str += temp->str_mode; str += "!"; qe.push(temp->left); qe.push(temp->right); } } cout << str << endl; } int main() { struct TreeNode *root = BuildTree(); preoder(root); bfs(root); return 0; }
#include<bits/stdc++.h> using namespace std; void serialPreOrder(int root,int* lc,int* rc,string& ans) { if(!root) { ans+="#!"; return; } ans+=to_string(root); ans+="!"; serialPreOrder(lc[root],lc,rc,ans); serialPreOrder(rc[root],lc,rc,ans); } void serialByLevel(int root,int* lc,int* rc,string& ans) { if(!root) { ans+="#!"; return ; } queue<int>q; q.push(root); while(!q.empty()) { int cur = q.front(); q.pop(); if(cur==0) { ans+="#!"; } else{ ans+=to_string(cur)+"!"; q.push(lc[cur]); q.push(rc[cur]); } } } int main() { int n,root; cin>>n>>root; int* lc = new int[n+1]; int* rc = new int[n+1]; int p; for(int i=0;i<n;++i) { cin>>p; cin>>lc[p]>>rc[p]; } string ans = ""; serialPreOrder(root,lc,rc,ans); cout<<ans<<endl; ans.clear(); serialByLevel(root,lc,rc,ans); cout<<ans<<endl; return 0; }
没见过这么恶心的,还要自己处理,将数组转化为二叉树,恶心到我了,但是还没通过,求大神助攻 #include <queue> #include <string> #include <iostream> using namespace std; struct TreeNode { public: int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } TreeNode(int x, int l, int r) { this->val=x; if(l==0) this->left=nullptr; if(r==0) this->right=nullptr; this->left=new TreeNode(l); this->right=new TreeNode(r); } int getVal(TreeNode* node) { return node->val; } }; class Solution { public: void serialize(TreeNode* r,string& s) { if(r==nullptr) { s+="#!"; } else { s+=r->val; serialize(r->left,s); serialize(r->right,s); } } string serialize(TreeNode* root) { string s; serialize(root,s); return s; } string layerserialize(TreeNode* root) { string s; queue<TreeNode*> nodes; if(root==nullptr)return ""; nodes.push(root); while(nodes.size()>0) { for(int i=0,n=nodes.size();i<n;++i) { TreeNode* node=nodes.front(); nodes.pop(); int val=node->val; string c=to_string(val)+"!"; s+=c; if(node->left==nullptr)s+="#!"; if(node->right==nullptr)s+="#!"; if(node->left!=nullptr)nodes.push(node->left); if(node->right!=nullptr)nodes.push(node->left); } } return s; } }; int main() { int num,val; cin>>num>>val; int fa,lch,rch; cin>>fa>>lch>>rch; TreeNode* root=new TreeNode(fa,lch,rch); for(int i=1;i<num;++i) { bool left=true; TreeNode* tmp=root; cin>>fa>>lch>>rch; if(fa==(tmp->left->val)) { tmp=tmp->left; if(lch==0) { tmp->left=nullptr; } else { tmp->left=new TreeNode(lch); } if(rch==0) { tmp->right=nullptr; } else { tmp->right=new TreeNode(rch); } } else if(fa==(tmp->right->val)) { tmp=tmp->right; if(lch==0) { tmp->left=nullptr; } else { tmp->left=new TreeNode(lch); } if(rch==0) { tmp->right=nullptr; } else { tmp->right=new TreeNode(rch); } } } Solution s; string s1,s2; s1=s.serialize(root); s2=s.layerserialize(root); cout<<s1<<endl; cout<<s2<<endl; return 0; }