将新树t，插入树T中，树t中每个结点的孩子结点都会先后顺序颠倒

Question

下面有我粘出来的代码,请大牛出手相助！
树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

Answer 1

include

include

define TRUE 1

define FALSE 0

define ERROR 0

define MAX_TREE_SIZE 100

define OVERFLOW 0

define OK 1

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);

*/

}