当前位置:网站首页>信息学奥赛一本通 1340:【例3-5】扩展二叉树
信息学奥赛一本通 1340:【例3-5】扩展二叉树
2022-07-05 20:10:00 【君义_noip】
【题目链接】
【题目考点】
1. 二叉树
【解题思路】
解法1:
用getchar()或cin.get()每次读取一个字符。
先序序列的格式为:<根结点> <左子树的先序序列> <右子树的先序序列>
可以用递归的方法构建二叉树:
- 读入一个字符,作为根结点
- 递归构建左子树
- 递归构建右子树
- 将左右子树接在这棵树根结点的下面,返回根结点的地址
完成树的构建后,再输出这棵树的中序和后序遍历序列。
【题解代码】
解法1:
#include <bits/stdc++.h>
using namespace std;
struct Node//二叉树结点
{
char val;
int left, right;
};
Node node[1000];//结点池
int p = 1;
void inOrder(int r)//中序遍历
{
if(r != 0)
{
inOrder(node[r].left);
cout << node[r].val;
inOrder(node[r].right);
}
}
void postOrder(int r)//后序遍历
{
if(r != 0)
{
postOrder(node[r].left);
postOrder(node[r].right);
cout << node[r].val;
}
}
int createTree(char val)//传入要生成的二叉树的根的值,返回生成的二叉树的地址
{
int np;
if(val == '.')
return 0;
else
{
np = p++;
node[np].val = val;
node[np].left = createTree(cin.get());//读入字符,构建左子树
node[np].right = createTree(cin.get());//读入字符,构建右子树
return np;
}
}
int main()
{
int root = createTree(cin.get());
inOrder(root);
cout << endl;
postOrder(root);
return 0;
}
边栏推荐
- ICTCLAS用的字Lucene4.9捆绑
- Base du réseau neuronal de convolution d'apprentissage profond (CNN)
- Cocos2d-x项目总结中的一些遇到的问题
- leetcode刷题:二叉树10(完全二叉树的节点个数)
- Oracle-表空间管理
- SecureRandom那些事|真伪随机数
- Is it safe for Anxin securities to open an account online?
- Leetcode brush questions: binary tree 18 (largest binary tree)
- 【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
- Interviewer: what is the internal implementation of set data types in redis?
猜你喜欢
【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
计算lnx的一种方式
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
Leetcode brush question: binary tree 13 (the same tree)
Build your own website (16)
微信小程序正则表达式提取链接
Scala基础【HelloWorld代码解析,变量和标识符】
随机推荐
Is it safe for Galaxy Securities to open an account online?
leetcode刷题:二叉树14(左叶子之和)
How to select the Block Editor? Impression notes verse, notation, flowus
Debezium series: record the messages parsed by debezium and the solutions after the MariaDB database deletes multiple temporary tables
Leetcode skimming: binary tree 16 (path sum)
炒股开户最低佣金,低佣金开户去哪里手机上开户安全吗
国信证券在网上开户安全吗?
c语言oj得pe,ACM入门之OJ~
ICTCLAS用的字Lucene4.9捆绑
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
港股将迎“最牛十元店“,名创优品能借IPO突围?
【数字IC验证快速入门】1、浅谈数字IC验证,了解专栏内容,明确学习目标
无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
Parler de threadlocal insecurerandom
The difference between ID selector and class selector
深度學習 卷積神經網絡(CNN)基礎
[C language] three implementations of quick sorting and optimization details
2022年7月4日-2022年7月10日(ue4视频教程mysql)
Solve the problem that the database configuration information under the ThinkPHP framework application directory is still connected by default after modification
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023