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 阅读(935) 评论(2)  编辑 收藏 引用 所属分类: 数据结构

评论

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

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

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

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

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