二叉树的还原（反序列化）

一般来说，只有前序遍历、中序遍历、后序遍历是无法还原出一棵二叉树的，要根据前序遍历+中序遍历、中序遍历+后序遍历才能还原出一棵二叉树（总之至少要有中序遍历），如果对这部分内容感兴趣的话可以看看我的另外一篇博客《二叉树及其遍历 树的遍历 && 还原二叉树 (25 分)》。但我们思考一下，如果前序遍历、中序遍历、后序遍历带有空结点信息，那我们是否能够还原出一棵二叉树呢？答案是肯定的，但有个前提，就是我们通过观察带有空结点信息的前序遍历、中序遍历、后序遍历结果能够知道二叉树的根结点，据此我们可以知道无法根据带空结点信息的中序遍历还原出一棵二叉树，因为中序遍历无法确定根结点的位置。另外根据带结点信息的层序遍历我们也可以还原出一棵二叉树，理由也是因为我们可以确定出根结点是谁。

        A
    /       \
   D         C
  / \       / \
 #   E     B   #
    / \   / \
   #   # #   #
#：代表空结点
前序遍历：AD#E##CB###，ADECB
中序遍历：#D#E#A#B#C#，DEABC
后序遍历：###ED##B#CA，EDBCA
层序遍历：ADC#EB#####，ADCEB

前序遍历

关键代码

//还原二叉树的函数
 pTree create(queue<char>&data){
    
     if(data.empty())return NULL;
     char ch=data.front();
     data.pop();
     
     if(ch=='#')return NULL;
     pTree root=new tree(ch);
     root->left=create(data);
     root->right=create(data);
     
     return root;
 }

测试代码

//AD#E##CB###
#include<bits/stdc++.h>
using namespace std;
typedef struct tree*pTree;
struct tree{
    
    char ch;
    pTree left,right;
    tree(char x){
    ch=x;left=right=NULL;}
};

void PreTraverse(pTree root){
    
    if(!root)return;
    cout<<root->ch;
    PreTraverse(root->left);
    PreTraverse(root->right);
}

void InTraverse(pTree root){
    
    if(!root)return;
    InTraverse(root->left);
    cout<<root->ch;
    InTraverse(root->right);
}

void PostTraverse(pTree root){
    
    if(!root)return;
    PostTraverse(root->left);
    PostTraverse(root->right);
    cout<<root->ch;
}

//还原二叉树的函数
 pTree create(queue<char>&data){
    
     if(data.empty())return NULL;
     char ch=data.front();
     data.pop();
     
     if(ch=='#')return NULL;
     pTree root=new tree(ch);
     root->left=create(data);
     root->right=create(data);
     
     return root;
 }

int main(){
    
    queue<char>data;
    string s;cin>>s;
    for(int i=0;i<s.size();i++)data.push(s[i]);
    pTree root=create(data);
    
    PreTraverse(root);
    cout<<endl;
    InTraverse(root);
    cout<<endl;
    PostTraverse(root);
    
    return 0;
}

后序遍历

关键代码

//还原二叉树的函数
pTree create(stack<char>&data){
    
    if(data.empty())return NULL;
    char ch=data.top();
    data.pop();
    
    if(ch=='#')return NULL;
    pTree root=new tree(ch);
    root->right=create(data); //一定是先右子树
    root->left=create(data); //再左子树
    
    return root;
}

测试代码

//###ED##B#CA
#include<bits/stdc++.h>
using namespace std;
typedef struct tree*pTree;
struct tree{
    
    char ch;
    pTree left,right;
    tree(char x){
    ch=x;left=right=NULL;}
};

void PreTraverse(pTree root){
    
    if(!root)return;
    cout<<root->ch;
    PreTraverse(root->left);
    PreTraverse(root->right);
}

void InTraverse(pTree root){
    
    if(!root)return;
    InTraverse(root->left);
    cout<<root->ch;
    InTraverse(root->right);
}

void PostTraverse(pTree root){
    
    if(!root)return;
    PostTraverse(root->left);
    PostTraverse(root->right);
    cout<<root->ch;
}

//还原二叉树的函数
pTree create(stack<char>&data){
    
    if(data.empty())return NULL;
    char ch=data.top();
    data.pop();
    
    if(ch=='#')return NULL;
    pTree root=new tree(ch);
    root->right=create(data); //一定是先右子树
    root->left=create(data); //再左子树
    
    return root;
}

int main(){
    
    stack<char>data;
    string s;cin>>s;
    for(int i=0;i<s.size();i++)data.push(s[i]);
    pTree root=create(data);
    
    PreTraverse(root);
    cout<<endl;
    InTraverse(root);
    cout<<endl;
    PostTraverse(root);
    
    return 0;
}

层序遍历

关键代码

//还原二叉树的函数
pTree create(queue<char>&data){
    
    queue<pTree>q;
    char ch=data.front();
    data.pop();
    pTree root=new tree(ch);
    q.push(root);

    while(!data.empty()){
    
        pTree parent=q.front();
        q.pop();
		
		//处理左子树
        char left=data.front();
        data.pop();
        if(left!='#'){
    
            parent->left=new tree(left);
            q.push(parent->left);
        }
        else parent->left=NULL;
		
		//处理右子树
        char right=data.front();
        data.pop();
        if(right!='#'){
    
            parent->right=new tree(right);
            q.push(parent->right);
        }
        else parent->right=NULL;
    }
    return root;
}

测试代码

#include<bits/stdc++.h>
using namespace std;
typedef struct tree*pTree;
struct tree{
    
    char ch;
    pTree left,right;
    tree(char x){
    ch=x;left=right=NULL;}
};

void PreTraverse(pTree root){
    
    if(!root)return;
    cout<<root->ch;
    PreTraverse(root->left);
    PreTraverse(root->right);
}

void InTraverse(pTree root){
    
    if(!root)return;
    InTraverse(root->left);
    cout<<root->ch;
    InTraverse(root->right);
}

void PostTraverse(pTree root){
    
    if(!root)return;
    PostTraverse(root->left);
    PostTraverse(root->right);
    cout<<root->ch;
}

//还原二叉树的函数
pTree create(queue<char>&data){
    
    queue<pTree>q;
    char ch=data.front();
    data.pop();
    pTree root=new tree(ch);
    q.push(root);

    while(!data.empty()){
    
        pTree parent=q.front();
        q.pop();
		
		//处理左子树
        char left=data.front();
        data.pop();
        if(left!='#'){
    
            parent->left=new tree(left);
            q.push(parent->left);
        }
        else parent->left=NULL;
		
		//处理右子树
        char right=data.front();
        data.pop();
        if(right!='#'){
    
            parent->right=new tree(right);
            q.push(parent->right);
        }
        else parent->right=NULL;
    }
    return root;
}

int main(){
    
    queue<char>data;
    string s;cin>>s;
    for(int i=0;i<s.size();i++)data.push(s[i]);
    pTree root=create(data);
    
    PreTraverse(root);
    cout<<endl;
    InTraverse(root);
    cout<<endl;
    PostTraverse(root);
    
    return 0;
}