栅格数据的四叉树编码

指针四叉树代码如下（最简单的递归实现）：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 64 + 5;
char g[maxn][maxn];
int n, k[10] = { 1 };
vector<int>a;

int solve_g(int l,int r,int u,int d,int cur,int p){
    int w = 1, b = 1;
    for(int i = u; i <= d; i++){
        if(!w && !b) break;
        for(int j = l; j <= r; j++){
            if(g[i][j] == '1') w = 0;
            else b = 0;
        }
    }
    if(w || b) return b ? cur : -1;
    int x = (l+r)/2, y = (u+d)/2, t;
    if((t = solve_g(l,x,u,y,cur + k[p],p+1)) > -1) a.push_back(t);
    if((t = solve_g(x+1,r,u,y,cur + 2*k[p],p+1)) > -1) a.push_back(t);
    if((t = solve_g(l,x,y+1,d,cur + 3*k[p],p+1)) > -1) a.push_back(t);
    if((t = solve_g(x+1,r,y+1,d,cur + 4*k[p],p+1)) > -1) a.push_back(t);
    return -1;
}

void solve_a(int a){
    int l = 0, r = n-1, u = 0, d = n-1;
    while(a){
        int x = (l + r) / 2, y = (u + d) / 2;
        switch(a % 5){
            case 1: r = x; d = y; break;
            case 2: l = x + 1; d = y; break;
            case 3: r = x; u = y + 1; break;
            case 4: l = x + 1; u = y + 1; break;
        }
        a /= 5;
    }
    for(int i = u; i <= d; i++){
        for(int j = l; j <= r; j++){
            g[i][j] = '*';
        }
    }
}

int main(){
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    for(int i = 1; i<10; ++i) k[i] = k[i-1]*5;
    int cnt = 0,t;
    while(scanf("%d",&n),n){
        if(cnt) printf("\n");
        printf("Image %d\n",++cnt);
        a.clear();
        memset(g,0,sizeof(g));
        if(n > 0){
            getchar();
            for(int i = 0; i<n; ++i) fgets(g[i],maxn-1,stdin);
            if((t = solve_g(0,n-1,0,n-1,0,0)) > -1) a.push_back(t);
            sort(a.begin(),a.end());
            int len = a.size();
            for(int i = 0; i < len;){
                printf("%d",a[i++]);
                if(i%12 == 0 || i == len) printf("\n");
                else printf(" ");
            }
            printf("Total number of black nodes = %d\n",len);
        }
        else{
            n = -n;
            while(1){
                scanf("%d",&t);
                if(t < 0) break;
                solve_a(t);
            }
            for(int i = 0; i < n; ++i){
                for(int j = 0; j<n; ++j)
                    if(!g[i][j]) g[i][j] = '.';
                puts(g[i]);
            }
        }
    }
    return 0;
}

线性四叉树（Morton码）：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 5;
const int n = 15;
char graph[maxn][maxn];
char zip_graph[maxn*maxn];
int zip_record[maxn*maxn];

int Morton_encode(int i,int j){
    int code = 0;
    for(int k = 0;k < n;k++){
        code |= ((i>>k)&1)<<(k*2);
        code |= ((j>>k)&1)<<(k*2+1);
    }
    return code;
}
int build_tree(int l){
    for(int i = 0;i < l;i++){
        for(int j = 0;j < l;j++){
            zip_graph[Morton_encode(j,i)] = graph[i][j];
        }
    }
    int t = l*l;
    int i = 0,j = 0;
    while(i < t){
        int k = i+1;
        while(zip_graph[i] == zip_graph[k]) k++;
        zip_record[j++] = i;
        i = k;
    }
    return j;
}
int main(){

    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    scanf("%s",graph[0]);
    int l = strlen(graph[0]);
    for(int i = 1;i < l;i++){
        scanf("%s",graph[i]);
    }
    int n = build_tree(l);
    for(int i = 0;i < n;i++) printf("%d\t",zip_record[i]);
    putchar('\n');
    for(int i = 0;i < n;i++) printf("%c\t",zip_graph[zip_record[i]]);

    return 0;
}