当前位置:编程学习 > C/C++ >>

二叉树-----二叉链表-----遍历(7种)

[cpp]  
//file:BTtree.h  
#ifndef _BTTREE_H_HUMING_INCLUDE_  
#define _BTTREE_H_HUMING_INCLUDE_  
#include<iostream>  
#include<queue>  
#include<stack>  
#define maxlen 100  
using namespace std;  
template <class T>  
class treenode  
{  
public:  
    treenode():lchild(NULL),rchild(NULL) {};  
    treenode(const T &v,treenode<T> *left,treenode<T> *right):data(v),lchild(left),rchild(right) {};  
    ~treenode()  
    {  
        delete lchild;  
        delete rchild;  
    }  
    treenode<T> *lchild,*rchild;  
    T data;  
};  
template <class T>  
class BTtree  
{  
public:  
    BTtree():root(NULL) {};  
    ~BTtree();  
    void pre_create();  
    bool Isempty();  
    treenode<T>* Lchild(treenode<T>* t);  
    treenode<T>* Rchild(treenode<T>* t);  
    T element(treenode<T>* t);  
    treenode<T>* return_root();  
    void pre_order(treenode<T>* t);  
    void in_order(treenode<T>* t);  
    void post_order(treenode<T>* t);  
    void nrec_pre_order(treenode<T>* t);  
    void nrec_in_order(treenode<T>* t);  
    void nrec_post_order(treenode<T>* t);  
    void level_order(treenode<T>* t);  
private:  
    treenode<T> *root;  
    void clear(treenode<T>* t);  
    treenode<T>*insert();  
};  
  
template<class T>  
BTtree<T>::~BTtree()  
{  
    clear(root);  
    delete root;  
}  
template <class T>  
void BTtree<T>::clear(treenode<T>* t)  
{  
    if(t==NULL) return;  
    else  
    {  
        clear(t->lchild);  
        clear(t->rchild);  
        t=NULL;  
    }  
}  
template <class T>  
void BTtree<T>::pre_create()  
{  
    root=insert();  
}  
template<class T>  
treenode<T>* BTtree<T>::insert()  
{  
    T ch;  
    treenode<T> *t;  
    cin >> ch;  
    if(ch=='#')  t=NULL;  
    else  
    {  
        t=new treenode<T>;  
        t->data=ch;  
        t->lchild=insert();  
        t->rchild=insert();  
    }  
    return t;  
}  
template<class T>  
bool BTtree<T>::Isempty()  
{  
    return root?false:true;  
}  
template <class T>  
treenode<T>* BTtree<T>::Lchild(treenode<T>* t)  
{  
    return t->lchild?t->lchild:NULL;  
}  
template <class T>  
treenode<T>* BTtree<T>::Rchild(treenode<T>* t)  
{  
    return t->rchild?t->rchild:NULL;  
}  
template <class T>  
T BTtree<T>::element(treenode<T>* t)  
{  
    return t->data;;  
}  
template <class T>  
void BTtree<T>::pre_order(treenode<T>* t)  
{  
    if(t!=NULL)  
    {  
        cout << t->data;  
        pre_order(t->lchild);  
        pre_order(t->rchild);  
    }  
}  
template <class T>  
treenode<T>* BTtree<T>::return_root()  
{  
    return root;  
}  
template <class T>  
void BTtree<T>::in_order(treenode<T>* t)  
{  
    if(t!=NULL)  
    {  
        in_order(t->lchild);  
        cout << t->data;  
        in_order(t->rchild);  
    }  
}  
template <class T>  
void BTtree<T>::post_order(treenode<T>* t)  
{  
    if(t!=NULL)  
    {  
        post_order(t->lchild);  
        post_order(t->rchild);  
        cout << t->data;  
    }  
}  
template <class T>  
void BTtree<T>::nrec_pre_order(treenode<T>* t)  
{  
    stack<treenode<T>*> s;  
    while(t!=NULL||!s.empty())  
    {  
        while(t!=NULL)  
        {  
            cout << t->data;  
            s.push(t);  
            t=t->lchild;  
        }  
        if(!s.empty())  
        {  
            t=s.top();  
            s.pop();  
            t=t->rchild;  
        }  
    }  
}  
template <class T>  
void BTtree<T>::nrec_in_order(treenode<T>* t)  
{  
    stack<treenode<T>*> s;  
    while(t!=NULL||!s.empty())  
    { &
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,