这题前边说了一堆废话
大意就是给出了一个二叉搜索树,但给出的方式比较奇怪,是删除叶子的顺序。 即把树上的叶子结点给出,然后揪掉这些叶子,把剩下的结点中变成叶子结点的再给出,这样一直到所有的结点都被揪掉。 最后要求这个二叉搜索树的先序遍历
这题解决的方式很简单,按照他给的那些东西,倒着建立二叉搜索树就行了。
为什么呢? 我们观察一下,可以发现,最后一个揪掉的一定是根节点,再往上,每一次揪掉的结点,之间一定是互相没有父子关系的。这是显然的。 而且所有的结点会先于他们的父亲结点被揪掉,这也是显然的。 那么倒序建二叉搜索树的时候,会跟原来的二叉搜索树是一样的,因为所有有父子关系的结点之间的相对位置没有变化。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 1000000000
using namespace std;
struct Tree
{
char c;
int lch, rch;
void init()
{
lch = rch = 0;
}
}tree[33];
char s[33][33];
int e;
void add(int u, char c)
{
if(c < tree[u].c)
{
if(!tree[u].lch)
{
tree[e].c = c;
tree[u].lch = e++;
}
else add(tree[u].lch, c);
}
else
{
if(!tree[u].rch)
{
tree[e].c = c;
tree[u].rch = e++;
}
else add(tree[u].rch, c);
}
}
void preorder(int u)
{
printf("%c", tree[u].c);
if(tree[u].lch) preorder(tree[u].lch);
if(tree[u].rch) preorder(tree[u].rch);
}
int main()
{
int cnt = 0;
while(scanf("%s", s[cnt++]) != EOF)
{
if(s[cnt - 1][0] == '*' || s[cnt - 1][0] == '$')
{
e = 0;
for(int i = 0; i < 30; i++) tree[i].init();
int n = cnt - 1;
tree[e++].c = s[n - 1][0];
for(int i = n - 2; i >= 0; i--)
{
int len = strlen(s[i]);
for(int j = 0; j < len; j++)
add(0, s[i][j]);
}
preorder(0);
printf("\n");
if(s[cnt - 1][0] == '$') break;
cnt = 0;
}
}
return 0;
}
分享到:
相关推荐
POJ 二叉搜索树 嘻嘻嘻 做的时候是一遍过好开心~~
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
NULL 博文链接:https://200830740306.iteye.com/blog/603493
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
北大POJ初级-简单搜索 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
数算的二叉树的POJ作业,分别有:二叉树1_二叉树的操作;二叉树2_文本二叉树;二叉树3_由中根序列和后根序列重建二叉树;二叉树4_表达式.表达式树....二叉树5_Huffman编码树;二叉树6_二叉搜索树;二叉树7_实现堆结构
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ题解 个人写法 线段树每个人都不一样
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
NULL 博文链接:https://128kj.iteye.com/blog/1704752
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告