欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-02 22:16:34
...

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->leftu->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();
    }
}

相关标签: 树与二叉树