UVA122 树的层次遍历 Trees on the level（两种方法详解）

UVA122 树的层次遍历 Trees on the level

输入：

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

输出：

5 4 8 11 13 4 7 2 1
not complete

//不管是左子树还是右子树，它们的父节点都是P/2;
以下内容来自《算法竞赛入门经典》

一、《算法竞赛入门经典》

方法一：结构体+指针

struct Node{
 bool have_value;//是否被赋值过,这个是针对本题要求设定的
 int v;//结点的值
 Node* left, *right;
 Node():have_value(false),left(NULL),right(NULL){}//构造函数
}*root;//二叉树的根结点

由于二叉树是递归定义的，其左右子结点类型都是“指向结点类型的指针”。换句话说， 如果结点的类型为Node，则左右子结点的类型都是Node *。

每次需要一个新的Node时，都要用new运算符申请内存，并执行构造函数。下面把申请 新结点的操作封装到newnode函数中：

Node* newnode() { return new Node(); }

还有这里lrj还提到了一个问题，当每次执行root=newnode()之后，之后这些内存就变成无法访问的内存垃圾了，因此最好写一个递归函数专门来清理这些内存。
下面是释清理内存的代码，请在“root = newnode()”之前加一 行

“remove_tree(root)”：
void remove_tree(Node* u) {  
   if(u == NULL) return;//提前判断比较稳妥  
   remove_tree(u->left);//递归释放左子树的空间
   remove_tree(u->right);//递归释放右子树的空间 
   delete u;//调用u的析构函数并释放u结点本身的内存 
}

方法二：数组+下标

首先还是给每个结点编号， 但不是按照从上到下从左到右的顺序，而是按照结点的生成顺序。用计数器cnt表示已存在的 结点编号的最大值，因此newnode函数需要改成这样：

const int root = 1;    
void newtree() { 
   left[root] = right[root] = 0; 
   have_value[root] = false; 
   cnt = root;
}    
int newnode() { 
   int u = ++cnt; 
   left[u] = right[u] = 0; 
   have_value[root] = false; 
   return u; 
}

上面的newtree()是用来代替前面的“remove_tree(root)”和“root = newnode()”两条语句的： 由于没有了动态内存的申请和释放，只需要重置结点计数器和根结点的左右子树了。 接下来，把所有的Node类型改成int类型，然后把结点结构中的成员变量改成全局数组 （例如，u->left和u->right分别改成left[u]和right[u]），除了char外，整个程序就没有任何指 针了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define debugs(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
const ll N=5e5+7;
const ll base=137;
const ll mod=2147483647;
template<typename T>inline T read(T &x)
{
    x=0;ll f=1;char c;
    while(!isdigit(c=getchar()))if(c=='-')f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
struct node
{
    ll v;//编号
    bool have_value;
    node *left,*right;
    node():have_value(false),left(NULL),right(NULL){}
};
ll v;
bool flag;
char s[N];
node *root;
node* newnode(){return new node();}
inline void remove_tree(node *p)
{
    if(p==NULL)return ;
    remove_tree(p->left);
    remove_tree(p->right);
    delete p;
}
inline bool bfs(vector<ll>&ans)
{
    ans.clear();
    queue<node*>q;
    q.push(root);
    while(!q.empty())//利用队列的先进先出来实现层序遍历
    {
        node*u=q.front();
        q.pop();
        if(!u->have_value)
            return false;
        ans.push_back(u->v);
        if(u->left!=NULL)
            q.push(u->left);
        if(u->right!=NULL)
            q.push(u->right);
    }
    return true;
}
inline void add_node(ll v,char *s)
{
    int len=strlen(s);
    node*u=root;
    for(int i=0;i<len;++i)
    {
        if(s[i]=='L'){
            if(u->left==NULL)
                u->left=newnode();
            u=u->left;
        }
        if(s[i]=='R'){
            if(u->right==NULL)
                u->right=newnode();
            u=u->right;
        }
    }
    if(u->have_value){flag=true;}
    u->v=v;
    u->have_value=true;
}
inline bool read_input()
{
    flag=false;
    remove_tree(root);
    root=newnode();
    for( ;; )
    {
        if(scanf("%s", s) != 1) {
            return false;
        }
        if(strcmp(s,"()") == 0) {
            break;
        }
        sscanf(&s[1],"%d",&v);
        add_node(v,strchr(s,',')+1);
    }
    return true;
}
int main()
{
    vector<ll>ans;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    while(read_input())
    {

        if(flag||!bfs(ans)){
            printf("not complete");
        }
        else {
            for(vector<ll>::iterator it=ans.begin();it!=ans.end();it++){
                if(it!=ans.end()-1)
                    printf("%lld ",*it);
                else printf("%lld",*it);
            }
        }
        puts("");
    }
    return 0;
}

二、利用STL超短代码

#include <iostream>
#include <string>
#include <map>
#include <queue>

using namespace std;

string OPT;
struct Node
{
    long long P, Num;
    Node(){}
    Node(long long X, long long Y) : P(X), Num(Y){}
    bool operator < (const Node &A) const
    {
        return P > A.P;//编号从小到大,原因在下面
    }
};
priority_queue <Node> Ans;//用来存已有的点
priority_queue <Node> OutPut;//用来输出的
map <long long, bool> Che;
//(long long)用来将表示位置的那一串转换成二进制,bool表示这个位置是否出现过

inline void WorkOut()
{
    long long i(1), Num(0), P(1);
    for (; OPT[i] != ','; ++i)Num = (Num << 1) + (Num << 3) + (OPT[i] ^ 48);//string转换成int
    ++i;
    for (; OPT[i] != ')'; ++i)OPT[i] == 'L' ? P = P << 1 : P = P << 1 | 1;//将LR的表示变成二进制,与线段树LSon = Root << 1, RSon = Root << 1 | 1比较类似,所以1是根节点
    Ans.push(Node(P, Num));
}

inline bool Check()
{
    Che[0] = 1;
    while (!Ans.empty())
    {
        if (!Che[Ans.top().P >> 1] || Che[Ans.top().P]) return 0;
        //如果没有爸爸,那这个树不能输出,这个位置有两个值,也不能输出
        Che[Ans.top().P] = 1;
        OutPut.push(Ans.top());
        Ans.pop();
    }
    return 1;
}

int main()
{
    while (cin >> OPT)
    {
        WorkOut();
        while (cin >> OPT && OPT.size() > 2)WorkOut();
        if (Check())
        {
            while (OutPut.size() > 1)//好像要卡空格,所以特殊处理一下
            {
                cout << OutPut.top().Num << ' ' ;
                OutPut.pop();
            }
            cout << OutPut.top().Num << endl ;
        }
        else cout << "not complete" << endl ;
        while (!OutPut.empty())OutPut.pop();//清空
        while (!Ans.empty())Ans.pop();//清空
        Che.clear();
    }
}