SEMAN

曾經滄海難為水、除卻巫山不是云

C++博客

管理

9 Posts :: 3 Stories :: 24 Comments :: 0 Trackbacks

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

文章分類

搜索

閱讀排行榜

評論排行榜

二叉樹的模板實現

#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++ 閱讀(1532) 評論(1) 編輯收藏引用所屬分類: STL

Feedback

# re: 二叉樹的模板實現 2007-06-13 23:58 hello

有沒有stack.h的頭文件亞？回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 比饒口令還饒口的復雜聲明二叉樹的模板實現

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品