当前位置:网站首页>二叉搜索树解决落叶问题
二叉搜索树解决落叶问题
2022-08-03 22:41:00 【chengqiuming】
一 原问题链接
Falling Leaves - POJ 1577 - Virtual Judgehttps://vjudge.net/problem/POJ-1577
二 输入和输出
1 输入
输入包含多个测试用例。每个测试用例都是一行或多行大写字母序列,每行都给出按上述步骤从二叉搜索树中删除的叶子,每行给出的字母都按字母升序排列。在测试用例之间以一行分隔,该行仅包含一个星号,在最后一个测试用例后给出一行,该行仅给出一个美元符号。在输入中没有空格或空行。
2 输出
对于每个测试用例,都有唯一的二叉搜索树,单行输出该树的先序遍历。
三 输入和输出样例
1 输入样例
BDHPY
CM
GQ
K
*
AC
B
$
2 输出样例
KGCBDHQMPY
BAC
四 算法设计
最后一个字母一定为树根,先输入的字母在树的深层,可以逆序建树。读入字母序列后用字符串存储,然后逆序创建二叉搜索树,将小的字母插入左子树,将大的字母插入右子树。输出该树的先序遍历:根,左子树,右子树。
五 代码
package poj1577;
import java.util.Scanner;
public class Poj1577 {
static int cnt = 1;
static data tree[] = new data[110];
static void insert(int t, char ch) {
if (tree[t].c == 0) {
tree[t].c = ch;
return;
}
if (ch < tree[t].c) {
if (tree[t].l == 0) {
tree[++cnt].c = ch;
tree[t].l = cnt;
} else
insert(tree[t].l, ch);
}
if (ch > tree[t].c) {
if (tree[t].r == 0) {
tree[++cnt].c = ch;
tree[t].r = cnt;
} else
insert(tree[t].r, ch);
}
}
static void preorder(int t) {
if (tree[t].c == 0)
return;
System.out.print(tree[t].c);
preorder(tree[t].l);
preorder(tree[t].r);
}
public static void main(String[] args) {
String s1, s;
while (true) {
s = "";
for (int i = 0; i < tree.length; i++) {
tree[i] = new data();
}
Scanner scanner = new Scanner(System.in);
while (true) {
s1 = scanner.next();
if (s1.charAt(0) != '*' && s1.charAt(0) != '$') {
s += s1;
} else {
break;
}
}
for (int i = s.length() - 1; i >= 0; i--)
insert(1, s.charAt(i));
preorder(1);
System.out.println();
if (s1.charAt(0) == '$')
break;
}
}
}
class data {
int l;
int r;
char c;
}
六 测试
绿色为输入,白色为输出。
边栏推荐
猜你喜欢
藏宝计划TreasureProject(TPC)系统模式开发技术原理
中国企业构建边缘计算解决方案的最佳实践
Network basic learning series four (network layer, data link layer and some other important protocols or technologies)
Data_web(九)mongodb增量同步到mongodb
override学习(父类和子类)
Summary bug 】 【 Elipse garbled solution project code in Chinese!
21天打卡挑战学习MySQL——《Window下安装MySql》第一周 第三篇
"Digital Economy Panorama White Paper" Financial Digital User Chapter released!
静态文件快速建站
《数字经济全景白皮书》金融数字用户篇 重磅发布!
随机推荐
Shell编程的条件语句
投资性大于游戏性 NFT游戏到底是不是门好生意
for loop exercises
Quickly build a website with static files
使用tf.image.resize() 和tf.image.resize_with_pad()调整图像大小
Network basic learning series four (network layer, data link layer and some other important protocols or technologies)
重发布实验报告
2022/8/3 考试总结
Diazo Biotin-PEG3-DBCO | Diazo Compound Modified Biotin-Tripolyethylene Glycol-Dibenzocyclooctyne
剑指offer第22题-链表中倒数第K个节点
L2-029 特立独行的幸福
Summary bug 】 【 Elipse garbled solution project code in Chinese!
Gains double award | know micro easily won the "2021 China digital twin solution suppliers in excellence" "made in China's smart excellent recommended products" double award!
HCIP BGP实验报告
Take an example of a web worker
Websocket multi-threaded sending message error TEXT_PARTIAL_WRITING--Use case of spin lock replacing synchronized exclusive lock
for循环练习题
log4j-slf4j-impl cannot be present with log4j-to-slf4j
Basic Concepts of Graphs
How to write a database document management tool based on WPF (2)