下面有我粘出来的代码,请大牛出手相助！
树T：
4 R
R ABC
A DE
B ^
C F
D ^
E ^
F GHK
G ^
H ^
K ^
新树t：
4 0
0 123
1 ^
2 ^
3 45
4 ^
5 ^
//将t插入T中，t中的每个结点的孩子结点最终在树中的位置都是颠倒的
//如t中：根结点0的三个孩子结点为123，但是插入后顺序变为321
typedef int status;
typedef char TElemType_C;
typedef struct CTNode //孩子结点
{
int child;//第一个孩子在数组中得位置
struct CTNode *next; //指向下一个用于存储孩子位置的空间的地址
}CTNode,*ChildPtr;
typedef struct
{
int parent; //结点双亲的位置
TElemType_C data; // 结点数值
ChildPtr firstchild; //孩子链表头指针
}CTBox;
typedef struct
{
CTBox nodes[MAX_TREE_SIZE];
int r; //根的位置
int n; //树的结点数
}CTree;
void InitTree_C(CTree *T) //操作结果：录入根结点的位置
{ // 结点数置为 0
int i;
printf("录入根结点的位置(非负数):");
scanf("%d",&i);
getchar();
if(iMAX_TREE_SIZE-1)// 0<=i<=MAX_TREE_SIZE-1
{
printf("i 值错误!\n");
exit(ERROR);
}
T->r=i;
T->n=0;
printf("初始化成功!\n");
}
void FreeChild_C(ChildPtr *p) //删除孩子链表
{
ChildPtr q;
while(*p)
{
q=(*p)->next;
free(*p);
*p=q;
}
}
void ClearTree_C(CTree *T)
{
}
status TreeEmpty_C(CTree T)
{
return T.n?FALSE:TRUE;
}
status CreatTree_C(CTree *T)
{
TElemType_C ch,data;//虽然结构里也有一个data变量，但是两者不冲突,因为辨识度高：用结构中的data是一个结构成员,(会用到'.'或'->')
int i; // i标记当前结点的父结点的位置
int j; // j标记当前结点位置
int k; // k标记i结点第一个孩子位置
ChildPtr p,q;
printf("录入树的根结点:");
scanf("%c",&ch);
getchar();
if(ch!='^')
{
i=T->r; //注意根结点的设置
T->nodes[i].parent=-1; //根结点的存储
T->nodes[i].data=ch;
T->nodes[i].firstchild=NULL;
T->n++;
if(i!=0) // 第二个结点位置的确定
j=0;
else
j=1;
k=j;
while(ch!=T->nodes[T->n-1].data)
{
scanf("%c",&ch);
getchar();
printf("依次录入 %c 的孩子的结点->",ch);
p=q=NULL;
while(1)
{
scanf("%c",&data);
// getchar();
if(data=='^'||data=='\n')
{
if(data=='^')
{
getchar();
}
break;
}
else
{
T->nodes[j].data=data;
T->nodes[j].parent=i;
T->nodes[j].firstchild=NULL;
T->n++;
p=(ChildPtr)malloc(sizeof(CTNode));
if(!p)
exit(OVERFLOW);
p->child=j;
p->next=NULL;
if(T->nodes[i].firstchild==NULL)
T->nodes[i].firstchild=p;
else
q->next=p;
q=p;
}
if(j+1==T->r)
j=j+2;
else
j++;
}//while(1)
i=k;
if(k+1==T->r)
k=k+2;
else
k++;
} //while(ch!=T->node[T->n-1].data)
}//if
}
status TreeDegree_C(CTree T)
{
int sub;//数组的下标
ChildPtr p;
int maxdegree=0;//树的度
int degree=0;//每个结点的度
for(sub=0;sub {
if(T.nodes[sub].firstchild==NULL)
degree=0;
else
{
p=T.nodes[sub].firstchild;
while(p)
{
degree++;
p=p->next;
}
}
if(degree>maxdegree)
maxdegree=degree;
}
return maxdegree;
}
status TreeDepth_C(CTree T)
{
int pos;//结点双亲在数组中的位置
int depth=0;//树的深度
int end;//最后一个结点在数组中的位置
if(T.n)
{
if(T.n==1)
end=T.r;
else
{
if(T.r<T.n-1)
end=T.n-1;
else
end=T.n-2;
}
depth++;
pos=T.nodes[end].parent;
while(pos!=-1)
{
depth++;
pos=T.nodes[pos].parent;
}
}
return depth;
}
TElemType_C Root_C(CTree T)
{
return T.n? T.nodes[T.r].data:'\0';
}
TElemType_C Value_C(CTree T,int i)
{
if(T.n &&i>0&& i<=T.n)
{
if(i==1)
return T.nodes[T.r].data;
else
{
if(i>T.r)
return T.nodes[i-1].data;
else
return T.nodes[i-2].data;
}
}
}
status Order_C(CTree T,TElemType_C e)//操作结果：返回e结点在数组中的下标
{ // 若该结点不存在,则返回 -1
int sub;//数组的下标
for(sub=0;sub {
if(T.nodes[sub].data==e)
return sub;
}
return -1;//该结点不存在
}
void Assign_C(CTree *T,TElemType_C e,TElemType_C value)
{
int sub;
if(T->n)
{
sub=Order_C(*T,e);
if(sub>=0)
T->nodes[sub].data=value;
else
printf("该结点不存在!\n");
}
}
TElemType_C ChildValue_C(CTree T,TElemType_C e,int order)
{
int sub;//结点e在数组中的下标
int count;
ChildPtr p;
if(T.n)
{
sub=Order_C(T,e);
if(sub>=0)
{
count=0;
p=T.nodes[sub].firstchild;
while(p)
{
count++;
if(count==order)
break;
else
p=p->next;
}
if(p)
return T.nodes[p->child].data;
}
}
return '\0';
}
TElemType_C Sibling_C(CTree T,TElemType_C e,int mark) // 0 为左兄弟
{ // 1 为右兄弟
int sub;//结点在数组中的下标
int pos;//结点双亲的位置
ChildPtr p;
if(T.n)
{
sub=Order_C(T,e);//结点在数组中的下标
if(sub>=0&&sub!=T.r)//结点存在并且不为根结点
{
pos=T.nodes[sub].parent; //找到双亲的位置
p=T.nodes[pos].firstchild;
while(p)
{
if(mark==0) //寻找左兄弟
{
if(p&&p->next&&p->next->child==sub)
return T.nodes[p->child].data;
}
if(mark==1)//寻找右兄弟
{
if(p&&p->child==sub&&p->next)
return T.nodes[p->next->child].data;
}
p=p->next;
}
}
}
return '\0';
}
status ChildCount_C(CTree T,TElemType_C e)
{
int sub;//数组下标
int count;//结点的孩子个数
ChildPtr p;
count=Order_C(T,e);
if(count return -1;
if(T.n==0)
return -1;
count=0;
if(T.n)
{
sub=Order_C(T,e);//结点在数组中的位置
p=T.nodes[sub].firstchild;//结点的第一个孩子的地址
if(sub>=0)//结点存在判定
{
while(p)
{
count++;
p=p->next;
}
}
}
return count;
}
/*****************************************************************************************************
返回树T中结点e的第i个孩子(层序计数)的位置，i=0定义为最后一个孩子
思想：先get结点的第i个孩子在数组中的下标值 若大于根结点在数组中的下标值，return其值加一
若小于根结点在数组中得下标值，return其值加二
不存在等于等结点得情况
层序计数，就是在数组中位置的下一个位置，在本程序中，下一个若是根结点则跳过
******************************************************************************************************/
status ChildSeat_C(CTree T,TElemType_C e, int i)
{
int k0,k1,k2,j,m;
int count;
k0=ChildCount_C(T,e);
if(k0<0||i<0)
return -2;
if(k0==0&&i!=0||k0!=0&&i>k0)
i=0;
if(i==0)
j=k0+1;
else
j=i+1;
k1=Order_C(T,e);
if(k1==T.r)
{
k2=count=0;
while(1)
{
if(k2==T.r)
k2++;
count++;
if(count==j)
{
break;
}
k2++;
}
}
else
{
m=0;
while(1)
{
if(m==T.r)
m++;
if(T.nodes[m].parent==T.r)
m++;
else
break;
}
k2=m;
count=0;
while(k2<T.n-1)
{
if(k2==T.r)
k2++;
else
{
if(T.nodes[k2].parent>=k1)
count++;
if(count==j)
break;
k2++;
}
}
if(k2==T.n-1)
{
if(T.r>=T.n-1)
k2=T.n;
if(T.r<T.n-1)
{
if(T.nodes[k2].parent>=k1)
count++;
if(count!=j)
k2=T.n;
}
}
}
return k2;
}
ChildPtr SiblingSeat_C(CTree T,TElemType_C e)
{
int sub;//结点在数组中的位置
int pos;//结点双亲在数组中的位置
ChildPtr p;
if(T.n)
{
sub=Order_C(T,e);
if(sub>=0)
{
pos=T.nodes[sub].parent;
p=T.nodes[pos].firstchild;
while(p)
{
if(p&&p->child==sub)
return p;
else
p=p->next;
}
}
}
return NULL;
}
/**************************************************************************************************************************
思路：1,从p结点得第i个孩子(层序计数)的位置开始,向后移动一位【根结点不移动】
2,修改移动了的孩子链表的child
3,将插入的结点放入其双亲的孩子链表中
注意:1,由于根结点是经过初始化赋予的值，所以，根结点在数组中的位置不变
2,由于根结点是经过初始化赋予的值，所以，其位置是在合法范围的任意位置，可能与其它非根结点在一起，也可能孤立在一个位置
****************************************************************************************************************************/
status InsertChild_C(CTree *T,TElemType_C p,int i,TElemType_C e)
{
int pos;//结点第i个孩子(层序计数)的位置
int j;//第三步插入位置的前一个结点(孩子链表)
int pre;
int later;
int num;//用于第二步的遍历修改结点的孩子链表链表的child
ChildPtr ptr;//用于第三步的寻找链表的插入位置
ChildPtr Cptr;//结点孩子链表的指针
if(T->n)
{
pos=ChildSeat_C(*T,p,i);
if(pos return ERROR;
//sub=Order_C(*T,p);
if(pos>=1)
{
if(T->rn)//根结点与其它结点聚在一起
{
later=T->n;
pre=T->n-1;
}
else//根结点独立
{
later=T->n-1;
pre=T->n-2;
}
while(later>pos)//执行的第一步,并空出结点插入的位置
{
if(pre==T->r)
pre--;
if(T->nodes[pre].parent T->nodes[later].parent=T->nodes[pre].parent;
else
{
if(T->nodes[pre].parent+1==T->r)//当其父母结点在数组中的位置的下一个位置是根结点时,须跳过根结点
T->nodes[later].parent=T->nodes[pre].parent+2;
else
T->nodes[later].parent=T->nodes[pre].parent+1;
}
T->nodes[later].data=T->nodes[pre].data;
T->nodes[later].firstchild=T->nodes[pre].firstchild;
later--;
if(later==T->r)
later--;
pre--;
}
T->nodes[pos].data=e;
T->nodes[pos].parent=Order_C(*T,p);
T->nodes[pos].firstchild=NULL;
T->n++;
num=0;
while(num<T->n-1||(num==T->n-1 && T->r<T->n))//执行第二步,修改移动了的孩子链表的child
{
ptr=T->nodes[num].firstchild;
while(ptr)
{
if(ptr->child>=pos)
{
if(ptr->child+1==T->r)
ptr->child=ptr->child+2;
else
ptr->child++;
}
ptr=ptr->next;
}
num++;
}
if(T->r>T->n-1)
{
ptr=T->nodes[T->r].firstchild;
while(ptr)
{
if(ptr->child>=pos)
{
//if(ptr->child+1==T->r)
// ptr->child=ptr->child+2;
//else
ptr->child++;
}
ptr=ptr->next;
}
}
ptr=(ChildPtr)malloc(sizeof(CTNode));//待插入结点的链表结点的创建
if(!ptr)
exit(OVERFLOW);
ptr->child=pos;
ptr->next=NULL;
if(i==0)
j=ChildCount_C(*T,p)+1;
else
j=i;
if(j=1)
{
Cptr=T->nodes[Order_C(*T,p)].firstchild;//第三步,一定不为NULL，因为插入的是结点的孩子的后面
if(Cptr)
{
ptr->next=Cptr->next;
Cptr->next=ptr;
}
}
else
{
Cptr=SiblingSeat_C(*T,ChildValue_C(*T,p,j-1));
ptr->next=Cptr->next;
Cptr->next=ptr;
}
}
}
/*************************************************************
测试代码:
int test;
for(test=0;testn;test++)
{
printf("node[%d]=%c ",test,T->nodes[test].data);
printf("双亲位置为:%d\n",T->nodes[test].parent);
}
printf("T.n=%d\n",T->n);
ChildPtr two;
for(test=0;test<T->n;test++)
{
two=T->nodes[test].firstchild;
printf("输出node[%c]的孩子链表:",T->nodes[test].data);
while(two)
{
printf("%d ",two->child);
two=two->next;
}
if(two==NULL)
printf("\n");
}
****************************************************************/
return OK;
}
status InsertTree_C(CTree *T,TElemType_C p,int i,CTree t)
{
int k;
int end;
//ChildPtr h,q,l;
if(TreeEmpty_C(*T)||TreeEmpty_C(t))
return ERROR;
if(t.r>=t.n-1)
end=t.n-2;
else
end=t.n-1;
InsertChild_C(T,p,i,t.nodes[t.r].data);//先将t的根结点插入到T中
//
int test6;
//
for(k=0;k<=end;k++)
{
if(k==t.r)
k++;
InsertChild_C(T,t.nodes[t.nodes[k].parent].data,0,t.nodes[k].data );
printf("测试行：........................\n");
printf("输出%c结点的第%d个孩子(层序计数)的位置:%d\n",t.nodes[t.nodes[k].parent].data,0,ChildSeat_C(*T,t.nodes[t.nodes[k].parent].data,0));
for(test6=0;test6<T->n ;test6++)
{
printf("node[%d]=%c ",test6,T->nodes[test6].data);
printf("双亲位置为:%d\n",T->nodes[test6].parent);
}
printf("T.n=%d\n",T->n);
printf("测试行结束........................\n");
}
return OK;
}
/**********************************************************************************
思路：1.先修改e结点的第i个孩子的双亲的孩子链表【删去孩子链表中该结点的位置】
2.若该结点有孩子结点那么，释放该结点子树中所有结点的孩子链表
3.将以该结点为根结点的树中结点的data全部置为'\0'
并记下置为'\0'的结点总数，用于修改T.n;
4.从前先后移动位置，两个int变量且都从0开始，之后遇到'\0'时，一个++，另一个不变，
即一个在前边探寻非'\0'的结点，另一个标志将要存入的位置
5.修改结点的双亲的值，及孩子链表的child域。
***********************************************************************************/
status DeleteTree_C(CTree *T,TElemType_C e,int i)
{
int k0;//结点e在数组中的位置
int k1;//e结点的第i个孩子在数组中的位置
int count;//
int sub=0;//数组order的下标
int n;//遍历找结点的孩子结点
int k2=0;
ChildPtr h,q,t;
int order[MAX_TREE_SIZE];//用于记录树的位置
int x,y;
k0=Order_C(*T,e);
if(k0>=0)
{
count=0;
h=T->nodes[k0].firstchild;
while(h)
{
count++;
if(count==i)
break;
h=h->next;
}
if(h)//不是自然退出
{
k1=h->child;
q=T->nodes[k0].firstchild;
if(q->child==k1)
{
t=q;
q=t->next;
}
else
{
while(q->next->child!=k1)
q=q->next;
t=q->next;
q->next=t->next;
}
free(t);//释放e结点的孩子链表中的该结点
t=NULL;
//T->nodes[k1].data='\0';
order[sub]=k1;//将以e结点的第i个孩子的树中的每个结点在数组中的位置存储在数组order中
while(k2<=sub)
{
for(n=order[k2]+1;n<T->n;n++)
{
if(T->nodes[n].parent==order[k2])
order[++sub]=n;
}
k2++;
}
for(k2=0;k2<=sub;k2++)//释放以e结点的第i个孩子为根的树的所有孩子链表
{
T->nodes[order[k2]].data='\0';//将以e结点的第i个孩子为根的树的中的data全部置为'\0'
FreeChild_C(&T->nodes[order[k2]].firstchild);
}
x=-1;
y=0;
count=1;//if，T->r<T->n,虽然表面上进行了n-1次循环,由于跳过了根的位置，所以实际上相当于进行了n次循环
//else,进行n-1次循环，由于根结点不跟其它结点聚在一起所以不用跳过根结点，恰好操作完成所有要移动的结点
while(count<T->n)//移位置，取代'\0'位
{
if(y==T->r)
y++;
if(T->nodes[y].data)
{
x++;
if(x==T->r)
x++;
T->nodes[x].data=T->nodes[y].data;
T->nodes[x].parent=T->nodes[y].parent;
T->nodes[x].firstchild=T->nodes[y].firstchild;
order[y]=x;//记录删除树后结点在数组中的位置
}
y++;
count++;
}
order[T->r]=T->r;
count=1;
x=0;
T->n-=sub+1;
while(count<T->n)//纠正双亲结点和孩子结点位置
{
if(x==T->r)
x++;
T->nodes[x].parent=order[T->nodes[x].parent];
if(T->nodes[x].firstchild)
{
t=T->nodes[x].firstchild ;
while(t)
{
t->child=order[t->child];
t=t->next;
}
}
x++;
count++;
}
return OK;
}
}
return ERROR;
}
void LevelOrderTraverse_C(CTree T)
{
int start,end;
printf("%c ",T.nodes[T.r].data);
if(T.r<T.n)
end=T.n;
else
end=T.n-1;
for(start=0;start<end;start++ )
{
if(start==T.r)
start++;
printf("%c ",T.nodes[start].data);
}
printf("\n");
}
void main()
{
CTree T;CTree t;
printf("InitTree_C函数Test.......\n");
InitTree_C(&T);
printf("CreatTree_C函数Test.......\n");
CreatTree_C(&T);
printf("TreeDegree_C函数Test.......\n");
printf("树的度为:%d\n",TreeDegree_C(T));
printf("TreeDepth_C函数Test.......\n");
printf("树的深度为:%d\n",TreeDepth_C(T));
printf("Root_C函数Test.......\n");
printf("输出树的根结点:%c\n",Root_C(T));
printf("Value_C函数Test.......\n");
printf("输出树的第7个结点的值:%c\n",Value_C(T,7));
printf("Order_C函数Test.......\n");
int test1;
for(test1=0;test1<T.n;test1++)
{
printf("输出%c结点在数组中的下标:%d\n",T.nodes[test1].data,Order_C(T,T.nodes[test1].data));
}
printf("Assign_C函数Test.......\n");
printf("将K结点的值修改为M.....\n");
Assign_C(&T,'K','M');
printf("输出修改后的结果:%c\n",T.nodes[T.n-1].data);
printf("ChildValue_C函数Test.......\n");
printf("输出F结点的第一个孩子的值:%c\n",ChildValue_C(T,'F',1));
printf("输出F结点的第二个孩子的值:%c\n",ChildValue_C(T,'F',2));
printf("输出F结点的第三个孩子的值:%c\n",ChildValue_C(T,'F',3));
printf("输出A结点的第三个孩子的值:%c\n",ChildValue_C(T,'A',3));//结点孩子不存在 test
printf("Sibling_C函数Test.......\n");
printf("输出结点B的左兄弟的值:%c\n",Sibling_C(T,'B',0));
printf("输出结点B的右兄弟的值:%c\n",Sibling_C(T,'B',1));
printf("输出结点A的左兄弟的值:%c\n",Sibling_C(T,'A',0));//结点左兄弟不存在 test
printf("输出结点C的右兄弟的值:%c\n",Sibling_C(T,'C',1));//结点右兄弟不存在 test
printf("ChildCount_C函数Test.......\n"); //全体测试
int test2;
for(test2=0;test2<T.n;test2++)
{
printf("输出%c结点的孩子数:%d\n",T.nodes[test2].data,ChildCount_C(T,T.nodes[test2].data));
}
printf("ChildSeat_C函数Test.......\n"); //全体测试
int test3;
int count;
for(test3=0;test3<T.n;test3++)
{
for(count=0;count<=ChildCount_C(T,T.nodes[test3].data);count++)
{
printf("输出%c结点的第%d个孩子(层序计数)的位置:%d\n",T.nodes[test3].data,count,ChildSeat_C(T,T.nodes[test3].data,count));
if(count>=ChildCount_C(T,T.nodes[test3].data)-1)
break;
}
}
printf("SiblingSeat_C函数Test.......\n");
printf("输出孩子链表中指向C的指针:%p\n",SiblingSeat_C(T,'C'));
printf("输出该指针指向的child:%d\n",SiblingSeat_C(T,'C')->child);
/* printf("InsertChild_C函数Test.......\n");
InsertChild_C(&T,'A',1,'0');
InsertChild_C(&T,'0',0,'1');
InsertChild_C(&T,'0',0,'2');
InsertChild_C(&T,'0',0,'3');
InsertChild_C(&T,'3',0,'4');
InsertChild_C(&T,'3',0,'5');
//测试插入一棵树后的树T的情况
int test4;
for(test4=0;test4<T.n;test4++)
{
printf("node[%d]=%c ",test4,T.nodes[test4].data);
printf("双亲位置为:%d\n",T.nodes[test4].parent);
}
printf("T.n=%d\n",T.n);
*/
printf("InitTree_C函数Test.......\n");
InitTree_C(&t);
printf("CreatTree_C函数Test.......\n");
CreatTree_C(&t);
//测试新树t的创建情况
// int test5;
// for(test5=0;test5<t.n;test5++)
// {
// printf("node[%d]=%c ",test5,t.nodes[test5].data);
// printf("双亲位置为:%d\n",t.nodes[test5].parent);
// }
// printf("t.n=%d\n",t.n);
printf("InsertTree_C函数Test.......\n");
printf("输出在A结点的第一个孩子的位置插入一棵树t后的数组:\n");
InsertTree_C(&T,'A',1,t);
printf("插入测试:%c\n",T.nodes[5].data);
int test6;
for(test6=0;test6<T.n;test6++)
{
printf("node[%d]=%c ",test6,T.nodes[test6].data);
printf("双亲位置为:%d\n",T.nodes[test6].parent);
}
printf("T.n=%d\n",T.n);
/*
printf("DeleteTree_C函数Test.......\n");
DeleteTree_C(&T,'A',2);
printf("输出在删除A结点的第二个孩子的位置后的树的所对应的数组:\n");
//测试代码
int wawa;
for(wawa=0;wawa<T.n;wawa++)
{
printf("node[%d]=%c ",wawa,T.nodes[wawa].data);
printf("双亲位置为:%d\n",T.nodes[wawa].parent);
}
printf("T.n=%d\n",T.n);
printf("LevelOrderTraverse_C函数Test.......\n");
printf("层序输出树T.........................\n");
LevelOrderTraverse_C(T);
*/
}