uva297 第一次又是runtime error 改了数组大小就AC了
大致思路是先建立两棵四叉树，然后相加得到新的四叉树，最后遍历新的四叉树统计出有多少个黑像素点。在相加的时候要注意剪枝，同一层黑像素块与其它相加最后肯定是黑像素块，空节点（白像素块）与其它任意节点相加无效果，还是的其它节点。只有parent加parent最复杂，需要递归调用函数将将其各自的四个子节点分别相加。统计黑像素点的时候也是递归求值，有一个技巧就是在全局建立一个数组存下每一层的像素数，比如0层时1024，一层是256...然后传递参数时加入depth参数，可以很轻松的进行递归计算。
会编二叉树后四叉树就不难了，开始建树的时候没有加入全局变量n统计已经建立了多少个节点，所以在递归几次返回第一层后会出现输入的字符不对的情况，因为这和给出前序遍历和中序遍历建树有所不同，他即给出了层次遍历节点的顺序，同时还给定了节点的类型，所以我的建树方法应该是最简单的。
代码如下
/*********************uva 297 *@author monkeyduck*@2013.10.24*Accpeted 22ms*********************/#include<iostream>using namespace std;class Node{public:int type;//标记类型，0为parent node，1为full，2为emptyNode* fch;Node* sch;Node* tch;Node* lch;};int n;//已建立节点的数目int expTable[6]={1024,256,64,16,4,1};//每一层格子的像素数Node* createNode(char* s)//递归建树{if (s[n]=='\0') return NULL;Node* pNode=new Node;if (s[n]=='p'){pNode->type=0;n++;pNode->fch=createNode(s);pNode->sch=createNode(s);pNode->tch=createNode(s);pNode->lch=createNode(s);}else if (s[n]=='f'){pNode->type=1;n++;}else{pNode->type=2;n++;}return pNode;}Node* treePlus(Node* rt1,Node* rt2)//两棵树相加{Node* nNode=new Node;if (rt1->type==1||rt2->type==1){nNode->type=1;return nNode;}else if(rt1->type==2&&rt2->type==2){nNode->type=2;return nNode;}else if (rt1->type==2&&rt2->type==0){nNode=rt2;return rt2;}else if (rt1->type==0&&rt2->type==2){return rt1;}else{nNode->type=0;nNode->fch=treePlus(rt1->fch,rt2->fch);nNode->sch=treePlus(rt1->sch,rt2->sch);nNode->tch=treePlus(rt1->tch,rt2->tch);nNode->lch=treePlus(rt1->lch,rt2->lch);return nNode;}}int count(Node* rt,int dep)//计算黑色格子数{if (rt->type==1){return expTable[dep];//dep表示该节点位于的层数，每一层的像素数是不同的}else if (rt->type==2) return 0;else{dep++;return count(rt->fch,dep)+count(rt->sch,dep)+count(rt->tch,dep)+count(rt->lch,dep);}}void clearNode(Node* rt)//释放节点{if (rt->type==1||rt->type==2) delete rt;else {clearNode(rt->fch);clearNode(rt->sch);clearNode(rt->tch);clearNode(rt->lch);}}int main(){int num;cin>>num;char* str=new char[2100];char* str2=new char[2100];while(num--){cin>>str;cin>>str2;Node* root1=new Node;Node* root2=new Node;Node* root3=new Node;n=0;root1=createNode(str);n=0;root2=createNode(str2);root3=treePlus(root1,root2);cout<<"There are "<<count(root3,0)<<" black pixels."<<endl;clearNode(root1);clearNode(root2);clearNode(root3);}delete[] str;delete[] str2;return 0;}