binarytree_bas.h

数据结构与算法设计学习得素材

//--------------------------------------------------------------------------------
#ifndef BINARYTREE_BAS_H_
#define BINARYTREE_BAS_H_

#include <vector>       
#include <stack>
#include <queue>
#include <iostream>
#include "BinaryTree_Input.h"
using namespace std;
//--------------------------------------------------------------------------------
// classes defined herein
template<class T>  class  BTreeBas;
template<class T>  class  BTreeApp;
//--------------------------------------------------------------------------------
// 二叉树二叉链表类的结点类
template<class T>
class BTNode
{
   private:
      T data;                   // 数据域
      BTNode *lch,*rch;         // 左、右孩子指针域
      friend class BTreeBas<T>; // 声明友元类   
      friend class BTreeApp<T>; // 声明友元类
   public:
      BTNode(const T& x): lch(NULL), rch(NULL), data(x) {}
      ~BTNode() {
	     delete lch;
	     delete rch;
      }
};
//--------------------------------------------------------------------------------
// 二叉树二叉链表基类
template<class T>
class BTreeBas
{
   private:
      // 树的根结点
      BTNode<T> *root;
      // 结点数
      size_t numbr;
      // ss是指针数组用于记录结点之间的关系
      vector<BTNode<T>* > ss;
      // 先根、中根、中根非递归、按层遍历输出结点
      void predorder(const BTNode<T> *p);
      void inorder(const BTNode<T> *p);
      void inorderz(BTNode<T> *p);
      void levelorderz(BTNode<T> *p);
   public:
      // 构造器：二叉树输入类
      BTreeBas(BTree_DATA<T> tinfo);
      // 析构器
      ~BTreeBas() { delete root; }
      // 返回二叉树结点数
      int size() const { return numbr; }
      // 返回二叉树根结点指针
      BTNode<T> *getroot() { return root; }
      // 遍历二叉树方式如下：
      // 方式1（先根）、方式2（中根）、
      // 方式3（中根非递归）、方式4（按层遍历）
      void traver_mode(int mode);
};
//--------------------------------------------------------------------------------
// 实现 
template<class T>
BTreeBas<T>::BTreeBas(BTree_DATA<T> tinfo): numbr(tinfo.n)
{
   BTNode<T> *q;
   ss.resize(MaxN);
   int i=0,j;
   while((size_t)i<numbr)
   {
      // 分配结点并初始化
      q=new BTNode<T>(tinfo.x[i]);
      // q存入指针向量
      ss[tinfo.indx[i]]=q;
      // 建立二叉树结点之间的关系
      if (i==0) root=q;             // q作为二叉树的根结点
      else
      {  j=(tinfo.indx[i]-1)/2;                 // 双亲结点编号
         if (tinfo.indx[i]%2==1) ss[j]->lch=q;  // 双亲结点左孩子
         else                    ss[j]->rch=q;  // 双亲结点右孩子
      }
      i++;
   }
}

//--------------------------------------------------------------------------------
// 遍历二叉树方式
template<class T>
void BTreeBas<T>::traver_mode(int mode)
{
    cout << "二叉树结点总数：" << numbr << endl;
    switch(mode) {
       case 1: cout << "先根遍历递归算法：";
               predorder(root);  break;
       case 2: cout << "中根遍历递归算法：";
               inorder(root);  break;
       case 3: cout << "中根遍历非递归算法：";
               inorderz(root);  break;
       case 4: cout << "按层遍历递归算法：";
               levelorderz(root);  break;
    }
    cout << endl;   
}

template<class T>
void BTreeBas<T>::predorder(const BTNode<T> *p)
{
   if(p!=NULL) {
      cout << p->data << "  ";
      predorder(p->lch);       // 按先根次序遍历左子树
      predorder(p->rch);       // 按先根次序遍历右子树
   }
}

template<class T>
void BTreeBas<T>::inorder(const BTNode<T> *p)
{
   if(p!=NULL) {
      inorder(p->lch);
      cout << p->data << "  ";
      inorder(p->rch);
   }
}

template<class T>
void BTreeBas<T>::inorderz(BTNode<T> *p)
{
   stack<BTNode<T>* > S;
   BTNode<T> *q = p;
   do {                           // 进栈
      S.push(q);  
      q=q->lch;          
   } while(q!=NULL); 
   while(!S.empty()) {
      q = S.top();
      S.pop();                   // 出栈
      cout << q->data << "  ";   // 访问根结点
      q=q->rch;
      while(q!=NULL) {           // 进栈
         S.push(q); 
         q=q->lch;
      }
   }
}
// 按层遍历二叉树的算法
template<class T>
void BTreeBas<T>::levelorderz(BTNode<T> *p)
{
   queue<BTNode<T>* > Q;            // 声明一个结点指针队列
   if(p!=NULL) Q.push(p);           // 根结点入队
   while (!Q.empty()) {
      p = Q.front();
      Q.pop();                      // 出队
      cout << p->data << "  ";
      if(p->lch!=NULL) {
         Q.push(p->lch);            // p左孩子不空则入队
      } 
      if(p->rch!=NULL) {
         Q.push(p->rch);            // p右孩子不空则入队
      } 
   }
}
#endif