bo6-1.cpp

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

 // bo6-1.cpp 二叉树的顺序存储(存储结构由c6-1.h定义)的基本操作(23个)
 template<class T>
 SqBiTree<T>::SqBiTree()
 { // 构造空二叉树。
   int i;
   for(i=0;i<MAX_TREE_SIZE;i++)
     SQBiTree[i]=Nil; // 初值为空(Nil在主程中定义)
 }
 template<class T>
 SqBiTree<T>::~SqBiTree()
 { // 构造空二叉树。
   int i;
   for(i=0;i<MAX_TREE_SIZE;i++)
     SQBiTree[i]=Nil; // 初值为空(Nil在主程中定义)
 }
 template<class T>
 void SqBiTree<T>::ClearBiTree()
 { // 清空二叉树。
   int i;
   for(i=0;i<MAX_TREE_SIZE;i++)
     SQBiTree[i]=Nil; // 初值为空(Nil在主程中定义)
 }
 template<class T>
 void SqBiTree<T>::CreateBiTree()
 { // 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树
   int i=0;
  #if CHAR // CHAR值为非零，结点类型为字符
   int j;
   char s[MAX_TREE_SIZE],ch;
   cout<<"请按层序输入结点的值(字符)，'_'表示空结点，'/'表示结束。 结点数≤"<<MAX_TREE_SIZE<<":\n";
   for(i=0;i<100;i++)
	{
		cin>>ch;
		s[i]=ch;
		if(s[i]=='/')break;
	}
	  
   for(j=0;j<i;j++) // 将字符串赋值给T
    {
	   SQBiTree[j]=s[j];
	   if(j!=0&&SQBiTree[j]!=Nil&&SQBiTree[(j+1)/2-1]==Nil) // 此结点不空但无双亲
       {
         cout<<"出现无双亲的非根结点"<<SQBiTree[j]<<endl;
         exit(-1);
       }
    }
   for(j=i;j<MAX_TREE_SIZE;j++){SQBiTree[j]=Nil;}
  #else // CHAR值为零，结点类型为整型
   cout<<"请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤"<< MAX_TREE_SIZE<<":\n";
   while(1) // 永真循环
   {
     int e;
     cin>>e;
     SQBiTree[i]=e;
     if(SQBiTree[i]==999) // 输入结束
     break; // 跳出循环
     if(SQBiTree[i]!=Nil&&SQBiTree[(i+1)/2-1]==Nil) // 此结点不空但无双亲
     {
       cout<<"出现无双亲的非根结点"<<SQBiTree[i]<<endl;
       exit(-1);
     }
     i++; // 计数器加1
   }
   while(i<MAX_TREE_SIZE){SQBiTree[i]=Nil;i++;}
  #endif
 }
 template<class T>
 bool SqBiTree<T>::BiTreeEmpty()
 { // 初始条件：二叉树存在。操作结果：若二叉树为空，则返回TRUE；否则FALSE
     if(SQBiTree[0]==Nil) // 根结点为空，则树空
     return 1;
   else
     return 0;
 }
 template<class T>
 int SqBiTree<T>::BiTreeDepth()
 { // 初始条件：二叉树存在。操作结果：返回二叉树的深度
   int i,j=-1;
   if(SQBiTree[0]==Nil) // 根结点为空，则树空
     return 0; // 空树的深度为0
   for(i=MAX_TREE_SIZE-1;i>=0;i--) // 从数组的后面向前找起
     if(SQBiTree[i]!=Nil) // 找到最后一个结点，其序号为i
       break;
	 i++;
	 do
	 j++;
	 while(i>=pow(2,j));
   return j;// j的值就是树的深度
 }
 template<class T>
 bool SqBiTree<T>::Root(T &e)
 { // 初始条件：二叉树存在。操作结果：当二叉树不空,用e返回T的根,返回OK；否则返回ERROR,e无定义
   if(BiTreeEmpty()) // 二叉树空
     return 0;
   else
   {
     e=SQBiTree[0];
     return 1;
   }
 }
 template<class T>
 T SqBiTree<T>::Value(position e)
 { // 初始条件：二叉树存在，e是二叉树中某个结点(的位置)
   // 操作结果：返回处于位置e(层,本层序号)的结点的值
   return SQBiTree[(int)pow(2,e.level-1)+e.order-2];
 }
 template<class T>
 bool SqBiTree<T>::Assign(position e,T value)
 { // 初始条件：二叉树存在，e是二叉树中某个结点(的位置)
   // 操作结果：给处于位置e(层,本层序号)的结点赋新值value
   int i=(int)pow(2,e.level-1)+e.order-2; // 将层、本层序号转为数组的序号
   if(i!=0&&value!=Nil&&SQBiTree[(i+1)/2-1]==Nil) // 不是根结点，值非空，但双亲为空
     return 0;
   else if(value==Nil&&(SQBiTree[i*2+1]!=Nil||SQBiTree[i*2+2]!=Nil)) // 给双亲赋空值但有孩子结点
      return 0;
   SQBiTree[i]=value; // 以上2种情况之外，给结点赋新值
   return 1;
 }
 template<class T>
 T SqBiTree<T>::Parent(T e)
 { // 初始条件：二叉树存在，e是二叉树中某个结点
   // 操作结果：若e是二叉树的非根结点，则返回它的双亲；否则返回“空”
   int i;
   if(SQBiTree[0]==Nil) // 空树
     return Nil; // 返回“空”
   for(i=1;i<=MAX_TREE_SIZE-1;i++) // 从二叉树的第2个结点开始查找
     if(SQBiTree[i]==e) // 找到e
       return SQBiTree[(i+1)/2-1]; // 返回其双亲结点的值
   return Nil; // 没找到e
 }
 template<class T>
 T SqBiTree<T>::LeftChild(T e)
 { // 初始条件：二叉树存在，e是二叉树中某个结点
   // 操作结果：返回e的左孩子。若e无左孩子，则返回“空”
   int i;
   for(i=0;i<=(MAX_TREE_SIZE-2)/2;i++) // 从T的第1个结点到最后一个可能有左孩子的结点
     if(SQBiTree[i]==e) // 找到e
       return SQBiTree[i*2+1]; // 返回e的左孩子的值
   return Nil; // 没找到e
 }
 template<class T> 
 T SqBiTree<T>::RightChild(T e)
 { // 初始条件：二叉树存在，e是二叉树中某个结点。操作结果：返回e的右孩子。若e无右孩子,则返回“空”
   int i;
   for(i=0;i<=(MAX_TREE_SIZE-3)/2;i++) // 从T的第1个结点到最后一个可能有右孩子的结点
     if(SQBiTree[i]==e) // 找到e
       return SQBiTree[i*2+2]; // 返回e的右孩子的值
   return Nil; // 没找到e
 }
 template<class T>
 T SqBiTree<T>::LeftSibling(T e)
 { // 初始条件：二叉树存在，e是二叉树中某个结点
   // 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”
   int i;
   if(SQBiTree[0]==Nil) // 空树
     return Nil; // 返回"空"
   for(i=1;i<=MAX_TREE_SIZE-1;i++) // 从二叉树的第2个结点开始查找
     if(SQBiTree[i]==e&&i%2==0) // 找到e且其序号为偶数(是右孩子)
       return SQBiTree[i-1]; // 返回e的左兄弟的值
   return Nil; // 没找到e
 }
 template<class T>
 T SqBiTree<T>::RightSibling(T e)
 { // 初始条件：二叉树存在，e是二叉树中某个结点
   // 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”
   int i;
   if(SQBiTree[0]==Nil) // 空树
     return Nil; // 返回"空"
   for(i=1;i<=MAX_TREE_SIZE-2;i++) // 从二叉树的第2个结点开始查找
     if(SQBiTree[i]==e&&i%2) // 找到e且其序号为奇数(是左孩子)
       return SQBiTree[i+1]; // 返回e的右兄弟的值
   return Nil; // 没找到e
 }
 #include "c3-2.h" // 链队列
 #include "bo3-2.cpp" // 链队列的基本操作
 template<class T>
 bool SqBiTree<T>::DeleteChild(position p,int LR)
 { // 初始条件：二叉树存在，p指向二叉树中某个结点，LR为0或1
   // 操作结果：根据LR为0或1，删除二叉树中p所指结点的左或右子树
   int i;
   bool k=1; // 队列不空的标志
   LinkQueue<int> q;
   i=(int)pow(2,p.level-1)+p.order-2; // 将层、本层序号转为数组的序号
   if(SQBiTree[i]==Nil) // 此结点空
     return 0;
   i=i*2+1+LR; // 待删除子树的根结点在数组中的序号
   while(k)
   {
     if(SQBiTree[2*i+1]!=Nil) // 左结点不空
       q.EnQueue(2*i+1); // 入队左结点的序号
     if(SQBiTree[2*i+2]!=Nil) // 右结点不空
       q.EnQueue(2*i+2); // 入队右结点的序号
     SQBiTree[i]=Nil; // 删除此结点
     k=q.DeQueue(i); // 出队结点的序号，其值赋给i，成功(队列不空)返回OK；否则返回ERROR
   }
   return 1;
 }
 template<class T>
 void SqBiTree<T>::PreTraverse(int e)
 { // 递归先序遍历二叉树T中序号为e的子树，PreOrderTraverse()调用
   VisitFunc(SQBiTree[e]); // 访问树T中序号为e的结点
   if(SQBiTree[2*e+1]!=Nil) // 序号为e的结点的左子树不空
     PreTraverse(2*e+1); // 递归先序遍历树T中序号为e的结点的左子树
   if(SQBiTree[2*e+2]!=Nil) // 序号为e的结点的右子树不空
     PreTraverse(2*e+2); // 递归先序遍历树T中序号为e的结点的右子树
 }
 template<class T>
 void SqBiTree<T>::PreOrderTraverse(void(*Visit)(T))
 { // 初始条件：二叉树存在，Visit是对结点操作的应用函数
   // 操作结果：先序遍历二叉树，对每个结点调用函数Visit一次且仅一次
   VisitFunc=Visit;
   if(!BiTreeEmpty()) // 树不空
     PreTraverse(0); // 递归先序遍历树二叉树中序号为0的树
   cout<<endl;
 }
 template<class T>
 void SqBiTree<T>::InTraverse(int e)
 { // 递归中序遍历二叉树中序号为e的子树，InOrderTraverse()调用
   if(SQBiTree[2*e+1]!=Nil) // 序号为e的结点的左子树不空
     InTraverse(2*e+1); // 递归中序遍历二叉树中序号为e的结点的左子树
   VisitFunc(SQBiTree[e]); // 访问二叉树中序号为e的结点
   if(SQBiTree[2*e+2]!=Nil) // 序号为e的结点的右子树不空
     InTraverse(2*e+2); // 递归中序遍历二叉树中序号为e的结点的右子树
 }
 template<class T>
 void SqBiTree<T>::InOrderTraverse(void(*Visit)(T))
 { // 初始条件：二叉树存在，Visit是对结点操作的应用函数
   // 操作结果：中序遍历二叉树，对每个结点调用函数Visit一次且仅一次
   VisitFunc=Visit;
   if(!BiTreeEmpty()) // 二叉树不空
     InTraverse(0); // 递归中序遍历二叉树中序号为0的树
   cout<<endl;
 }
 template<class T>
 void SqBiTree<T>::PostTraverse(int e)
 { // 递归后序遍历二叉树中序号为e的子树，PostOrderTraverse()调用
   if(SQBiTree[2*e+1]!=Nil) // 序号为e的结点的左子树不空
     PostTraverse(2*e+1); // 递归后序遍历二叉树中序号为e的结点的左子树
   if(SQBiTree[2*e+2]!=Nil) // 序号为e的结点的右子树不空
     PostTraverse(2*e+2); // 递归后序遍历二叉树中序号为e的结点的右子树
   VisitFunc(SQBiTree[e]); // 访问二叉树中序号为e的结点
 }
 template<class T>
 void SqBiTree<T>::PostOrderTraverse(void(*Visit)(T))
 { // 初始条件：二叉树存在，Visit是对结点操作的应用函数
   // 操作结果：后序遍历二叉树，对每个结点调用函数Visit一次且仅一次
   VisitFunc=Visit;
   if(!BiTreeEmpty()) // 二叉树不空
     PostTraverse(0); // 递归后序遍历二叉树中序号为0的树
   cout<<endl;
 }
 template<class T>
 void SqBiTree<T>::LevelOrderTraverse(void(*Visit)(T))
 { // 层序遍历二叉树T
   int i=MAX_TREE_SIZE-1,j;
   while(SQBiTree[i]==Nil)
     i--; // 找到最后一个非空结点的序号
   for(j=0;j<=i;j++) // 从根结点起，按层序遍历二叉树
     if(SQBiTree[j]!=Nil)
       Visit(SQBiTree[j]); // 只遍历非空的结点
   cout<<endl;
 }
 template<class T>
 void SqBiTree<T>::Print()
 { // 逐层、按本层序号输出二叉树
   int j,k;
   position p;
   T e;
   for(j=1;j<=BiTreeDepth();j++) // j为当前层
   {
     cout<<"第"<<j<<"层";
     p.level=j; // 当前结点所在层
     for(k=1;k<=pow(2,j-1);k++)
     {
       p.order=k; // 当前结点在本层的顺序
       e=Value(p); // 该结点的值赋给e
       if(e!=Nil) // e非空
         cout<<k<<":"<<e<<" "; // 输出在本层的顺序及值
     }
   cout<<endl;
   }
 }
  void Move(SqBiTree<int> &c,int j,SqBiTree<int> &t,int i) // InsertChild()用到。加
  { // 把从q的j结点开始的子树移为从的i结点开始的子树
   if(i>=MAX_TREE_SIZE) // i结点超出了存储范围
     exit(-1);
   if(c.SQBiTree[2*j+1]!=Nil) // q的左子树不空
   {Move(c,(2*j+1),t,(2*i+1));}// 把q的j结点的左子树移为t的i结点的左子树
   if(c.SQBiTree[2*j+2]!=Nil) // q的右子树不空
   {Move(c,(2*j+2),t,(2*i+2));}// 把q的j结点的右子树移为t的i结点的右子树
   t.SQBiTree[i]=c.SQBiTree[j]; // 把q的j结点移为T的i结点
   c.SQBiTree[j]=Nil; // 把q的j结点置空
  }
  void Move(SqBiTree<char> &c,int j,SqBiTree<char> &t,int i) // InsertChild()用到。加
  { // 把从q的j结点开始的子树移为从t的i结点开始的子树
   if(i>=MAX_TREE_SIZE) // i结点超出了存储范围
     exit(-1);
   if(c.SQBiTree[2*j+1]!=Nil) // q的左子树不空
   {Move(c,(2*j+1),t,(2*i+1));} // 把q的j结点的左子树移为t的i结点的左子树
   if(c.SQBiTree[2*j+2]!=Nil) // q的右子树不空
   {Move(c,(2*j+2),t,(2*i+2));} // 把q的j结点的右子树移为t的i结点的右子树
   t.SQBiTree[i]=c.SQBiTree[j]; // 把q的j结点移为t的i结点
   c.SQBiTree[j]=Nil; // 把q的j结点置空
  }
  //template<class T>
  void InsertChild(SqBiTree<int> &t,int p,int LR, SqBiTree<int> &c )
  { //初始条件:二叉树t存在，p是t中某个结点的值，LR为0或1，非空二叉树c与t不相交且右子树为空
    //操作结果:根据LR为0或1,插入c为t中p结点的左或右子树。p结点的原有左或右子树则成为c的右子树
   int j,k;
   for(j=0;j<(int)pow(2,t.BiTreeDepth())-1;j++) // 查找p的序号
     if(t.SQBiTree[j]==p) // j为p的序号
       break;
   k=2*j+1+LR; // k为p的左或右孩子的序号
   if(t.SQBiTree[k]!=Nil) // p原来的左或右孩子不空
     Move(t,k,c,2); // 把从t的k结点开始的子树移为c的右子树
   Move(c,0,t,k); // 把树c移为从t的k结点开始的子树
  }
  void InsertChild(SqBiTree<char> &t,char p,int LR,SqBiTree<char> &c)
  { //初始条件:二叉树t存在，p是t中某个结点的值，LR为0或1，非空二叉树c与t不相交且右子树为空
    //操作结果:根据LR为0或1,插入c为t中p结点的左或右子树。p结点的原有左或右子树则成为c的右子树
   int j,k;
   for(j=0;j<(int)pow(2,t.BiTreeDepth())-1;j++) // 查找p的序号
     if(t.SQBiTree[j]==p) // j为p的序号
       break;
   k=2*j+1+LR; // k为p的左或右孩子的序号
   if(t.SQBiTree[k]!=Nil) // p原来的左或右孩子不空
     Move(t,k,c,2); // 把从T的k结点开始的子树移为c的右子树
   Move(c,0,t,k); // 把树c移为从t的k结点开始的子树
  }