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

//用于遍歷的遞歸函數(shù)
template<class T>
void BinaryTree<T>::Traverse(BTreeNode<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;
     BTreeNode<T> *Q[MaxLength];
    //定義存儲(chǔ)二叉樹結(jié)點(diǎn)指針的數(shù)組空間作為隊(duì)列使用
     int front=0, rear=0;
    //定義隊(duì)首指針和隊(duì)尾指針,初始均置0表示空隊(duì)
    BTreeNode<T> *p;
    if(BT!=NULL) {
     rear=(rear+1)%MaxLength;  //后移隊(duì)尾指針
     Q[rear]=BT;}              //將樹根結(jié)點(diǎn)指針進(jìn)隊(duì)
    while(front!=rear)
     {//當(dāng)隊(duì)列非空時(shí)執(zhí)行循環(huán)
      front=(front+1)%MaxLength;
      //后移隊(duì)首指針
      p=Q[front];
      //刪除隊(duì)首結(jié)點(diǎn)
      cout<<p->data<<' ';
      //輸出隊(duì)首結(jié)點(diǎn)的值
      if(p->left!=NULL)
       {//若結(jié)點(diǎn)存在左孩子，則左孩子結(jié)點(diǎn)指針進(jìn)隊(duì)
	rear=(rear+1)%MaxLength;
        Q[rear]=p->left;
       }
      if(p->right!=NULL)
       {//若結(jié)點(diǎn)存在右孩子,則右孩子結(jié)點(diǎn)指針進(jìn)隊(duì)
	rear=(rear+1)%MaxLength;
	Q[rear]=p->right;
       }
      }
     }
   else
    {cerr<<"mark的值無(wú)效!遍歷失敗!"<<endl;exit(1);
}}
//求二叉樹的深度
template<class T>
int BinaryTree<T>::BTreeDepth()
{return Depth(root);}

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

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

//用于求二叉樹中所有葉子結(jié)點(diǎn)數(shù)的遞歸函數(shù)
template<class T>
int BinaryTree<T>::LeafCount(BTreeNode<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);
}
//按照二叉樹的廣義表表示輸出整個(gè)二叉樹
template<class T>
void BinaryTree<T>::PrintBTree()
{Print(root);}

//用于輸出整個(gè)二叉樹的遞歸函數(shù)
template<class T>
void BinaryTree<T>::Print(BTreeNode<T> *&BT)
{if(BT==NULL) return;//樹為空時(shí)返回
 else {//否則執(zhí)行如下操作
  cout<<BT->data;//輸出根結(jié)點(diǎn)的值
  if(BT->left!=NULL || BT->right!=NULL)
   {cout<<'(';  //輸出左括號(hào)
    Print(BT->left);//輸出左子樹
    if(BT->right!=NULL)
     cout<<',';//若右子樹不為空則輸出逗號(hào)分隔符
    Print(BT->right);//輸出右子樹
    cout<<')';} //輸出右括號(hào)
}}
//析構(gòu)函數(shù),清除二叉樹
template<class T>
BinaryTree<T>::~BinaryTree()
{Clear(root);}
//用于清除二叉樹的遞歸函數(shù)
template<class T>
void BinaryTree<T>::Clear(BTreeNode<T> *&BT)
{if(BT!=NULL)
   { //當(dāng)二叉樹非空時(shí)進(jìn)行如下操作
    Clear(BT->left); //刪除左子樹
    Clear(BT->right);//刪除右子樹
    delete BT;       //刪除根結(jié)點(diǎn)
    BT=NULL;}        //置根指針為空
}
//二叉樹類相關(guān)操作的測(cè)試btree2M.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<strstrea.h>
#include "btree2.h"
#include "btree2.cpp"

void main()
{cout<<"btree2M.cpp運(yùn)行結(jié)果:\n";
 int n;
 char b[80]="(a)(b),c(d),e(f),g(h),i(j),k(l),m(n),o@";
 BinaryTree<char> B;
 cout<<"創(chuàng)建的二叉樹為:\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<<"二叉樹的所有結(jié)點(diǎn)數(shù)="<<n<<endl;
 n=B.BTreeLeafCount();
 cout<<"二叉樹的所有葉子結(jié)點(diǎn)數(shù)="<<n<<endl;
 cout<<"按二叉樹的廣義表輸出:\n";
 B.PrintBTree();cout<<endl;
 cin.get();}
btree2M.cpp運(yùn)行結(jié)果:
創(chuàng)建的二叉樹為:
 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
二叉樹的所有結(jié)點(diǎn)數(shù)=15
二叉樹的所有葉子結(jié)點(diǎn)數(shù)=8
按二叉樹的廣義表輸出:
a(b,c(d,e(f,g(h,i(j,k(l,m(n,o)))))))