当前位置:网站首页>Informatics Olympiad 1340: [example 3-5] extended binary tree
Informatics Olympiad 1340: [example 3-5] extended binary tree
2022-07-05 20:18:00 【Jun Yi_ noip】
【 Topic link 】
ybt 1340:【 example 3-5】 Expand the binary tree
【 Topic test site 】
1. Binary tree
【 Their thinking 】
solution 1:
use getchar() or cin.get() Read one character at a time .
The format of the preorder sequence is :< Root node > < The first sequence of the left subtree > < The precedence sequence of the right subtree >
A binary tree can be constructed recursively :
- Read in a character , As the root node
- Recursive construction of left subtree
- Recursively build the right subtree
- Connect the left and right subtrees under the root node of this tree , Return the address of the root node
After building the tree , Then output the middle order and post order traversal sequence of this tree .
【 Solution code 】
solution 1:
#include <bits/stdc++.h>
using namespace std;
struct Node// Binary tree node
{
char val;
int left, right;
};
Node node[1000];// Node pool
int p = 1;
void inOrder(int r)// In the sequence traversal
{
if(r != 0)
{
inOrder(node[r].left);
cout << node[r].val;
inOrder(node[r].right);
}
}
void postOrder(int r)// After the sequence traversal
{
if(r != 0)
{
postOrder(node[r].left);
postOrder(node[r].right);
cout << node[r].val;
}
}
int createTree(char val)// Pass in the value of the root of the binary tree to be generated , Returns the address of the generated binary tree
{
int np;
if(val == '.')
return 0;
else
{
np = p++;
node[np].val = val;
node[np].left = createTree(cin.get());// Read in character , Build the left subtree
node[np].right = createTree(cin.get());// Read in character , Build the right subtree
return np;
}
}
int main()
{
int root = createTree(cin.get());
inOrder(root);
cout << endl;
postOrder(root);
return 0;
}
边栏推荐
- y57.第三章 Kubernetes从入门到精通 -- 业务镜像版本升级及回滚(三十)
- About the priority of Bram IP reset
- Jvmrandom cannot set seeds | problem tracing | source code tracing
- 股票开户哪里好?网上客户经理开户安全吗
- 物联网智能家居基本方法实现之经典
- Debezium series: modify the source code to support UNIX_ timestamp() as DEFAULT value
- c语言oj得pe,ACM入门之OJ~
- leetcode刷题:二叉树13(相同的树)
- mongodb/文档操作
- CVPR 2022 | 常见3D损坏和数据增强
猜你喜欢
Convolution free backbone network: Pyramid transformer to improve the accuracy of target detection / segmentation and other tasks (with source code)
- Oui. Net Distributed Transaction and Landing Solution
[quick start of Digital IC Verification] 9. Finite state machine (FSM) necessary for Verilog RTL design
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
Leetcode skimming: binary tree 12 (all paths of binary tree)
【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
Leetcode skimming: binary tree 17 (construct binary tree from middle order and post order traversal sequence)
14. Users, groups, and permissions (14)
死信队列入门(两个消费者,一个生产者)
Leetcode brush questions: binary tree 11 (balanced binary tree)
随机推荐
Debezium series: idea integrates lexical and grammatical analysis ANTLR, and check the DDL, DML and other statements supported by debezium
Mysql频繁操作出现锁表问题
【c语言】快速排序的三种实现以及优化细节
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
js方法传Long类型id值时会出现精确损失
[quick start of Digital IC Verification] 7. Basic knowledge of digital circuits necessary for verification positions (including common interview questions)
【数字IC验证快速入门】1、浅谈数字IC验证,了解专栏内容,明确学习目标
死信队列入门(两个消费者,一个生产者)
C - sequential structure
点云文件的.dat文件读取保存
Flume series: interceptor filtering data
19 mongoose modularization
. Net distributed transaction and landing solution
C langue OJ obtenir PE, ACM démarrer OJ
IC科普文:ECO的那些事儿
2020 CCPC 威海 - A. Golden Spirit(思维),D. ABC Conjecture(大数分解 / 思维)
model方法
mongodb/文档操作
nprogress插件 进度条
Oracle tablespace management