当前位置: 代码迷 >> 综合 >> POJ 1577 二叉搜索树
  详细解决方案

POJ 1577 二叉搜索树

热度:31   发布时间:2024-01-13 17:46:03.0

这题前边说了一堆废话 

大意就是给出了一个二叉搜索树,但给出的方式比较奇怪,是删除叶子的顺序。 即把树上的叶子结点给出,然后揪掉这些叶子,把剩下的结点中变成叶子结点的再给出,这样一直到所有的结点都被揪掉。 最后要求这个二叉搜索树的先序遍历

这题解决的方式很简单,按照他给的那些东西,倒着建立二叉搜索树就行了。

为什么呢?  我们观察一下,可以发现,最后一个揪掉的一定是根节点,再往上,每一次揪掉的结点,之间一定是互相没有父子关系的。这是显然的。  而且所有的结点会先于他们的父亲结点被揪掉,这也是显然的。  那么倒序建二叉搜索树的时候,会跟原来的二叉搜索树是一样的,因为所有有父子关系的结点之间的相对位置没有变化。


#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 < tr