完全二叉树

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB

Total submit users: 22, Accepted users: 18

Problem 10846 : No special judgement

Problem description

“树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只有左、右两个子树，如下图所示。 我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值，s代表从根节点到该节点的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。上图中值为13的节点用(13,RL)表示，值为2的节点用(2, LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值的按层次遍历序列（即先上层后下层、从左至右地遍历）。图1中的二叉树，其节点值的按层次遍历序列为：5, 4, 8, 11, 13, 4, 7, 2, 1。

Input

输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括号字符“()”标记，括号之内没有空格。

Output

针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描述的二叉树，则在新的一行中输出字符串“not complete”。

Sample Input

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

Sample Output

5 4 8 11 13 4 7 2 1 not complete

Judge Tips

注意树为空的情况

Problem Source

湖南省第二界程序设计大赛

解题报告：
 仔细找下规律，假如我们从根节点按层给二叉数节点从 1 开始编号
则对于题目给出的节点 (n,s) 的编号，我们有公式 i = pow(2,strlen(s))+fun(s)
其中 fun(s) 为将 L看做 0 ，R 看做 1 时对应的二进制串转为十进制后的值。
比如 (13,RL) 的编号为 pow(2,2)+fun(10) = 6。这样编号后，根据二叉树的性质我们
可以通过 m/2 很快找到它的父节点的编号。于是我们设一个 bool 型的数组gbFlag，该
数组记录在这种编号方式下，某个位置是否有节点的情况，若gbFlag[m]==true，表示编号
为 m 的位置有节点。若 m 位置有节点则它的父节点 gbFlag[m/2] 必须为 true 否则该二
叉树是不完备的。另外要注意仔细阅读题目，我因为这句“ 而且每个节点只被赋值一次 ”
没注意到，WA了一大片，这种情况是历史上最悲惨的 ！！！
本想用STL写，但是不知道 sort 函数怎样排序不是C++内置的数据类型。

///// 注意以下只能程序处理 log2(MAX_TEST) 层的二叉数，结点个数
///// 最多 400。 不受限制的方法留给读者思考。

#include <iostream>
#include <cmath>
#define MAX_TEST 1000000
using namespace std;

typedef struct node{
    int first,second;
}NODE;
NODE gNode[400];
bool gbFlag[MAX_TEST]={false},bFlag=false;

void mySet(int j, int& m,int& gN){
    if(gbFlag[j])
        bFlag = true;
    else{
        gbFlag[j] = true;
        gNode[gN].first = j;
        gNode[gN++].second = m;
    }
}

int myCmp(const void *a,const void *b){
    if(((NODE*)a)->first > ((NODE*)b)->first)
        return 1;
    else if(((NODE*)a)->first < ((NODE*)b)->first)
        return -1;
    return 0;
}

int main(){
    char buf[30],str[60];
    int i,j,m,gN=0,sum;
    while(cin>>str){
        if(!strcmp(str,"()")){
            if(!bFlag && gbFlag[1]){
                qsort(gNode,gN,sizeof(NODE),myCmp);
                for(i=1; i<gN; i++){
                    if(gbFlag[gNode[i].first] && !gbFlag[gNode[i].first>>1]){
                        cout<<"not complete"<<endl;
                        break;
                    }
                }
                if(i>=gN){
                    cout<<gNode[0].second;
                    for(i=1; i<gN; i++)
                        cout<<" "<<gNode[i].second;
                    cout<<endl;
                }
            }else
                cout<<"not complete"<<endl;
            for(i=0; i<gN; i++)
                gbFlag[gNode[i].first]=false;
            gN = bFlag =false;
        }
        else if(!bFlag){
            for(j=(int)strlen(str),i=1; str[i]!=','; i++)
                buf[i-1]=str[i];
            buf[i-1]='\0';
            m = atoi(buf);
            if(str[i+1]==')'){
                mySet(1,m,gN);
                continue;
            }
            sum = (int)pow((float)2,j-i-2);
            for(i=1,j-=2; str[j]!=','; j--,i<<=1){
                if(str[j]=='R')
                    sum+=i;
            }
            mySet(sum,m,gN);
        }
    }
    return 0;
}

评论