#include <stdio.h>
#include <stdlib.h>

#define MAXID 1000000
#define MAXN 1000005
#define MAXL MAXN*10
#define MAXD 15

struct treenode {
    int id,numch;
    struct treenode* child[MAXD];
};

int nid;
int availid[MAXID+5];


struct treenode* generateTree(int branch, int depth) {
    struct treenode* root;
    int indexid,k,i;

    root = (struct treenode*)malloc(sizeof(struct treenode));

    indexid = rand()%nid;
    root->id = availid[indexid];
    availid[indexid] = availid[nid-1];
    nid--;

    k=rand()%branch+1;
    if (depth==0) k=0;

    for (i=0; i<k; i++) {
        root->child[i] = generateTree(branch,depth-1);
    }
    root->numch = k;
    return root;
}

void printTree(struct treenode* r) {
    int i;
    struct treenode* tmp;

    printf("%d ",r->id);
    if (r->numch == 0) return;

    for (i=0; i<r->numch; i++) {
        printf("(");
        printTree(r->child[i]);
        printf(") ");
    }
}

void permuteTree(struct treenode* r, int swaps) {
    int i,j,k,sw;
    struct treenode* tmp;

    k = r->numch;
    if (k>1) {
        for (sw=0; sw<swaps; sw++) {
            i = rand()%k;
            j = rand()%k;
            // swap children i and j
            tmp = r->child[i];
            r->child[i] = r->child[j];
            r->child[j] = tmp;
        }
    }
    for (i=0; i<k; i++) {
        permuteTree(r->child[i],swaps);
    }
}

int main() {
    int i;
    struct treenode* r;
    
    nid = MAXID;
    for (i=0; i<nid; i++) {
        availid[i] = i+1;
    }

    r = generateTree(2,20);
    printTree(r);
    printf("\n");
    permuteTree(r,10);
    printTree(r);
    printf("\n");
	
    return 0;
}