二叉树的基本操作

#include<iostream>
using namespace std;

/*
  定义二叉树的数据结构 
*/ 
  
  int MAXSIZE = 100;
  
  typedef struct Node{
        
       char data;
       struct Node* lchild;
       struct Node* rchild; 
   }*BitTree,BitNode; 

 //声明与二叉树相关的操作函数
   
    //1.初始化二叉树
   void InitBitTree(BitTree &T);
    //2.创建二叉树的操作
   void CreateBitTree(BitTree &T);
    //3.先序遍历二叉树
   void PreOrderBitTree(BitTree &T);
     //4.中序遍历二叉树
   void InOrderBitTree(BitTree &T);
    // 5.后序遍历二叉树
   void PostOrderBitTree(BitTree &T);
    //6.二叉树的层次遍历
   void LevelOrderBitTree(BitTree &T);
    //8.返回二叉树的叶子节点的个数
   int LeafNum(BitTree &T);
    //7.求二叉树的高度
   int BitTreeDepth(BitTree &T);
 
 
 
    //1.初始化二叉树
   void InitBitTree(BitTree &T){
        
        T = NULL;
   }
   
   
   //2.创建二叉树的操作
   void CreateBitTree(BitTree &T){
        
       char ch;
       cin>>ch;
      
      if(ch=='#')  { T = NULL;}
      else{
         T = (BitTree)malloc(sizeof(BitNode));
         if(T==NULL){
                     
            exit(-1);            
         }
         T->data = ch;
         CreateBitTree(T->lchild);
         CreateBitTree(T->rchild);
      }   
    
 }
    //3.先序遍历二叉树,采用非递归的方式遍历二叉树 
   void PreOrderBitTree(BitTree &T){
        
        BitTree  stack[MAXSIZE];
        int top = 0;
        BitTree p = T;
        while(p!=NULL||top>0){
                              
            while(p!=NULL){
              cout<<p->data<<" ";
              stack[top++] = p;
              p=p->lchild;              
            }                      
         if(top>0){
           
            p = stack[--top];
            p = p->rchild;        
         }      
     }
    cout<<endl;
}
 
   //4.中序遍历二叉树,采用非递归的方式遍历二叉树 
   void InOrderBitTree(BitTree &T){
        
          
        BitTree  stack[MAXSIZE];
        int top = 0;
        BitTree p = T;
        while(p!=NULL||top>0){
                              
            while(p!=NULL){
             
              stack[top++] = p;
              p=p->lchild;              
            }                      
         if(top>0){
           
            p = stack[--top];
            cout<<p->data<<" ";
            p = p->rchild;        
         }      
     }
    cout<<endl;
 }
 
    // 后序遍历二叉树,采用非递归的方式遍历二叉树 
   void PostOrderBitTree(BitTree &T){
       BitTree  stack[MAXSIZE];
       int top = 0;
       BitTree p = T;
       BitTree q = NULL;
        while(p!=NULL||top>0){
                              
            while(p!=NULL){
             
              stack[top++] = p;
              p=p->lchild;              
            }                      
         if(top>0){
           p = stack[top-1];
           if(p->rchild == NULL||p->rchild == q){
           
             cout<<p->data<<" ";
             top--;
             q=p;
             p=NULL;
                        
           }else{
             p = p->rchild;        
         }
       }      
   }
   cout<<endl;
}

   //6.二叉树的层次遍历
   void LevelOrderBitTree(BitTree &T){
        BitTree Queue[MAXSIZE];
        int front = -1;
        int rear = -1;
        rear++;
        Queue[rear] = T;
        BitTree p = NULL;
      while(front!=rear){
                         
          front = (front+1)%MAXSIZE;    
          p = Queue[front];
         cout<<p->data<<" ";
         if(p->lchild!=NULL){
         rear = (rear+1)%MAXSIZE;         
         Queue[rear] = p->lchild;                    
         }
         if(p->rchild!=NULL){
         rear = (rear+1)%MAXSIZE;         
         Queue[rear] = p->rchild;                    
         }
                    
      }
    cout<<endl;
   }
   
    //8.返回二叉树的叶子节点的个数
   int LeafNum(BitTree &T){
       
       if(!T) return 0;
       if(!(T->lchild)&&!(T->rchild))
       return 1;
       else
       return LeafNum(T->lchild)+LeafNum(T->rchild);
       
   }
    //7.求二叉树的高度
   int BitTreeDepth(BitTree &T){
       
       if(!T) return 0;
       
       int lh = BitTreeDepth(T->lchild);
       int rh = BitTreeDepth(T->rchild);
       return lh>rh?1+lh:1+rh;
       
   }
 
 
 int main(){
     
     BitTree T;
   
     cout<<"创建一个二叉树:"<<endl;
     CreateBitTree(T);
     
     cout<<"线序遍历二叉树:"<<endl; 
     PreOrderBitTree(T);
     
     cout<<"中序遍历二叉树:"<<endl;
     InOrderBitTree(T);
     
     cout<<"后序遍历二叉树:"<<endl;
     PostOrderBitTree(T);
     
     cout<<"按层次遍历二叉树:"<<endl;
     LevelOrderBitTree(T);
     
     cout<<"输出二叉树的叶子节点个数:"<<endl;
     cout<<LeafNum(T)<<endl;
     
     cout<<"输出二叉树的高度:"<<endl;
     cout<<BitTreeDepth(T)<<endl;
     
    system("pause");
    
    return 0;      
     
 }