当前位置:网站首页>二叉树的还原(反序列化)
二叉树的还原(反序列化)
2022-07-31 05:21:00 【im34v】
一般来说,只有前序遍历、中序遍历、后序遍历是无法还原出一棵二叉树的,要根据前序遍历+中序遍历、中序遍历+后序遍历才能还原出一棵二叉树(总之至少要有中序遍历),如果对这部分内容感兴趣的话可以看看我的另外一篇博客《二叉树及其遍历 树的遍历 && 还原二叉树 (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;
}
边栏推荐
猜你喜欢
随机推荐
文件内容浏览cut、uniq、sort、tr命令的使用,
LVM和磁盘配额
多线程(1)
2022年软件测试现状最新报告
Oracle入门 04 - Vmware虚拟机安装配置
PXE高效批量网络装机
IPTV直播列表
FRP穿透教程
文本三剑客之e`grep,seq文本编辑工具
树状数组(单点修改区间查询和区间修改单点查询)
Qt TreeView 问题记录
shell的脚本的基本用法
Oracle入门 09 - Linux 文件上传与下载
对称加密和非对称加密
网盘程序 ZFile安装
12.0 堆参数调优入门之GC收集日志信息
数据库原理作业2 — JMU
磁盘和储存管理
基本正则表达式元字符,字符,次数,锚定分组
DHCP原理与配置