#include "stdlib.h"
#include "stdio.h"
#define max 10
#define error 0
#define ok 1
typedef char elemtype;
//存储结构(数组)
struct PTNode
{
    elemtype data;
    int parent;
};

typedef struct PTree
{
    PTNode nodes[max+1];//0号不用
    int r;//根
    int n;//结点数
}*Tree;
//构造空树
void inittree(Tree &p)
{
    int i;
    p=(Tree)malloc(sizeof(PTree));
    if(!p) exit(1);
    for(i=1;i<=max;i++){
        p->nodes[i].data=NULL;
        p->nodes[i].parent=0;
    }
    p->n=0;
    p->r=0;
}

//销毁树
void destroytree(Tree &p)
{
    if(!p) exit(1);
    free(p);
}

//子树的结点数
int nodes(Tree &p,int cur_e)//cur_e为子树位置
{
    int i,count=1;
    if(p->nodes[cur_e].data==NULL&&p->nodes[cur_e].parent==0)
        return(0);
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e)
            count+=nodes(p,i);
    }
    return(count);
}




//清空子树
void cleartree(Tree &p,int cur_e)//cur_e为子树位置
{
    int i;
    p->nodes[cur_e].data=NULL;
    p->nodes[cur_e].parent=0;
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e)
            cleartree(p,i);
    }
    p->n=p->n-nodes(p,cur_e);
    if(cur_e==p->r)
        p->r=0;
}

//判断树空
bool emptytree(Tree &p)
{
    if(p->n==0) return(1);
    return(0);
}


//返回树的深度
int depthtree(Tree &p,int cur_e)//cur_e为子树位置
{
    int depth[max+1],i,depth_t;
    for(i=1;i<=max;i++)
        depth[i]=0;
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e)
            depth[i]=depthtree(p,i);
    }
    depth_t=depth[1];
    for(i=2;i<=max;i++){
        if(depth[i]>depth_t) depth_t=depth[i];
    }
    return(depth_t+1);
}

//返回根的位置
int roottree(Tree &p)
{
    if(!p) exit(1);
    return(p->r);
}

//返回结点的数据
elemtype value(Tree &p,int cur_e)
{
    return(p->nodes[cur_e].data);
}


//返回双亲的位置
int parent(Tree &p,int cur_e)
{
    return(p->nodes[cur_e].parent);
}

//返回孩子的位置
int * child(Tree &p,int cur_e,int &count)
{
    int * child_t,i,k=0;
    count=0;
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e) count++;
    }
    child_t=(int *)malloc(sizeof(int)*count);
    if(!child_t) exit(1);
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e) child_t[k++]=i;
    }
    return(child_t);
}

//返回兄弟的位置(同上)采用节约空间的办法 
int * sibling(Tree &p,int cur_e,int &count)
{
    int * sib_t,pare,i,k=0;
    count=0;
    pare=parent(p,cur_e);
    if(pare==-1) exit(1);//是根没有兄弟
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==pare&&i!=cur_e) count++;
    }
    sib_t=(int *)malloc(sizeof(int)*count);
    if(!sib_t) exit(1);
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==pare&&i!=cur_e) sib_t[k++]=i;
    }
    return(sib_t);
}

//遍历子树(先根)
void traverse1(Tree &p,int cur_e,void (*visit)(elemtype))//用打印
{
    int i;
    visit(p->nodes[cur_e].data);
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e)
            traverse1(p,i,visit);
    }
}




//遍历树(后根)
void traverse2(Tree &p,int cur_e,void (*visit)(elemtype))
{
    int i;
    for(i=1;i<=max;i++){
        if(p->nodes[i].parent==cur_e)
            traverse2(p,i,visit);
    }
    visit(p->nodes[cur_e].data);
}


//visit函数
void print(elemtype p)
{
    printf("%c  ",p);
}


//插入子树(必须配合实际情况)