亚洲精选大片,亚洲精品系列,久久综合导航

[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 閱讀(970) 評論(2) 編輯收藏引用所屬分類: 數據結構

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。回復 更多評論

弱弱的說...刪除那段似乎刪了樹葉...留了個樹干 - -

2009-09-01 10:10 | Ocean.Tu

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。回復 更多評論

謝謝LS提醒，已經改了。
這些東西真麻煩哦。。

2009-09-01 12:37 | shly

刷新評論列表

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



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

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。回復 更多評論

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。回復 更多評論

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

l

[C++]二叉樹的鏈式描述。創建，遍歷，摧毀。

評論

導航

常用鏈接

留言簿(24)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

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

l

[C++]二叉樹的鏈式描述。創建，遍歷，摧毀。

評論

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。 回復 更多評論

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。 回復 更多評論

導航

常用鏈接

留言簿(24)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。回復更多評論

# re: [C++]二叉樹的鏈式描述。創建，遍歷，摧毀。回復更多評論