SEMAN

曾经沧海难为水、除却巫山不是云
C++博客 首页 新随笔 联系 聚合 管理
  9 Posts :: 3 Stories :: 24 Comments :: 0 Trackbacks
二叉树的模板实现

 

#include "iostream.h"
#include "stdlib.h"
#include "stack.h"
#pragma once

template<class T>
class CBiTree{
    public: 
        CBiTree(void) { } 
        ~CBiTree(void) { }

         static struct _tagBiTNode {  
            T data;  
            struct _tagBiTNode* lchild;  
            struct _tagBiTNode* rchild; 
        };
    private:    
        typedef _tagBiTNode BiTNode,*BiTree;

    public: 
        bool CreateBiTree(BiTree& t); 
        bool PreOrderTraverse(BiTree t,void (*visit)(T data)); 
        bool PreOrderTraverseEx(BiTree t,void (*visit)(T data)); 
        bool InOrderTraverse(BiTree t,void (*visit)(T data)); 
        bool InOrderTraverseEx(BiTree t,void (*visit)(T data)); 
        bool PostOrderTraverse(BiTree t,void (*visit)(T data)); 
        bool PostOrderTraverseEx(BiTree t,void (*visit)(T data));  
        void CountLeaf(BiTree t,int& count); 
        int BiTreeDepth(BiTree t); //二叉排序树的操作 
        void CreateSortBiTree(BiTree &root,T* a,int n); 
        void InsertNode(BiTree &root,T e); 
        bool DeleteNode(BiTree &t,T& e); 
        bool SearchNode(BiTree t,T key,BiTree f,BiTree& p);
    private: 
        void deleteNode(BiTree& p);
};


//创建一个无序二叉树
template<typename T>
bool CBiTree<T>::CreateBiTree(BiTree& t){  
    int n; 
    cin>>n; 
    if(n==0) 
        t=NULL; 
    else {  
        if(!(t = new BiTNode)) 
            return false;  
        t->data = n;  
        CreateBiTree(t->lchild);  
        CreateBiTree(t->rchild); 
    }  
    return true;
}    

//先根遍历 递归表示
template<typename T>
bool CBiTree<T>::PreOrderTraverse(BiTree t,void (*visit)(T data)){ 
    if(t!=NULL) {  
        visit(t->data);  
        PreOrderTraverse(t->lchild,visit);  
        PreOrderTraverse(t->rchild,visit); 
    } 
    return false;
}

//先根遍历,栈表示
template<typename T>
bool CBiTree<T>::PreOrderTraverseEx(BiTree t,void (*visit)(T data)){ 
    try {  
        CStack<BiTree>::_tagStack s; //栈  
        CStack<BiTree> stack ;
              //if(stack == NULL)  // return false;
      BiTree p = new BiTNode;
      if(p == NULL)   
            return false;
      stack.InitStack(s);  
        p = t;  
        while(p||!stack.StackEmpty(s))  {   
            if(p){    
                visit(p->data);    
                stack.Push(s,p);    
                p = p->lchild;   
            }   
            else{    
                stack.Pop(s,p);        
                p = p->rchild;   
            }  
        }  
        stack.DestroyStack(s);  
        return true; 
    } catch() {  
        visit(-1);  
        return false; 
    }
}

//中序遍历,递归算法
template<typename T>
bool CBiTree<T>::InOrderTraverse(BiTree t,void (*visit)(T data)){ 
    if(t != NULL) {  
        InOrderTraverse(t->lchild,visit);  
        visit(t->data);  
        InOrderTraverse(t->rchild,visit); 
    } 
    return true;
}

//中序遍历,栈表示
template<typename T>
bool CBiTree<T>::InOrderTraverseEx(BiTree t,void (*visit)(T data)){ 
    try {  
        CStack<BiTree>::_tagStack s;  
        CStack<BiTree> stack;
      BiTree p = new BiTNode;  
      p = t;  
      stack.InitStack(s);  
      while(p||!stack.StackEmpty(s))  {   
          if(p){
              stack.Push(s,p);    
              p = p->lchild;   
          }   
          else{
              stack.Pop(s,p);    
              visit(p->data);    
              p = p->rchild;   
          }  
      }  
      stack.DestroyStack(s);  
      return true; 
      } catch() {  
          visit(-1);  
          return false; 
          }
}

//后序遍历,递归算法
template<class T>
bool CBiTree<T>::PostOrderTraverse(BiTree t,void (*visit)(T data)){ 
    if(t != NULL) {  
        PreOrderTraverse(t->lchild,visit);  
        PreOrderTraverse(t->rchild,visit);  
        visit(t->data); 
        } 
    return true;
}

//后序遍历,栈表示
template<class T>
bool CBiTree<T>::PostOrderTraverseEx(BiTree t,void (*visit)(T data)){ 
    try {  
        CStack<BiTree>::_tagStack s;  
            CStack<BiTree> stack;  
            BiTree p = new BiTNode;  
            p = t;  
            stack.InitStack(s);  
            while(p||!stack.StackEmpty(s))  {   
                if(p){    
                    stack.Push(s,p->lchild);    
                    p = p ->lchild;   
                }   
                else{ 
                    visit(p->data);    
                    stack.Pop(s,p);    
                    p = p->rchild;    
                    visit(p->data);   
                }
          }  
          return true; 
      } catch() {  
          visit(-1);  
          return false; 
          }
}

//计数树叶的个数
template<class T>
void CBiTree<T>::CountLeaf(BiTree t,int& count){ 
    if(t != NULL) {  
        CountLeaf(t->lchild,count);  
        CountLeaf(t->rchild,count);  //检查结点t是否为叶子结点,若是,则定量count++  
        if(t->lchild == NULL &&t->rchild ==NULL)   
            count++; 
    }
}

//树的深度
template<class T>
int CBiTree<T>::BiTreeDepth(BiTree t){ 
    int dep; 
    int depleft; 
    int deprigth ;
     if( t==NULL)  
         dep = -1; 
     if( t != NULL ) {
         depleft = BiTreeDepth(t->lchild);  
         deprigth = BiTreeDepth(t->rchild);  
         dep = 1 + ( depleft>deprigth? depleft:deprigth); 
     }   
     return dep;
}

// 
template<class T>    
bool CBiTree<T>::SearchNode(BiTree t,T key,BiTree f,BiTree& p){ 
    if(t == NULL){
        p = f;  
        return false; 
    }
    else if(key == t->data)  {   
        p = t;   
        return true;  
    } 
    else if(key < t->data)  {   
        SearchNode(t->lchild,key,t,p);  
    } 
    else  
        SearchNode(t->rchild,key,t,p);
}

template<class T>
void CBiTree<T>::InsertNode(BiTree &root,T e){ 
    BiTree t = root; 
    BiTree p = NULL; 
    BiTree newNode = new BiTNode;  
    while(t) {  
        p = t;  
        if(e <=t->data)   
            t = t->lchild;  
        else   
            t = t->rchild; 
    } 
    newNode->data = e; 
    newNode->lchild = newNode->rchild =NULL; 
    if(p==NULL)  
        root = newNode; 
    else  
        if(e <p->data)   
            p->lchild = newNode;  
        else   
            p->rchild = newNode; 
}
//找到要删除的结点,删除结点
template<class T>
void CBiTree<T>::deleteNode(BiTree& p){ 
    BiTree q; 
    BiTree s; 
    if(!p->lchild) {  
        q = p;  
        p = p->rchild;  
        free(q); 
    } 
    else if(!p->rchild) {  
        q = p;  
        p = p->lchild;  
        free(q); 
    } 
    else {   
        q = p;   
        s = p->lchild;   
        while(s->rchild){
            q = s;    
            s = s->rchild;   
        }
        p->data = s->data;   
        if(q!=p)     
            q->rchild = s->lchild;   
        else    
            q->lchild = s->lchild; 
        }
}

//查找要删除的结点,并删除
template<class T>
bool CBiTree<T>::DeleteNode(BiTree &t,T& e){ 
    if(!t)  
        return false; 
    else {  
        if(e == t->data)   
            deleteNode(t);  
        else 
            if(e < t->data)   
                DeleteNode(t->lchild,e);  
            else    
                DeleteNode(t->rchild,e);  
            return true; 
    }
}// n 为数据的总长度 用n = sizeof(a) / sizeof(a[0]);

template<class T>
void CBiTree<T>::CreateSortBiTree(BiTree &root,T* a,int n){ 
    for(int i=0;i<n;i++) {  
        InsertNode(root,a[i]); 
    }
}
/**************************************************************test**************************************************************/

void print(int data){ 
    if(data == -1)  
        cout<<"\nError"<<endl; 
        cout<<data<<"\t"; 
}

int _tmain(int argc, _TCHAR* argv[]){
    cout<<"\nBiTree:-----------------------\n"; 
    CBiTree<int>::_tagBiTNode *p1= NULL;
    CBiTree<int>* tree = new CBiTree<int>; 
     cout<<"\n树的深度为:"<<tree->BiTreeDepth(t)<<endl; 
     int n=0;
     int a[]={8,6,9,10,23,2,3,0,4,0,5};
     tree->CreateSortBiTree(p1,a,sizeof(a)/sizeof(a[0]));  
     cout<<"\n前序遍历\n"; 
     tree->PreOrderTraverse(p1,&print); 
     cout<<"\n"; 
     tree->PreOrderTraverseEx(p1,&print); 
     cout<<"\n中序遍历\n"<<endl; 
     tree->InOrderTraverse(p1,&print); 
     cout<<"\n"; 
     tree->InOrderTraverseEx(p1,&print); 
     tree->CountLeaf(p1,n); 
     cout<<"\n树的深度为:"<<tree->BiTreeDepth(p1)<<endl;
    cout<<"叶子:"<<n<<endl;
     cout<<"查找"<<endl; 
     int k0=3; 
     if(tree->SearchNode(p1,3,NULL,t)) {  
         cout<<"找到了"<<endl;  
         tree->DeleteNode(p1,k0);  
         tree->InOrderTraverse(p1,&print); 
     }else  
         cout<<"没找到"<<endl;
}
posted on 2005-10-24 11:06 味全每日C++ 阅读(1430) 评论(1)  编辑 收藏 引用 所属分类: STL

Feedback

# re: 二叉树的模板实现 2007-06-13 23:58 hello
有没有stack.h的头文件亚？  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理