#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 200000000;
typedef struct Tnode
{
    struct Tnode *parent;
    struct Tnode **node;
    int keynum,*key;
}Tnode;

typedef struct queuenode//构造队列结点
{
    Tnode *tnode;
    struct queuenode *next;
}queuenode;

typedef struct//构造队列
{
    queuenode *front;
    queuenode *rear;
}queue;

queue *initqueue(queue *q)
{
    q=(queue*)malloc(sizeof(queue));
    q->front=q->rear=(queuenode*)malloc(sizeof(queuenode));
    return q;
}

void pushqueue(queue *q,Tnode *rc)
{
    queuenode *temp;
    temp=(queuenode*)malloc(sizeof(queuenode));
    q->rear->tnode=rc;
    q->rear->next=temp;
    q->rear=q->rear->next;
}

Tnode *popqueue(queue *q)
{
    queuenode *temp;
    Tnode *rc;
    if(q->front==q->rear) return 0;
    else
    {
        temp=q->front;
        rc=q->front->tnode;
        q->front=q->front->next;
        free(temp);
    }
    return rc;
}

int emptyqueue(queue *q)
{
    if(q->front==q->rear) return 0;
    else return 1;
}

int insertkey(Tnode *temp,int inkey)//插入数字并修改孩子指针指向
{
    int i,k;
    k=i=0;
    if(temp->key[i]!=MAX)
    {
        temp->key[i]=inkey;
        temp->node[i++]=NULL;
        temp->node[i]=NULL;
    }   
    else
    {
        while(temp->key[i]!=MAX)//找到插入点
        {
            if(inkey>temp->key[i]) k=i+1;
            if(inkey==temp->key[i]) return -1;
            i++;
        }
        while(k!=i) //向后移动
        {
            temp->key[i]=temp->key[--i];
            temp->node[i]=temp->node[--i];
        }
        temp->node[k]=NULL;
        temp->key[k]=inkey;
    }
    temp->keynum++;
    return k;
}

Tnode *search(Tnode *root,int inkey)//搜索合适的插入结点
{
    Tnode *child;
    int i;
    i=0;
    child=root;
    while(child)
    {
        if(inkey>child->key[i]) i++;
        else
            if(inkey<child->key[i]) child=child->node[i];
            if(inkey==child->key[i]) break;
    }
    return child->parent;
}

Tnode *insert(Tnode *root,int inkey,int m)//插入数字
{
    Tnode *temp;
    int n;
    temp=root;
    if(!root)
    {
        root=(Tnode*)malloc(sizeof(Tnode));
        root->parent=NULL;
        root->node=(Tnode**)malloc(m*sizeof(Tnode*));
        root->key=(int*)malloc(m*sizeof(int));
        for(n=0;n<m;n++)
        {
            root->node[n]=(Tnode*)malloc(sizeof(Tnode));
            root->node[n]=NULL;
            root->key[n]=MAX;
        }
        root->key[0]=inkey;

    }
    else
    {
        temp=search(temp,inkey);
        n=insertkey(temp,inkey);
        if(temp->keynum<m) return temp;
        else  temp=fullchange(temp,m);
    }
    return temp;
}

Tnode *fullchange(Tnode *temp,int m)//结点分裂并修改孩子结点指针
{
    Tnode *pnode,*rnode;
    int i,s,k;
    pnode=rnode=NULL;
    if(!temp->parent)
    {
        pnode=(Tnode*)malloc(sizeof(Tnode));
        rnode=(Tnode*)malloc(sizeof(Tnode));
        pnode->node=(Tnode**)malloc(m*sizeof(Tnode*));
        rnode->node=(Tnode**)malloc(m*sizeof(Tnode*));
        pnode->key=(int*)malloc(m*sizeof(int));
        rnode->key=(int*)malloc(m*sizeof(int));
        for(i=0;i<m;i++)
        {
            pnode->node[i]=(Tnode*)malloc(sizeof(Tnode));
            rnode->node[i]=(Tnode*)malloc(sizeof(Tnode));
            pnode->key[i]=MAX;
            pnode->node[i]=NULL;
            rnode->key[i]=MAX;
            rnode->node[i]=NULL;
        }
        s=m/2;
        temp->parent=pnode;
        k=insertkey(pnode,temp->key[s]);
        pnode->node[1]=rnode;
        pnode->node[0]=temp;
        i=s+1;
        s=0;
        while(i<m)
        {
            insertkey(rnode,temp->key[i]);
            temp->key[i++]=MAX;
            rnode->node[s++]=temp->node[i];
            rnode->node[i]=NULL;
        }
    }
    else
    {
        rnode=(Tnode*)malloc(sizeof(Tnode));
        rnode->node=(Tnode**)malloc(m*sizeof(Tnode*));
        rnode->key=(int*)malloc(m*sizeof(int));
        for(i=0;i<m;i++)
        {
            rnode->node[i]=(Tnode*)malloc(sizeof(Tnode));
            rnode->node[i]=NULL;
            rnode->key[i]=MAX;
        }
        s=m/2;
        temp->parent=pnode;
        k=insertkey(pnode,temp->key[s]);
        pnode->node[k]=rnode;
        i=s+1;
        s=0;
        while(i<m)
        {
            k=insertkey(rnode,temp->key[i]);
            temp->key[i++]=MAX;
            rnode->node[s++]=temp->node[i];
            rnode->node[i]=NULL;
        }
        if(pnode->keynum>=m) pnode=fullchange(pnode,m);
    }
    return pnode;
}

void print(Tnode *root)//广度输出
{
    queue *q;
    Tnode *temp;
    int i;
    q=initqueue(q);
    temp=root;
    pushqueue(q,temp);
    while(emptyqueue(q))
    {
        for(i=0;i<temp->keynum;i++)
            printf("%d",temp->key[i++]);
        for(i=0;i<temp->keynum+1;i++)
            pushqueue(q,temp->node[i]);
    }
}

int getjieshu(int a)//得到树的阶数
{
    int i=0;
    while(1)
    {
        if(pow(2,i)-1>=a) i++;
        else
        {
            i--;
            break;
        }

    }
    return i;
}
void main()
{
    Tnode *root;
    int n,m,a;
    root=NULL;
    printf("关键字总个数:");
    scanf("%d",&a);
    m=getjieshu(a);
    printf("输入一组关键字(空格隔开):");
    while(a)
    {
        getchar();
        scanf("%d",&n);
        root=insert(root,n,m);
        a--;
    }
    print(root);
}
differs in levels of indirection from 'int ()' 这句没看懂..我照着意思改没改好.