信息学奥赛一本通T1340：树与二叉树 扩展二叉树
【题目描述】由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。现给出扩展二叉树的先序序列，要求输出其中序和后序序列。【输入】扩展二叉树的先序序列。【输出】输出其中序和后序序列。【输入样例】ABD..EF..G..C..【输出样例】DB
信息学奥赛一本通T1340：扩展二叉树
【题目描述】
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
【输入】
扩展二叉树的先序序列。
【输出】
输出其中序和后序序列。
【输入样例】
ABD..EF..G..C..
【输出样例】
DBFEGAC
DFGEBCA
【源程序】
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 101
#define MOD 123
#define E 1e-6
using namespace std;
typedef struct Node;
typedef Node *tree;
struct Node {
char data;
tree lchild, rchild;
};
tree bt;
int i = -1;
string s;
void build(tree &bt) //建树
{
if (s[++i] != '.') {
bt = new Node;
bt = new Node;
bt->data = s[i];
build(bt->lchild);
build(bt->rchild);
} else
bt = NULL;
}
void inorder(tree bt) //输出中序序列
{
if (bt) {
inorder(bt->lchild);
cout << bt->data;
inorder(bt->rchild);
}
}
void postorder(tree bt) //输出后序序列
{
if (bt) {
postorder(bt->lchild);
postorder(bt->rchild);
cout << bt->data;
}
}
int main() {
cin >> s;
build(bt);
inorder(bt);
cout << endl;
postorder(bt);
cout << endl;
return 0;
}
信息学奥赛一本通T1340：树与二叉树 扩展二叉树 归属于 树与二叉树，更多同类题解源程序见：树与二叉树 和 扩展二叉树
- 发表于 2020-05-11 10:20
- 阅读 ( 728 )
- 分类：信息学奥赛一本通
轩爸
0 篇文章
作家榜 »
-
admin
2 文章
-
张芳
0 文章
-
hanna
0 文章
-
Jason
0 文章
-
lixiaioqian
0 文章
-
GeraldWrora
0 文章
-
董伟
0 文章
-
信奥达人
0 文章
