二叉树的序列化

#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;
}

// 直接打印或者使用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);
}

#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;
}