//二叉樹類定義btree.h
template<class T>class BTree {
 private:
  BTree<T> *left;//左子樹指針
  BTree<T> *right;//右子樹指針
 public:
  T data;//數據域
//構造函數,初始化二叉樹為空
  BTree() {left=right=NULL;}
  BTree(T item,BTree<T> *left1=NULL,
    BTree<T> *right1=NULL):data(item),
    left(left1),right(right1){ }
  BTree<T> *&Left(){return left;}
  BTree<T> *&Right(){return right;}
//根據字符數組a的二叉樹廣義表建立對應的二叉樹存儲結構
  void CreateBTree(char* a);
//判斷二叉樹是否為空
  bool BTreeEmpty() {return left==NULL;}
//按任一種遍歷次序輸出二叉樹中的所有結點
  void TraverseBTree(int mark);
//用于遍歷的遞歸函數
  void Traverse(BTree<T> *&BT,int mark);
//求二叉樹的深度
  int BTreeDepth();
//用于求二叉樹深度的遞歸函數
  int Depth(BTree<T> *&BT);
//求二叉樹中所有結點數
  int BTreeCount();
//用于求二叉樹中所有結點數的遞歸函數
  int Count(BTree<T> *&BT);
//求二叉樹中所有葉子結點數
  int BTreeLeafCount();
//用于求二叉樹中所有葉子結點數的遞歸函數
  int LeafCount(BTree<T> *&BT);
//按照二叉樹的一種表示方法輸出整個二叉樹
  void PrintBTree();
//用于輸出整個二叉樹的遞歸函數
  void Print(BTree<T> *&BT);
//用于清除二叉樹的遞歸函數
  void Clear(BTree<T> *&BT);
//析構函數，清除二叉樹
  ~BTree();
};
//二叉樹類的實現btree.cpp
//根據字符數組a的二叉樹廣義表建立對應的二叉樹存儲結構
template<class T>
void BTree<T>::CreateBTree(char *a)
{BTree<T> *s[80];//s數組作為存儲二叉樹中根結點指針的棧
 int top=-1;      //top作為s棧的棧頂指針
 left=NULL;       //先將left作為樹根指針給予置空
 BTree<T> *p=NULL;//定義p為指向二叉樹結點的指針
 //用k作為處理結點的左子樹和右子樹的標記,k=1處理左子樹,k=2處理右子樹
 int k;
 istrstream ins(a);//把字符串a定義為輸入字符串流對象ins
 char ch;
 ins>>ch;//從ins流對象順序讀入一個字符，
 while (ch!='@')
 {//每循環一次處理一個讀入的字符,直到掃描到'@'字符為止
  switch(ch)
    {case '(':top++;s[top]=p;k=1;break;
     case ')':top--;break;
     case ',':top++;k=2;break;
     default:p=new BTree<T>;
       p->data=ch;p->left=p->right=NULL;
       cout<<setw(2)<<p->data;
       if(left==NULL) left=p;
       else {
	if(k==1) s[top]->left=p;
        else s[top]->right=p;}
    }
  ins>>ch;
 }
}
//按任一種遍歷次序輸出二叉樹中的所有結點
template<class T>
void BTree<T>::TraverseBTree(int mark)
{Traverse(left,mark);}

//用于遍歷的遞歸函數
template<class T>
void BTree<T>::Traverse(BTree<T> *&BT,int mark)
{if(mark==1){ //先序遍歷
  if(BT!=NULL)
   {cout<<BT->data<<' ';
    Traverse(BT->left,mark);
    Traverse(BT->right,mark);
   }}
 else
  if(mark==2)//中序遍歷
   {if(BT!=NULL)
     {Traverse(BT->left,mark);
      cout<<BT->data<<' ';
      Traverse(BT->right,mark);
    }}
  else
   if(mark==3) {//后序遍歷
     if(BT!=NULL) {
      Traverse(BT->left,mark);
      Traverse(BT->right,mark);
      cout<<BT->data<<' ';
    }}
  else
   if(mark==4) //按層遍歷
    {const MaxLength=80;
     BTree<T> *Q[MaxLength];
    //定義存儲二叉樹結點指針的數組空間作為隊列使用
     int front=0, rear=0;
    //定義隊首指針和隊尾指針,初始均置0表示空隊
    BTree<T> *p;
    if(BT!=NULL) {
     rear=(rear+1)%MaxLength;  //后移隊尾指針
     Q[rear]=BT;}              //將樹根結點指針進隊
    while(front!=rear)
     {//當隊列非空時執行循環
      front=(front+1)%MaxLength;
      //后移隊首指針
      p=Q[front];
      //刪除隊首結點
      cout<<p->data<<' ';
      //輸出隊首結點的值
      if(p->left!=NULL)
       {//若結點存在左孩子，則左孩子結點指針進隊
	rear=(rear+1)%MaxLength;
        Q[rear]=p->left;
       }
      if(p->right!=NULL)
       {//若結點存在右孩子,則右孩子結點指針進隊
	rear=(rear+1)%MaxLength;
	Q[rear]=p->right;
       }
      }
     }
   else
    {cerr<<"mark的值無效!遍歷失敗!"<<endl;exit(1);
}}
//求二叉樹的深度
template<class T>
int BTree<T>::BTreeDepth()
{return Depth(left);}

//用于求二叉樹深度的遞歸函數
template<class T>
int BTree<T>::Depth(BTree<T> *&BT)
{if(BT==NULL) return 0;//對于空樹,返回0并結束遞歸
 else
   {//計算左子樹的深度
    int dep1=Depth(BT->left);
    //計算右子樹的深度
    int dep2=Depth(BT->right);
    //返回樹的深度
    if(dep1>dep2) return dep1+1;
    else return dep2+1;
   }
}
//求二叉樹中所有結點數
template<class T>
int BTree<T>::BTreeCount()
{return Count(left);}

//用于求二叉樹中所有結點數的遞歸函數
template<class T>
int BTree<T>::Count(BTree<T> *&BT)
{if(BT==NULL) return 0;
 else
  return Count(BT->left)+Count(BT->right)+1;
}
//求二叉樹中所有葉子結點數
template<class T>
int BTree<T>::BTreeLeafCount()
{return LeafCount(left);}

//用于求二叉樹中所有葉子結點數的遞歸函數
template<class T>
int BTree<T>::LeafCount(BTree<T> *&BT)
{if(BT==NULL) return 0;
 else if(BT->left==NULL && BT->right==NULL) return 1;
  else return LeafCount(BT->left)+LeafCount(BT->right);
}
//按照二叉樹的廣義表表示輸出整個二叉樹
template<class T>
void BTree<T>::PrintBTree()
{Print(left);}

//用于輸出整個二叉樹的遞歸函數
template<class T>
void BTree<T>::Print(BTree<T> *&BT)
{if(BT==NULL) return;//樹為空時返回
 else {//否則執行如下操作
  cout<<BT->data;//輸出根結點的值
  if(BT->left!=NULL || BT->right!=NULL)
   {cout<<'(';  //輸出左括號
    Print(BT->left);//輸出左子樹
    if(BT->right!=NULL)
     cout<<',';//若右子樹不為空則輸出逗號分隔符
    Print(BT->right);//輸出右子樹
    cout<<')';} //輸出右括號
}}
//析構函數,清除二叉樹
template<class T>
BTree<T>::~BTree()
{Clear(left);}
//用于清除二叉樹的遞歸函數
template<class T>
void BTree<T>::Clear(BTree<T> *&BT)
{if(BT!=NULL)
   { //當二叉樹非空時進行如下操作
    Clear(BT->left); //刪除左子樹
    Clear(BT->right);//刪除右子樹
    delete BT;       //刪除根結點
    BT=NULL;}        //置根指針為空
}
//二叉樹類相關操作的測試btreeM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<strstrea.h>
#include "btree.h"
#include "btree.cpp"
void main()
{cout<<"btreeM.cpp運行結果:\n";
 int n;
 char b[80]="(a)(b),c(d),e(f),g(h),i(j),k(l),m(n),o@";
 BTree<char> B;
 cout<<"創建的二叉樹為:\n";
 B.CreateBTree(b);cout<<endl;
 if(!B.BTreeEmpty())
   cout<<"二叉樹非空!\n";
 else
   cout<<"二叉樹為空!\n";
 cout<<"先序遍歷二叉樹:\n";
 B.TraverseBTree(1);cout<<endl;
 cout<<"中序遍歷二叉樹:\n";
 B.TraverseBTree(2);cout<<endl;
 cout<<"后序遍歷二叉樹:\n";
 B.TraverseBTree(3);cout<<endl;
 cout<<"按層遍歷二叉樹:\n";
 B.TraverseBTree(4);cout<<endl;
 n=B.BTreeDepth();
 cout<<"二叉樹的深度="<<n<<endl;
 n=B.BTreeCount();
 cout<<"二叉樹的所有結點數="<<n<<endl;
 n=B.BTreeLeafCount();
 cout<<"二叉樹的所有葉子結點數="<<n<<endl;
 cout<<"按二叉樹的廣義表輸出:\n";
 B.PrintBTree();cout<<endl;
 cin.get();}
btreeM.cpp運行結果:
創建的二叉樹為:
 a b c d e f g h i j k l m n o
二叉樹非空!
先序遍歷二叉樹:
a b c d e f g h i j k l m n o 
中序遍歷二叉樹:
b a d c f e h g j i l k n m o 
后序遍歷二叉樹:
b d f h j l n o m k i g e c a 
按層遍歷二叉樹:
a b c d e f g h i j k l m n o 
二叉樹的深度=8
二叉樹的所有結點數=15
二叉樹的所有葉子結點數=8
按二叉樹的廣義表輸出:
a(b,c(d,e(f,g(h,i(j,k(l,m(n,o)))))))