l

成都手游码农一枚
随笔 - 32, 文章 - 0, 评论 - 117, 引用 - 0
数据加载中……

[C++]二叉树的链式描述。创建，遍历，摧毁。

前段时间写的，不好的地方请支持，谢谢。

/*********************************************************
FileName:BinaryTree.cpp
Author    :shly
Date    :2009.9.1
E-mail    :xlq1989@vip.qq.com
*二叉树的链式描述。创建，遍历，摧毁。
*********************************************************/
#include <iostream>
#include <deque>
#include <cassert>
#include <cstring>
using namespace std;

template<typename _Ty>
struct BinNode
{
    BinNode():pLeft(NULL),pRight(NULL)
    {
    //    cout<<nNode<<endl;++nNode;
    }
    BinNode<_Ty> *pLeft, *pRight;
    _Ty    tData;

    //test---
    //~BinNode(){--nNode;cout<<nNode<<endl;}
    
//    static int nNode;
};
//template<typename _Ty>
//int BinNode<_Ty>::nNode=0;

template<typename _Ty>
class BinaryTree
{
    BinNode<_Ty>* pRoot;
public:
    BinaryTree():pRoot(NULL){}
    ~BinaryTree(){}
public:
//    void CreateBinTree(_Ty& tData);
    void CreateBinTree(_Ty* tpStart,int nSize);
    void DestroyBinTree();
//    void AddBinTree(BinaryTree* pLeft,BinaryTree* pRight);
    void PreOrder();
    void InOrder();
    void PostOrder();
    void LevelOrder();
    void Vista(const _Ty& tData);
private: 
    void _destroy(BinNode<_Ty>* pNode);
    void _pre(BinNode<_Ty>* pNode);
    void _in(BinNode<_Ty>* pNode);
    void _post(BinNode<_Ty>* pNode);
};

/*********************************************************
*Function    :CreateBinTree
*parameter    :_Ty tData
*return        :void
*为pRoot创建一个结点。
*********************************************************/
//template<typename _Ty>void BinaryTree<_Ty>::CreateBinTree(_Ty& tData){
//    assert(NULL==pRoot);
//    pRoot=new BinNode<_Ty>;
//    assert(NULL!=pRoot);
//
//    pRoot->tData=tData;
//    pRoot->pLeft=pRoot->pRight=NULL;
//}
/*********************************************************
*Function    :CreateBinTree
*parameter    :_Ty* tpStart,int nSize
*return        :void
*根据一组数据顺序生成一颗二叉树。
*********************************************************/
template<typename _Ty>
void BinaryTree<_Ty>::CreateBinTree(_Ty* tpStart,int nSize)
{
    assert(tpStart&&!pRoot&&nSize>0);

    deque<BinNode<_Ty>**> dq;
    dq.push_back(&pRoot);
    
    for(int i=0;i<nSize;)
    {
        BinNode<_Ty>** pb=dq.front();
        dq.pop_front();
        assert(NULL==(*pb));
        (*pb)=new BinNode<_Ty>;
        (*pb)->tData=tpStart[i++];
        dq.push_back(&(*pb)->pLeft);
        dq.push_back(&(*pb)->pRight);
    }
}
/*********************************************************
*Function    :AddBinTree
*parameter    :BinaryTree* pLeft,* pRight
*return        :void
*将两个子树组合成一个。
*********************************************************/
//template<typename _Ty>void BinaryTree<_Ty>::AddBinTree(BinaryTree* pLeft,BinaryTree* pRight){
//    assert(NULL!=pLeft);
//    assert(NULL!=pRight);
//    assert(NULL!=pRoot);
//    assert(NULL==pRoot->pLeft);
//    assert(NULL==pRoot->pRight);
//
//    pRoot->pLeft=pLeft;
//    pRoot->pRight=pRight;
//
//    pLeft=pRight=0;
//}
/*********************************************************
*Function    :DestroyBintree
*parameter    :void
*return        :void
*摧毁二叉树。
*********************************************************/
template<typename _Ty>void BinaryTree<_Ty>::_destroy(BinNode<_Ty>* pNode){
/*    if(NULL==pNode)return;
    if(NULL==pNode->pLeft
     &&NULL==pNode->pRight){
        delete pNode;
        static int i=0;
        ++i;
        cout<<i<<"__";
        pNode=NULL;
    //    cout<<"Destroy BinaryTree!"<<endl;
    }
    else{
        _destroy(pNode->pLeft);
        _destroy(pNode->pRight);
    }*/
    if(!pNode)return;
    _destroy(pNode->pLeft);
    _destroy(pNode->pRight);
    delete pNode;
    pNode=NULL;
}
template<typename _Ty>
inline void BinaryTree<_Ty>::DestroyBinTree()
{
    _destroy(pRoot);
}

/*********************************************************
*Function    :PreOrder
*parameter    :void
*return        :void
*先序遍历。
*********************************************************/
template<typename _Ty>
void BinaryTree<_Ty>::_pre(BinNode<_Ty>* pNode)
{
    if(!pNode)return;
    Vista(pNode->tData);
    _pre(pNode->pLeft);
    _pre(pNode->pRight);
}
template<typename _Ty>
inline void BinaryTree<_Ty>::PreOrder()
{
    _pre(pRoot);
}
/*********************************************************
*Function    :InOrder
*parameter    :void
*return        :void
*中序遍历。
*********************************************************/
template<typename _Ty>
void BinaryTree<_Ty>::_in(BinNode<_Ty>* pNode)
{
    if(!pNode)return;
    _in(pNode->pLeft);
    Vista(pNode->tData);
    _in(pNode->pRight);
}
template<typename _Ty>
inline void BinaryTree<_Ty>::InOrder()
{
    _in(pRoot);
}
/*********************************************************
*Function    :PostOrder
*parameter    :void
*return        :void
*后序遍历。
*********************************************************/
template<typename _Ty>
void BinaryTree<_Ty>::_post(BinNode<_Ty>* pNode)
{
    if(!pNode)return;
    _post(pNode->pLeft);
    _post(pNode->pRight);
    Vista(pNode->tData);
}
template<typename _Ty>
inline void BinaryTree<_Ty>::PostOrder()
{
    _post(pRoot);
}
/*********************************************************
*Function    :LevelOrder
*parameter    :void
*return        :void
*逐层遍历。
*********************************************************/
template<typename _Ty>
void BinaryTree<_Ty>::LevelOrder()
{
    if(!pRoot)return;
    deque<BinNode<_Ty>*> dq;
    dq.push_back(pRoot);
    while(!dq.empty())
    {
        BinNode<_Ty>* temp=dq.front();
        dq.pop_front();
        Vista(temp->tData);
        if(NULL!=temp->pLeft)
            dq.push_back(temp->pLeft);
        if(NULL!=temp->pRight)
            dq.push_back(temp->pRight);
    }
}
/*********************************************************
*Function    :Vista
*parameter    :const _Ty& tData
*return        :void
*访问操作。
*********************************************************/
template<typename _Ty>
void BinaryTree<_Ty>::Vista(const _Ty& tData)
{
    if(' '!=tData)
        cout<<tData<<" ";
}

int main()
{
    //char* arr="+*/abcd";
    //char* arr="++d+c  ab";
    char* arr="/+*-++* axy bca";
    BinaryTree<char> bt;
    bt.CreateBinTree(arr,strlen(arr));//创建二叉树
    bt.PreOrder();//先序遍历
    cout<<endl;
    bt.InOrder();//中序遍历
    cout<<endl;
    bt.PostOrder();//后序遍历
    cout<<endl;
    bt.LevelOrder();//逐层遍历
    cout<<endl;
    bt.DestroyBinTree();//摧毁二叉树
    return 0;
}

posted on 2009-09-01 00:58 l1989 阅读(938) 评论(2)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: [C++]二叉树的链式描述。创建，遍历，摧毁。  回复  更多评论   

弱弱的说...删除那段似乎删了树叶...留了个树干 - -
2009-09-01 10:10 | Ocean.Tu

# re: [C++]二叉树的链式描述。创建，遍历，摧毁。  回复  更多评论   

谢谢LS提醒，已经改了。
这些东西真麻烦哦。。
2009-09-01 12:37 | shly

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