算法入门经典二叉树系列 UVO

灰太狼 2022-01-11 11:37 187阅读 0赞

首先是例题6.3.3层次遍历.

题意描述：

输入一颗二叉树，你的任务是按从上到下，从左到右的顺序输出各个节点的值。每个节点都按照从根节点到它的移动序列给出（L表示左，R表示右）。在输入中，每个节点的左括号之间没有空格，相邻节点之间用一个空格隔开。每棵树的输入用一对空括号（）结束（这对括号本身不代表一个结点），如图所示。

4 8

11 13 4

7 2 1

注意，如果从根到某个叶节点的路径上有的结点没有再输入中给出，或者给出了超过一次，应当输出-1.结点个数不超过256.

样例输入：

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

样例输出：

5 4 8 11 13 4 7 2 1

\-1

书上给的例程中对输入的字符串的处理运用的很巧妙，但是我就是感觉这样的话这个程序是错的，不会输出这样的结果，求大神指正，看程序中的这样一句：

if(scanf("%s",s)!=1)
                return 0;

他这句的意思就是输入一行字符串，否则返回0退出，但是后面用到的时候解释说是每次读入的是一个括号中的一部分，比如测试数据中的"(11,LL)",但是这句话不会起到只是每次读入括号中的部分吧。

求能实现这样只是读入括号中的部分的函数：

下面贴书上不返回运行结果的例程：

#include <iostream>
    #include <cstdio>
    #include <string.h>
    #include <cstdlib>
    using namespace std;
    #define Max 300
    struct Node
    {
        int have_value;
        int date;
        struct Node *left;
        struct Node *right;
    };
    
    Node *root;
    char s[Max];   //保存读入节点
    int failed;
    
    Node* newnode()   //创建节点并且分配内存
    {
        Node* u=(Node *)malloc(sizeof(Node));
        if(u != NULL)
        {
            u->have_value=0;
            u->left = u->right= NULL;
        }
        return u;
    }
    void addnode(int x,char *s)
    {
        Node *v=root;
        for(int i=0;i<strlen(s);i++)
        {
            if(s[i]=='L'){
                if(v->left==NULL) v->left = newnode();     //函数调用啊啊啊！！竟然忘记后面括号了、伤啊、、
                v = v->left;
            }
            if(s[i]=='R'){
                if(v->right==NULL) v->right = newnode();
                v=v->right;
            }
        }
        if(v->have_value) failed=1;
        v->date = x;
        v->have_value = 1;
    }
    void remove_tree(Node *u)  //释放内存
    {
        if(u==NULL) return;
        remove_tree(u->left);
        remove_tree(u->right);
        free(u);
    }
    
    int read_input()
    {
        failed=0;
        remove_tree(root);
        root=newnode();
        for(;;)
        {
            if(scanf("%s",s)!=1)
                return 0;
            if(!strcmp(s,"()"))
                break;
            int v;
            sscanf(&s[1],"%d",&v);
            addnode(v,strchr(s,',')+1);
        }
        return 1;
    }
    
    int n=0,ans[Max];
    int Bfs()
    {
        Node* q[Max];
        int count=0;
        int front=0,rear=1;
        q[0]=root;
        while(front<rear)
        {
            Node* u=q[count++];
            if(u->have_value==0) return 0;
            ans[n++]=u->date;
            if(u->left!=NULL) q[count++]=u->left;
            if(u->right!=NULL) q[count++]=u->right;
        }
        return 1;
    }
    
    
    
    int main()
    {
        read_input();
        Bfs();
        if(failed==1)
            cout<<"-1"<<endl;
        else
        for(int i=0;i<n;++i)
            cout<<ans[i]<<" ";
        system("pause");
        return 0;
    }
    /*
    (11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()
    (4,L)(4,R)()
    */