u013720139
天青晚雨
2016-05-22 12:04
采纳率: 66.7%
浏览 1.3k

二叉搜索树,一道简单的ACM为什么一直WA?

题目描述:
判断两序列是否为同一二叉搜索树序列

输入:
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。

输出:

如果序列相同则输出YES,否则输出NO

样例输入:

2
567432
543267
576342
0

样例输出:

YES
NO

#include
#include

struct Node {
int i;
Node *left;
Node *right;
}Tree[12];
int loc=0;
Node *create(){
Tree[loc].left=Tree[loc].right=NULL;
return &Tree[loc++];
}
Node *insert(Node *root,int a){
if(root==NULL)
{
root = create();
root->i = a;
return root;
}
else if(ai)root->left=insert(root->left,a);
else if(a>root->i)root->right=insert(root->right,a);
return root;
}

char ch1[10]={'\0',},ch2[10]={'\0',};
char ch1pre[10]={'\0',},ch1in[10]={'\0',},ch2pre[10]={'\0',},ch2in[10]={'\0',};
int count=0;
void preorder1(Node *root){
ch1pre[count++] = root->i+'0';
if(root->left!=NULL)preorder1(root->left);
if(root->right!=NULL)preorder1(root->right);
}
void preorder2(Node *root){
ch2pre[count++] = root->i+'0';
if(root->left!=NULL)preorder2(root->left);
if(root->right!=NULL)preorder2(root->right);
}

void inorder1(Node *root){

if(root->left!=NULL)inorder1(root->left);
ch1in[count++] = root->i+'0';
if(root->right!=NULL)inorder1(root->right);

}
void inorder2(Node *root){

if(root->left!=NULL)inorder2(root->left);
ch2in[count++] = root->i+'0';
if(root->right!=NULL)inorder2(root->right);

}

void clear(char c[]){
for(int i=0;i<10;i++){
c[i]='\0';
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)return 0;
clear(ch1in);
clear(ch1pre);
clear(ch1);
loc=0;
scanf("%s",ch1);
Node *n1=NULL;
for(int i=0;ch1[i]!='\0';i++){
n1 = insert(n1,ch1[i]-'0');
}
count=0;
preorder1(n1);
count=0;
inorder1(n1);
clear(ch2in);
clear(ch2pre);
clear(ch2);

while(n--){
loc=0;
scanf("%s",ch2);
Node *n2= NULL;
for(int j=0;ch2[j]!='\0';j++){

            n2 = insert(n2,ch2[j]-'0');
        }
        count=0;    
        preorder2(n2);
        count=0;
        inorder2(n2);
        bool b1 = strcmp(ch1pre,ch2pre);
        bool b2 = strcmp(ch1in,ch2in);
        if((b1==0)&&(b2==0))printf("%s\n","YES");
        else printf("%s\n","NO");
    }
}
return 0;

}



  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • QiaXi
    Valtava 2016-05-22 16:58

    没完全看明白楼主的思路。刚巧以前写过一个类似的,改了改放在这里,楼主可以参考下,希望能在思路上帮到你。

    #include <map>
    #include <iostream>
    #include <string>
    #include <vector>
    
    using std::cin;
    using std::cout;
    using std::endl;
    using std::map;
    using std::string;
    using std::vector;
    
    bool isSameTree(map<size_t,int>& tree, map<size_t, int>& anotherTree);
    void buildTree(vector<int>& dataVec, map<size_t, int>& builtTree);
    void generateVector(const string& inputs, vector<int>& generatedVec);
    
    int main()
    {
        const string booleanValueMap[2] = {"NO", "YES"};
        vector<bool> results;
    
        int iTreeAmount = 0;
        cin >> iTreeAmount;
        while(iTreeAmount != 0)
        {
            string tmpString;
            vector<int> tmpVector;
            map<size_t, int> originalTree;
            cin >> tmpString;
            generateVector(tmpString, tmpVector);
            buildTree(tmpVector, originalTree);
            for(int i=0; i!=iTreeAmount; ++i)
            {
                cin >> tmpString;
                map<size_t, int> newTree;
                generateVector(tmpString, tmpVector);
                buildTree(tmpVector, newTree);
                results.push_back(isSameTree(originalTree, newTree));
            }
    
            cin >> iTreeAmount;
        }
    
        for(vector<bool>::size_type i=0; i!=results.size();++i)
            cout << booleanValueMap[results.at(i)] << endl;
    
        return 0;
    }
    
    void buildTree(vector<int>& dataVec, map<size_t, int>& builtTree)
    {
        builtTree[0] = dataVec[0];
        for(vector<int>::size_type i=1;i!=dataVec.size();++i)
        {
            int iNewNumber = dataVec[i];
            size_t ulIndex = 0;
            while (builtTree.count(ulIndex))
            {
                if(iNewNumber > builtTree[ulIndex])
                    ulIndex = ulIndex * 2 + 2;
                else // as there are no identical numbers, it has to be iNewNumber < builtTree[ulIndex] here
                    ulIndex = ulIndex * 2 + 1;
            }
            builtTree[ulIndex] = iNewNumber;
        }
    }
    
    bool isSameTree(map<size_t,int>& oneTree, map<size_t, int>& anotherTree)
    {
        if(oneTree.size() != anotherTree.size())
            return false;
    
        for(map<size_t, int>::iterator itr=oneTree.begin();itr!=oneTree.end();++itr)
        {
            if(!anotherTree.count(itr->first))
    
                return false;
            else if(itr->second != anotherTree[itr->first])
                return false;
        }
    
        return true;
    }
    
    void generateVector(const string& inputs, vector<int>& generatedVec)
    {
        generatedVec.clear();
        for(string::size_type i=0;i!=inputs.size();++i)
        {
            generatedVec.push_back(inputs.at(i) - '0');
        }
    }
    
    
    点赞 评论

相关推荐