//--------------------------------------------------------------------------------
#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