swust oj 983
2024-04-16 08:46:24
利用二叉树中序及后序遍历确定该二叉树的先序序列
1000(ms)
10000(kb)
2606 / 4908
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果，要求输出其先序遍历结果。
输入
第一行为中序序列
第二行为后续序列
输出
输出为遍历二叉树得到的先序序列
样例输入
BFDAEGC
FDBGECA
样例输出
ABDFCEG
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
typedef char Datetype;
using namespace std;
int x; typedef struct link{
Datetype date;
struct link *lchild;
struct link *rchild;
}tree; typedef struct queue{
tree *data;
struct queue *next;
}que; typedef struct {
que *front;
que *rear;
}lin; void Initqueue(lin *&L)
{
L=(lin *)malloc(sizeof(lin));
L->front=L->rear=NULL;
} void destroyed(lin *&L)
{
que *p=NULL,*r=NULL;
p=L->front;
while(p!=NULL)
{
r=p;
p=p->next;
free(r);
}
free(L);
} bool pop(lin *&L, tree *&e)
{
que *p;
if(L->rear==NULL)
return false;
p=L->front;
if(L->rear==L->front)
L->front=L->rear=NULL;
else
L->front=p->next;
e=p->data;
free(p);
return true;
} int empty(lin *&L)
{
return (L->rear==NULL);
} void push(lin *&L,tree *e)
{
que *p;
p = (que *)malloc(sizeof(que));
p->data=e;
p->next=NULL;
if(L->rear==NULL)
{
L->front=p;
L->rear=p;
}
else
{
L->rear->next=p;
L->rear=p;
}
} void creattree(tree *&L)
{
char c;
cin>>c;
if(c=='#')
L=NULL;
else
{
L = (tree *)malloc(sizeof(tree)) ;
L->date=c;
creattree(L->lchild);
creattree(L->rchild);
}
} void find(tree *L)
{
if(L!=NULL)
{
x++;
find(L->rchild);
}
} void destroytree(tree *&L)
{
if(L!=NULL)
{
destroytree(L->lchild);
destroytree(L->rchild);
free(L);
}
} int deep(tree *L)
{
int ldep,rdep,max;
if(L!=NULL)
{
ldep=deep(L->lchild);
rdep=deep(L->rchild);
max=ldep>rdep?ldep+:rdep+;
return max;
}
else
return ;
} void finddegree(tree *&L, int n)
{
if(L!=NULL)
{
if(x<n)
x=n;
finddegree(L->lchild,n);
finddegree(L->rchild,n+);
} } void run(tree *L)
{
tree *p=L;
lin *qu;
Initqueue(qu);
if(L!=NULL)
push(qu,p);
while(!empty(qu))
{
pop(qu,p);
cout<<p->date;
if(p->lchild!=NULL)
push(qu,p->lchild);
if(p->rchild!=NULL)
push(qu,p->rchild);
}
destroyed(qu);
} void displayhou(tree *&L)
{
if(L!=NULL)
{
displayhou(L->lchild);
displayhou(L->rchild);
cout<<L->date;
}
} void displaypre(tree *&L)
{
if(L!=NULL)
{
cout<<L->date;
displaypre(L->lchild);
displaypre(L->rchild);
}
} void creatinpre(tree *&L ,char *in,char *pre,int x)
{
int k=;
char *p;
if(x<=)
{
L=NULL;
return ;
}
L=(tree *)malloc(sizeof(tree));
L->date = *pre;
for(p=in ; p<in+x; p++)
{
if(*p==*pre)
break;
}
k=p-in;
creatinpre(L->lchild,in,pre+,k);
creatinpre(L->rchild,p+,pre+k+,x-k-);
} void creatinhou(tree *&L ,char *in,char *pre,int x)
{
int k=;
char *p;
if(x<=)
{
L=NULL;
return ;
}
L=(tree *)malloc(sizeof(tree));
L->date = *pre;
for(p=in ; p>in-x; p--)
{
if(*p==*pre)
break;
}
k=in-p;
creatinhou(L->rchild,in,pre-,k);
creatinhou(L->lchild,p-,pre-k-,x-k-);
} int main()
{
tree *L = NULL;
x=;
char in[],hou[];
cin>>in;
cin>>hou;
x=strlen(in);
creatinhou(L,in+x-,hou+x-,x);
displaypre(L);
destroytree(L);
return ;
}
最新文章
- js常用函数
- android开发------编写用户界面之线性布局
- Codeforces Round #247 (Div. 2)
- JS读写Cookie（设置、读取、删除）
- NodeJS Stream 三：readable
- C语言之linux内核--BCD码转二进制与二进制转BCD码（笔试经典）
- Linux时间同步问题
- JDK、JRE
- [转]Database Transactions in Laravel
- Java发送Email邮件及SpringBoot集成
- golang printf中的%c，%d，%u.都分别代表输出的是什么类型的？
- Python标示符和关键字
- angularjs的路由ui.router
- grunt搭建自动化的web前端开发环境（转）
- Linux 学习日记 2 (常用命令 + deb包的安装)
- UOJ 393 【NOI2018】归程——可持久化并查集
- 判断浏览器是ie9座特殊处理
- 构造函数constructor 与析构函数destructor（二）
- 【链表】Sort List（归并排序）
- java SE 入门之八大内置基本类型(第二篇)
热门文章
- CSS 水平垂直居中的几种实现方法
- [Android] Android RxJava2+Retrofit2+OkHttp3 的使用(一) --基础篇 Retrofit2 的使用
- [物理学与PDEs]第5章习题7 各向同性材料时稳定性条件的等价条件
- 同步Name到Comment 及 同步 Comment 到Name
- Django对于模型的数据操作
- 410 for 循环 运算 改变循环的控制流 死循环 遍历数组 定义方法 有名函数匿名函数 定义函数的方法取值 date math 局部变量 函数 局部与全局变量 次幂/随机数/取绝对值/向上取整/平方根
- PowerDesigner的Table视图同时显示Code和Name的方法[转发]
- codeforces 915E - Physical Education Lessons 动态开点线段树
- 【原创】大叔经验分享（3）hbase client 如何选择
- Nginx location 正则篇