file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/R`LJX07MY]`I_76G~27K(9V.jpg树的孩子兄弟表示法" TITLE="第六章 树的孩子兄弟表示法" />

 

 // c6-5.h 树的二叉链表(孩子－兄弟)存储表示
 typedef struct CSNode
 {
   TElemType data;
   CSNode *firstchild,*nextsibling;
 }CSNode,*CSTree;

 

 // bo6-5.cpp 树的二叉链表(孩子－兄弟)存储(存储结构由c6-5.h定义)的基本操作(17个)
 Status InitTree(CSTree &T)
 { // 操作结果: 构造空树T
   T=NULL;
   return OK;
 }

 void DestroyTree(CSTree &T)
 { // 初始条件: 树T存在。操作结果: 销毁树T
   if(T)
   {
     if(T->firstchild) // T有长子
       DestroyTree(T->firstchild); // 销毁T的长子为根结点的子树
     if(T->nextsibling) // T有下一个兄弟
       DestroyTree(T->nextsibling); // 销毁T的下一个兄弟为根结点的子树
     free(T); // 释放根结点
     T=NULL;
   }
 }

 typedef CSTree QElemType; // 定义队列元素类型
 #include"c3-2.h" // 定义LinkQueue类型
 #include"bo3-2.cpp" // LinkQueue类型的基本操作
 Status CreateTree(CSTree &T)
 { // 构造树T
   char c[20]; // 临时存放孩子结点(设不超过20个)的值
   CSTree p,p1;
   LinkQueue q;
   int i,l;
   InitQueue(q);
   printf("请输入根结点(字符型,空格为空): ");
   scanf("%c%*c",&c[0]);
   if(c[0]!=Nil) // 非空树
   {
     T=(CSTree)malloc(sizeof(CSNode)); // 建立根结点
     T->data=c[0];
     T->nextsibling=NULL;
     EnQueue(q,T); // 入队根结点的指针
     while(!QueueEmpty(q)) // 队不空
     {
       DeQueue(q,p); // 出队一个结点的指针
       printf("请按长幼顺序输入结点%c的所有孩子: ",p->data);
       gets(c);
       l=strlen(c);
       if(l>0) // 有孩子
       {
         p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); // 建立长子结点
         p1->data=c[0];
         for(i=1;i<l;i++)
         {
           p1->nextsibling=(CSTree)malloc(sizeof(CSNode)); // 建立下一个兄弟结点
           EnQueue(q,p1); // 入队上一个结点
           p1=p1->nextsibling;
           p1->data=c[i];
         }
         p1->nextsibling=NULL;
         EnQueue(q,p1); // 入队最后一个结点
       }
       else
         p->firstchild=NULL;
     }
   }
   else
     T=NULL;
   return OK;
 }

 #define ClearTree DestroyTree // 二者操作相同

 Status TreeEmpty(CSTree T)
 { // 初始条件: 树T存在。操作结果: 若T为空树,则返回TURE,否则返回FALSE
   if(T) // T不空
     return FALSE;
   else
     return TRUE;
 }

 int TreeDepth(CSTree T)
 { // 初始条件: 树T存在。操作结果: 返回T的深度
   CSTree p;
   int depth,max=0;
   if(!T) // 树空
     return 0;
   if(!T->firstchild) // 树无长子
     return 1;
   for(p=T->firstchild;p;p=p->nextsibling)
   {
     depth=TreeDepth(p);
     if(depth>max)
       max=depth;
   }
   return max+1;
 }

 TElemType Value(CSTree p)
 { // 返回p所指结点的值
   return p->data;
 }

 TElemType Root(CSTree T)
 { // 初始条件: 树T存在。操作结果: 返回T的根
   if(T)
     return Value(T);
   else
     return Nil;
 }

 CSTree Point(CSTree T,TElemType s)
 { // 返回二叉链表(孩子－兄弟)树T中指向元素值为s的结点的指针。另加
   LinkQueue q;
   QElemType a;
   if(T) // 非空树
   {
     InitQueue(q); // 初始化队列
     EnQueue(q,T); // 根结点入队
     while(!QueueEmpty(q)) // 队不空
     {
       DeQueue(q,a); // 出队,队列元素赋给a
       if(a->data==s)
         return a;
       if(a->firstchild) // 有长子
         EnQueue(q,a->firstchild); // 入队长子
       if(a->nextsibling) // 有下一个兄弟
         EnQueue(q,a->nextsibling); // 入队下一个兄弟
     }
   }
   return NULL;
 }

 Status Assign(CSTree &T,TElemType cur_e,TElemType value)
 { // 初始条件: 树T存在,cur_e是树T中结点的值。操作结果: 改cur_e为value
   CSTree p;
   if(T) // 非空树
   {
     p=Point(T,cur_e); // p为cur_e的指针
     if(p) // 找到cur_e
     {
       p->data=value; // 赋新值
       return OK;
     }
   }
   return Nil; // 树空或没找到
 }

 TElemType Parent(CSTree T,TElemType cur_e)
 { // 初始条件: 树T存在,cur_e是T中某个结点
   // 操作结果: 若cur_e是T的非根结点,则返回它的双亲,否则函数值为＂空＂
   CSTree p,t;
   LinkQueue q;
   InitQueue(q);
   if(T) // 树非空
   {
     if(Value(T)==cur_e) // 根结点值为cur_e
       return Nil;
     EnQueue(q,T); // 根结点入队
     while(!QueueEmpty(q))
     {
       DeQueue(q,p);
       if(p->firstchild) // p有长子
       {
         if(p->firstchild->data==cur_e) // 长子为cur_e
           return Value(p); // 返回双亲
         t=p; // 双亲指针赋给t
         p=p->firstchild; // p指向长子
         EnQueue(q,p); // 入队长子
         while(p->nextsibling) // 有下一个兄弟
         {
           p=p->nextsibling; // p指向下一个兄弟
           if(Value(p)==cur_e) // 下一个兄弟为cur_e
             return Value(t); // 返回双亲
           EnQueue(q,p); // 入队下一个兄弟
         }
       }
     }
   }
   return Nil; // 树空或没找到cur_e
 }

 TElemType LeftChild(CSTree T,TElemType cur_e)
 { // 初始条件: 树T存在,cur_e是T中某个结点
   // 操作结果: 若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回＂空＂
   CSTree f;
   f=Point(T,cur_e); // f指向结点cur_e
   if(f&&f->firstchild) // 找到结点cur_e且结点cur_e有长子
     return f->firstchild->data;
   else
     return Nil;
 }

 TElemType RightSibling(CSTree T,TElemType cur_e)
 { // 初始条件: 树T存在,cur_e是T中某个结点
   // 操作结果: 若cur_e有右兄弟,则返回它的右兄弟,否则返回＂空＂
   CSTree f;
   f=Point(T,cur_e); // f指向结点cur_e
   if(f&&f->nextsibling) // 找到结点cur_e且结点cur_e有右兄弟
     return f->nextsibling->data;
   else
     return Nil; // 树空
 }

 Status InsertChild(CSTree &T,CSTree p,int i,CSTree c)
 { // 初始条件: 树T存在,p指向T中某个结点,1≤i≤p所指结点的度+1,非空树c与T不相交
   // 操作结果: 插入c为T中p结点的第i棵子树
   // 因为p所指结点的地址不会改变，故p不需是引用类型
   int j;
   if(T) // T不空
   {
     if(i==1) // 插入c为p的长子
     {
       c->nextsibling=p->firstchild; // p的原长子现是c的下一个兄弟(c本无兄弟)
       p->firstchild=c;
     }
     else // 找插入点
     {
       p=p->firstchild; // 指向p的长子
       j=2;
       while(p&&j<i)
       {
         p=p->nextsibling;
         j++;
       }
       if(j==i) // 找到插入位置
       {
         c->nextsibling=p->nextsibling;
         p->nextsibling=c;
       }
       else // p原有孩子数小于i-1
         return ERROR;
     }
     return OK;
   }
   else // T空
     return ERROR;
 }

 Status DeleteChild(CSTree &T,CSTree p,int i)
 { // 初始条件: 树T存在,p指向T中某个结点,1≤i≤p所指结点的度
   // 操作结果: 删除T中p所指结点的第i棵子树
   // 因为p所指结点的地址不会改变，故p不需是引用类型
   CSTree b;
   int j;
   if(T) // T不空
   {
     if(i==1) // 删除长子
     {
       b=p->firstchild;
       p->firstchild=b->nextsibling; // p的原次子现是长子
       b->nextsibling=NULL;
       DestroyTree(b);
     }
     else // 删除非长子
     {
       p=p->firstchild; // p指向长子
       j=2;
       while(p&&j<i)
       {
         p=p->nextsibling;
         j++;
       }
       if(j==i) // 找到第i棵子树
       {
         b=p->nextsibling;
         p->nextsibling=b->nextsibling;
         b->nextsibling=NULL;
         DestroyTree(b);
       }
       else // p原有孩子数小于i
         return ERROR;
     }
     return OK;
   }
   else
     return ERROR;
 }

 void PreOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { // 先根遍历孩子－兄弟二叉链表结构的树T
   if(T)
   {
     Visit(Value(T)); // 先访问根结点
     PreOrderTraverse(T->firstchild,Visit); // 再先根遍历长子子树
     PreOrderTraverse(T->nextsibling,Visit); // 最后先根遍历下一个兄弟子树
   }
 }

 void PostOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { // 后根遍历孩子－兄弟二叉链表结构的树T
   CSTree p;
   if(T)
   {
     if(T->firstchild) // 有长子
     {
       PostOrderTraverse(T->firstchild,Visit); // 后根遍历长子子树
       p=T->firstchild->nextsibling; // p指向长子的下一个兄弟
       while(p)
       {
         PostOrderTraverse(p,Visit); // 后根遍历下一个兄弟子树
         p=p->nextsibling; // p指向再下一个兄弟
       }
     }
     Visit(Value(T)); // 最后访问根结点
   }
 }

 void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { // 层序遍历孩子－兄弟二叉链表结构的树T
   CSTree p;
   LinkQueue q;
   InitQueue(q);
   if(T)
   {
     Visit(Value(T)); // 先访问根结点
     EnQueue(q,T); // 入队根结点的指针
     while(!QueueEmpty(q)) // 队不空
     {
       DeQueue(q,p); // 出队一个结点的指针
       if(p->firstchild) // 有长子
       {
         p=p->firstchild;
         Visit(Value(p)); // 访问长子结点
         EnQueue(q,p); // 入队长子结点的指针
         while(p->nextsibling) // 有下一个兄弟
         {
           p=p->nextsibling;
           Visit(Value(p)); // 访问下一个兄弟
           EnQueue(q,p); // 入队兄弟结点的指针
         }
       }
     }
   }
 }

 // main6-5.cpp 检验bo6-5.cpp的主程序
 #include"c1.h"
 typedef char TElemType;
 TElemType Nil=' '; // 以空格符为空
 #include"c6-5.h"
 #include"bo6-5.cpp"

 void vi(TElemType c)
 {
   printf("%c ",c);
 }

 void main()
 {
   int i;
   CSTree T,p,q;
   TElemType e,e1;
   InitTree(T);
   printf("构造空树后,树空否? %d(1:是 0:否) 树根为%c 树的深度为%d\n",TreeEmpty(T),Root(T),TreeDepth(T));
   CreateTree(T);
   printf("构造树T后,树空否? %d(1:是 0:否) 树根为%c 树的深度为%d\n",TreeEmpty(T),Root(T),TreeDepth(T));
   printf("先根遍历树T:\n");
   PreOrderTraverse(T,vi);
   printf("\n请输入待修改的结点的值 新值: ");
   scanf("%c%*c%c%*c",&e,&e1);
   Assign(T,e,e1);
   printf("后根遍历修改后的树T:\n");
   PostOrderTraverse(T,vi);
   printf("\n%c的双亲是%c,长子是%c,下一个兄弟是%c\n",e1,Parent(T,e1),LeftChild(T,e1),RightSibling(T,e1));
   printf("建立树p:\n");
   InitTree(p);
   CreateTree(p);
   printf("层序遍历树p:\n");
   LevelOrderTraverse(p,vi);
   printf("\n将树p插到树T中，请输入T中p的双亲结点子树序号: ");
   scanf("%c%d%*c",&e,&i);
   q=Point(T,e);
   InsertChild(T,q,i,p);
   printf("层序遍历树T:\n");
   LevelOrderTraverse(T,vi);
   printf("\n删除树T中结点e的第i棵子树，请输入e i: ");
   scanf("%c%d",&e,&i);
   q=Point(T,e);
   DeleteChild(T,q,i);
   printf("层序遍历树T:\n",e,i);
   LevelOrderTraverse(T,vi);
   printf("\n");
   DestroyTree(T);
 }