[数据结构与算法]2014年数据结构第五题（C/C++）

题目：

我的代码实现：

#include<iostream>
using namespace std;

#define TElemType char
typedef struct BiTNode{
 TElemType data;
 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)//先序遍历的顺序建立二叉链表
{
 TElemType ch;
 cin>>ch;
 if(ch=='#')T=NULL;
 else
 {
  T=new BiTNode;
  T->data=ch;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
 }
}

//顺序队列及其基本操作....................
#define QElemType BiTNode*
#define MAXQSIZE 100
typedef struct{
 QElemType *base;
 int front;
 int rear;
}SqQueue;

bool InitQueue(SqQueue &Q)
{
 Q.base=new QElemType[MAXQSIZE];
 if(!Q.base)exit(EOVERFLOW);
 Q.front=Q.rear=0;
 return true;
}

int QueueLength(SqQueue Q)
{
 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

bool EnQueue(SqQueue &Q,QElemType e)
{
 if((Q.rear+1)%MAXQSIZE==Q.front)return false;
 Q.base[Q.rear]=e;
 Q.rear=(Q.rear+1)%MAXQSIZE;
 return true;
}

bool DeQueue(SqQueue &Q,QElemType &e)
{
 if(Q.front==Q.rear)return false;
 e=Q.base[Q.front];
 Q.front=(Q.front+1)%MAXQSIZE;
 return true;
}
//........................................

//本题解答...........................
TElemType *name=NULL;
void Output(TElemType *name,int j,int k)
{
 printf("这家人共有%d代，最后一代有%d人.",k,j);
 printf("\n最后一代人姓名:\n");
 for(int i=0;i<=j;i++)
 {
  printf("%c ",name[i]);
 }
 printf("\n");
 delete name;
 name=NULL;
}

void PushSon(SqQueue &Q,QElemType &e)
{
 if(e->lchild)
 {
   BiTNode* p=e->lchild;
   while(p)
   {
    EnQueue(Q,p);
    p=p->rchild;
   }
 }
}

void Calcultate_Family(BiTree &T)
{
 BiTNode* p=T;
 int k=0,j=0;
 SqQueue Q;
 InitQueue(Q);
 EnQueue(Q,p);
 while(Q.front!=Q.rear)
 {
  k++;
  if(name)delete name;
  name=NULL;j=0;
  int l=QueueLength(Q);
  name=new TElemType[l];
  while(l)
  {
   QElemType e;
   DeQueue(Q,e);
   name[j++]=e->data;//用来临时保存当前出队的一代人的姓名
   PushSon(Q,e);//将e的所有孩子全部入队
   l--;
  }
 }
 Output(name,j,k);//输出总代数、最后一代人数及姓名
}
//...................................

void DestroyTree(BiTree &T)//销毁二叉树
{
 if(T!=NULL)
 {
  DestroyTree(T->lchild);
  DestroyTree(T->rchild);
  printf("销毁结点: %c\n",T->data);
  delete T;
  T=NULL; 
 }
 return;
}

int main()
{
  BiTree T=NULL;
  printf("先序建立二叉树:\n");
  CreateBiTree(T);
  
  Calcultate_Family(T); //本题解答

  DestroyTree(T);//销毁二叉树
  printf("\n成功销毁二叉树!\n");
  return 0; 
}

算法思想：这个家谱树的根结点没有兄弟。在该算法中，首先从树的根节点开始将每一代入队列中，再逐个出队，出队时将每一个节点的所有的孩子同时入队，直到队列中全为新一代结点地址，在最外层的while循环内设置动态数组用来临时存放每次出队的一代，如果这一代没有孩子，则为最后一代，否则动态数组会被释放。