uva 297 Quadtrees

题目意思：给定两个字符串，字符p对应建立子树，字符e为白色，f为黑色对于不同层黑点f对应不同的值，最上面为1024下来为每个子树256.....，这样建立两颗四叉树，计算两颗树相加后的黑点f对应的值，注意在两颗树上同一点处，只要有一个为黑点，那么相加后就为黑点

解题思路：1首先建立两颗树，采用递归建树的方法  2建完树后利用前序遍历的方法进行递归求解和

代码：

[cpp]
<span style="font-size:18px;">#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <string> 
#include <cstdlib> 
#include <deque> 
#include <algorithm> 
using namespace std; 
 
const int MAXN = 1000010;//定义一个常量 
 
//4叉树的结构体 
struct Btree{ 
    char c; 
    struct Btree *child[4];//四叉我们开个数组存储四个子树 
}; 
Btree *root1 , *root2;//两颗树的根节点 
char  str1[MAXN] , str2[MAXN];//存储读入的两串字符串 
int l1 , l2 , sum , pos; 
 
//4叉树的初始华 
void newnode(Btree *u){ 
    u -> c = 0; 
    for(int i = 0 ; i < 4 ; i++) 
        u -> child[i] = NULL; 
} 
 
//树的递归建立 
Btree* BuildTree(Btree *root , char *str){//返回Btree* 
    ++pos;//pos要为全局，注意递归的全局和局部变量区别 
    if(pos == strlen(str))//如果达到字符串末尾则返回NULL 
        return NULL; 
    root = new Btree;//每一New一个 
    newnode(root);//new出来要习惯初始化 
    root -> c = str[pos];//根节点的值为str[pos] 
    if(str[pos] == 'p'){//如果为p则建立子树，否则直接返回根节点就好 
        for(int i = 0 ; i < 4 ; ++i){ 
            if(root->child[i] == NULL){//如果哪个子树为空则递归产生子树 
                root->child[i] = BuildTree(root->child[i] , str);  
            } 
        } 
    } 
    return root; 
} 
 
//前序求和（同时遍历两颗树） 
void preorder(Btree *root1 , Btree *root2 , int level){ 
    if(root1 == NULL && root2 == NULL)//如果两颗树此时都为空则直接返回 
        return; 
    if(root1 == NULL){//树1为空时候 
        if(root2->c == 'f'){//如果当前树2的值为f要加上值1024>>(level*2) 
            sum += 1024>>(level*2);//位运算的使用 
            return;//为f   说明子树为空直接返回即可 
        } 
        for(int i = 0 ; i < 4 ; i++)//否则遍历子树2的四个方向 
            preorder(root1 , root2->child[i] , level+1); 
        return;//记得每一次都要返回 
    } 
    if(root2 == NULL){//同上 
        if(root1->c == 'f'){ 
            sum += 1024>>(level*2); 
            return; 
        } 
        for(int i = 0 ; i < 4 ; i++) 
            preorder(root1->child[i] , root2 , level+1); 
        return; 
    } 
    //如果此时要个都不为空只要有一个是f就要加上对应值 
    if(root1->c == 'f' || root2->c == 'f'){ 
        sum += 1024>>(level*2); 
        return;//返回上一层 
    } 
    for(int i = 0 ; i < 4 ; i++)//四个方向的遍历 
        preorder(root1->child[i] , root2->child[i] , level+1); 
}   www.2cto.com
 
//输入函数 
void solve(){ 
    pos = -1; 
    root1 = new Btree; 
    root2 = new Btree; 
    newnode(root1);//初始化 
    newnode(root2); 
    root1 = BuildTree(root1 , str1);//建树 
    root2 = BuildTree(root2 , str2);//建树 
    sum = 0; 
    preorder(root1 , root2 , 0); 
    printf("There are %d black pixels.\n" , sum); 
} 
//主函数 
int main(){ 
    int t; 
    scanf("%d" , &t); 
    while(t--){ 
        scanf("%s%s" , str1 , str2);//输入两串字符串 
        solve(); 
    } 
    return  0; 
} 
 
 
 
</span>