二叉树的顺序存储.txt

主要是关于二叉树的顺序存储的

 typedef int QElemType; /* 设队列元素类型为整型(序号) */
// #include "c3-3.h" /* 顺序非循环队列 */
// #include "bo3-4.c" /* 顺序非循环队列的基本操作 */
  /* bo3-4.c 顺序队列(非循环,存储结构由c3-3.h定义)的基本操作(9个) */
 Status InitQueue(SqQueue *Q)
 { /* 构造一个空队列Q */
   (*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
   if(!(*Q).base) /* 存储分配失败 */
     exit(OVERFLOW);
   (*Q).front=(*Q).rear=0;
   return OK;
 }

 Status DestroyQueue(SqQueue *Q)
 { /* 销毁队列Q,Q不再存在 */
   if((*Q).base)
     free((*Q).base);
   (*Q).base=NULL;
   (*Q).front=(*Q).rear=0;
   return OK;
 }

 Status ClearQueue(SqQueue *Q)
 { /* 将Q清为空队列 */
   (*Q).front=(*Q).rear=0;
   return OK;
 }

 Status QueueEmpty(SqQueue Q)
 { /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
   if(Q.front==Q.rear) /* 队列空的标志 */
     return TRUE;
   else
     return FALSE;
 }

 int QueueLength(SqQueue Q)
 { /* 返回Q的元素个数,即队列的长度 */
   return(Q.rear-Q.front);
 }

 Status GetHead(SqQueue Q,QElemType *e)
 { /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
   if(Q.front==Q.rear) /* 队列空 */
     return ERROR;
   *e=*(Q.base+Q.front);
   return OK;
 }

 Status EnQueue(SqQueue *Q,QElemType e)
 { /* 插入元素e为Q的新的队尾元素 */
   if((*Q).rear>=MAXQSIZE)
   { /* 队列满，增加1个存储单元 */
     (*Q).base=(QElemType *)realloc((*Q).base,((*Q).rear+1)*sizeof(QElemType));
     if(!(*Q).base) /* 增加单元失败 */
       return ERROR;
   }
   *((*Q).base+(*Q).rear)=e;
   (*Q).rear++;
   return OK;
 }

 Status DeQueue(SqQueue *Q,QElemType *e)
 { /* 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
   if((*Q).front==(*Q).rear) /* 队列空 */
     return ERROR;
   *e=(*Q).base[(*Q).front];
   (*Q).front=(*Q).front+1;
   return OK;
 }

 Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))
 { /* 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败 */
   int i;
   i=Q.front;
   while(i!=Q.rear)
   {
     vi(*(Q.base+i));
     i++;
   }
   printf("\n");
   return OK;
 }
 /////////////////////////////////////////////////////////////////////////////////////////////////////

 Status DeleteChild(SqBiTree T,position p,int LR)
 { /* 初始条件: 二叉树T存在,p指向T中某个结点,LR为1或0 */
   /* 操作结果: 根据LR为1或0,删除T中p所指结点的左或右子树 */
   int i;
   Status k=OK; /* 队列不空的标志 */
   SqQueue q;
   InitQueue(&q); /* 初始化队列，用于存放待删除的结点 */
   i=(int)pow(2,p.level-1)+p.order-2; /* 将层、本层序号转为矩阵的序号 */
   if(T[i]==Nil) /* 此结点空 */
     return ERROR;
   i=i*2+1+LR; /* 待删除子树的根结点在矩阵中的序号 */
   while(k)
   {
     if(T[2*i+1]!=Nil) /* 左结点不空 */
       EnQueue(&q,2*i+1); /* 入队左结点的序号 */
     if(T[2*i+2]!=Nil) /* 右结点不空 */
       EnQueue(&q,2*i+2); /* 入队右结点的序号 */
     T[i]=Nil; /* 删除此结点 */
     k=DeQueue(&q,&i); /* 队列不空 */
   }
   return OK;
 }

 Status(*VisitFunc)(TElemType); /* 函数变量 */
 void PreTraverse(SqBiTree T,int e)
 { /* PreOrderTraverse()调用 */
   VisitFunc(T[e]);
   if(T[2*e+1]!=Nil) /* 左子树不空 */
     PreTraverse(T,2*e+1);
   if(T[2*e+2]!=Nil) /* 右子树不空 */
     PreTraverse(T,2*e+2);
 }

 Status PreOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 先序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     PreTraverse(T,0);
   printf("\n");
   return OK;
 }

 void InTraverse(SqBiTree T,int e)
 { /* InOrderTraverse()调用 */
   if(T[2*e+1]!=Nil) /* 左子树不空 */
     InTraverse(T,2*e+1);
   VisitFunc(T[e]);
   if(T[2*e+2]!=Nil) /* 右子树不空 */
     InTraverse(T,2*e+2);
 }

 Status InOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 中序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     InTraverse(T,0);
   printf("\n");
   return OK;
 }

 void PostTraverse(SqBiTree T,int e)
 { /* PostOrderTraverse()调用 */
   if(T[2*e+1]!=Nil) /* 左子树不空 */
     PostTraverse(T,2*e+1);
   if(T[2*e+2]!=Nil) /* 右子树不空 */
     PostTraverse(T,2*e+2);
   VisitFunc(T[e]);
 }

 Status PostOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 后序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     PostTraverse(T,0);
   printf("\n");
   return OK;
 }

 void LevelOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 层序遍历二叉树 */
   int i=MAX_TREE_SIZE-1,j;
   while(T[i]==Nil)
     i--; /* 找到最后一个非空结点的序号 */
   for(j=0;j<=i;j++)  /* 从根结点起,按层序遍历二叉树 */
     if(T[j]!=Nil)
       Visit(T[j]); /* 只遍历非空的结点 */
   printf("\n");
 }

 void Print(SqBiTree T)
 { /* 逐层、按本层序号输出二叉树 */
   int j,k;
   position p;
   TElemType e;
   for(j=1;j<=BiTreeDepth(T);j++)
   {
     printf("第%d层: ",j);
     for(k=1;k<=pow(2,j-1);k++)
     {
       p.level=j;
       p.order=k;
       e=Value(T,p);
       if(e!=Nil)
         printf("%d:%d ",k,e);
     }
     printf("\n");
   }
 }


int main(int argc, char* argv[])
{
   Status i;
   int j;
   position p;
   TElemType e;
   SqBiTree T,s;
   InitBiTree(T);
   CreateBiTree(T);
   printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
   i=Root(T,&e);
   if(i)
     printf("二叉树的根为：%d\n",e);
   else
     printf("树空，无根\n");
   printf("层序遍历二叉树:\n");
   LevelOrderTraverse(T,visit);
   printf("中序遍历二叉树:\n");
   InOrderTraverse(T,visit);
   printf("后序遍历二叉树:\n");
   PostOrderTraverse(T,visit);
   printf("请输入待修改结点的层号 本层序号: ");
   scanf("%d%d",&p.level,&p.order);
   e=Value(T,p);
   printf("待修改结点的原值为%d请输入新值: ",e);
   scanf("%d",&e);
   Assign(T,p,e);
   printf("先序遍历二叉树:\n");
   PreOrderTraverse(T,visit);
   printf("结点%d的双亲为%d,左右孩子分别为",e,Parent(T,e));
   printf("%d,%d,左右兄弟分别为",LeftChild(T,e),RightChild(T,e));
   printf("%d,%d\n",LeftSibling(T,e),RightSibling(T,e));
   InitBiTree(s);
   printf("建立右子树为空的树s:\n");
   CreateBiTree(s);
   printf("树s插到树T中,请输入树T中树s的双亲结点 s为左(0)或右(1)子树: ");
   scanf("%d%d",&e,&j);
   InsertChild(T,e,j,s);
   Print(T);
   printf("删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: ");
   scanf("%d%d%d",&p.level,&p.order,&j);
   DeleteChild(T,p,j);
   Print(T);
   ClearBiTree(T);
   printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
   i=Root(T,&e);
   if(i)
     printf("二叉树的根为：%d\n",e);
   else
     printf("树空，无根\n");
 return 0;
}