二叉树的模板实现

#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++ 阅读(1456) 评论(1) 编辑收藏引用所属分类: STL

Feedback

# re: 二叉树的模板实现 2007-06-13 23:58 hello

有没有stack.h的头文件亚？回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 比饶口令还饶口的复杂声明二叉树的模板实现

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

SEMAN

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

收藏夹

C/C++

搜索

最新评论

阅读排行榜

评论排行榜

Feedback