bo3-2.cpp

该程序实现了对二叉树的各种遍历

 // bo3-2.cpp 链队列(存储结构由c3-2.h定义)的基本操作(9个)
 template<class T1>
 LinkQueue<T1>::LinkQueue()
 { // 构造一个空队列
   if(!(front=rear=new QNode)) // 生成头结点
     exit(OVERFLOW);
   front->next=NULL; // 头结点的next域为空
 }
 template<class T1>
 LinkQueue<T1>::~LinkQueue()
 { // 销毁队列(无论空否均可)。
  while(front) // front不为空
  {
    rear=front->next; // rear指向front的下一个结点
    delete front; // 释放front所指结点
    front=rear; // front指向front的下一个结点
   }
 }
 template<class T1>
 void LinkQueue<T1>::ClearQueue()
 { // 将队列清为空队列
   while(front) // front不为空
  {
    rear=front->next; // rear指向front的下一个结点
    delete front; // 释放front所指结点
    front=rear; // front指向front的下一个结点
  } //~LinkQueue(); // 销毁队列
   if(!(front=rear=new QNode)) // 生成头结点
     exit(OVERFLOW);
   front->next=NULL; // 头结点的next域为空                
 }
 
 template<class T1>
 bool LinkQueue<T1>::QueueEmpty()
 { // 若队列为空队列，则返回TRUE；否则返回FALSE
   if(front->next==NULL)
     return 1;
   else
     return 0;
 }
 template<class T1>
 int LinkQueue<T1>::QueueLength()
 { // 求队列的长度
   int i=0; // 计数器，初值为0
   QueuePtr p=front; // p指向头结点
   while(rear!=p) // p所指不是尾结点
   {
     i++; // 计数器+1
     p=p->next; // p指向下一个结点
   }
   return i;
 }
 template<class T1> 
 bool LinkQueue<T1>::GetHead(T1 &e)
 { // 若队列不空，则用e返回队头元素，并返回OK；否则返回ERROR
   QueuePtr p;
   if(front==rear) // 队列空
     return 0;
   p=front->next; // p指向队头结点
   e=p->data; // 将队头元素的值赋给e
   return 1;
 }
 template<class T1>
 void LinkQueue<T1>::EnQueue(T1 e)
 { // 插入元素e为队列的新的队尾元素
   QueuePtr p;
   if(!(p=new QNode)) // 动态生成新结点
     exit(OVERFLOW); // 失败则退出
   p->data=e; // 将值e赋给新结点
   p->next=NULL; // 新结点的指针域为空
   rear->next=p; // 原队尾结点的指针指向新结点
   rear=p; // 尾指针指向新结点
 }
 template<class T1>
 bool LinkQueue<T1>::DeQueue(T1 &e)
 { // 若队列不空，删除队头元素，用e返回其值，
   // 并返回OK；否则返回ERROR。
   QueuePtr p;
   if(front==rear) // 队列空
     return 0;
   p=front->next; // p指向队头结点
   e=p->data; // 将队头元素的值赋给e
   front->next=p->next; // 头结点指向下一个结点
   if(rear==p) // 删除的是队尾结点
     rear=front; // 修改队尾指针指向头结点(空队列)
   delete p; // 释放队头结点
   return 1;
 }
 template<class T1>
 void LinkQueue<T1>::QueueTraverse(void(*visit)(T1))
 { // 从队头到队尾依次对队列中每个元素调用函数visit()
   QueuePtr p=front->next; // p指向队头结点
   while(p) // p指向结点
   {
     visit(p->data); // 对p所指元素调用visit()
     p=p->next; // p指向下一个结点
   }
   cout<<"\n";
 }