当前位置:网站首页>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;
}
边栏推荐
- js方法传Long类型id值时会出现精确损失
- 信息学奥赛一本通 1340:【例3-5】扩展二叉树
- Go language learning tutorial (XV)
- Ffplay document [easy to understand]
- Go language learning tutorial (16)
- leetcode刷题:二叉树10(完全二叉树的节点个数)
- selenium 元素信息
- Is it safe for CICC fortune to open an account online?
- Leetcode skimming: binary tree 16 (path sum)
- Codeforces Round #804 (Div. 2) - A, B, C
猜你喜欢
[quick start of Digital IC Verification] 1. Talk about Digital IC Verification, understand the contents of the column, and clarify the learning objectives
CTF reverse Foundation
PyTorch 1.12发布,正式支持苹果M1芯片GPU加速,修复众多Bug
零道云新UI设计中
关于BRAM IP复位的优先级
leetcode刷题:二叉树11(平衡二叉树)
Oracle-表空间管理
ROS2专题【01】:win10上安装ROS2
About the priority of Bram IP reset
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
随机推荐
nprogress插件 进度条
ROS2专题【01】:win10上安装ROS2
炒股开户最低佣金,低佣金开户去哪里手机上开户安全吗
解决php无法将string转换为json的办法
实操演示:产研团队如何高效构建需求工作流?
Schema和Model
.Net分布式事務及落地解决方案
Let's talk about threadlocalinsecurerandom
Introduction to dead letter queue (two consumers, one producer)
DP:树DP
死信队列入门(两个消费者,一个生产者)
selenium 元素信息
处理文件和目录名
Elk distributed log analysis system deployment (Huawei cloud)
sun. misc. Base64encoder error reporting solution [easy to understand]
Minimum commission for stock trading account opening, where to open an account with low commission? Is it safe to open an account on your mobile phone
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
Oracle tablespace management
Go language | 01 wsl+vscode environment construction pit avoidance Guide