c++二叉樹的幾種遍歷算法
更新時間：2013年02月19日 11:52:31 作者：
c++二叉樹的幾種遍歷算法，需要的朋友可以參考一下
1. 前序/中序/后序遍歷（遞歸實現(xiàn)）
復制代碼 代碼如下:
// 前序遍歷
void BT_PreOrder(BiTreePtr pNode){
if (!pNode) return;
visit(pNode);
BT_PreOrder(pNode->left);
BT_PreOrder(pNode->right); }
// 中序遍歷
void BT_PreOrder(BiTreePtr pNode){
if (!pNode) return;
BT_PreOrder(pNode->left);
visit(pNode);
BT_PreOrder(pNode->right);}
// 后序遍歷void BT_PreOrder(BiTreePtr pNode){
if (!pNode) return;
BT_PreOrder(pNode->left);
BT_PreOrder(pNode->right);
visit(pNode);}
2. 前序遍歷（非遞歸實現(xiàn)）
復制代碼 代碼如下:
// 用棧實現(xiàn)
void BT_PreOrderNoRec1(BiTreePtr pNode){
stack<BiTreePtr> s;
while (!pNode || !s.empty())
{
if (!pNode)
{
visit(pNode);
s.push(pNode);
pNode = pNode->left;
}
else
{
pNode = s.pop();
pNode = pNode->right;
}
}
}
// 用棧實現(xiàn)
void BT_PreOrderNoRec2(BiTreePtr pNode){
if (!pNode)
{
stack<BiTreePtr> s;
s.push(pNode);
while (!s.empty())
{
BiTreePtr pvNode = s.pop();
visit(pvNode);
s.push(pvNode->right);
s.push(pvNode->left);
}
}}
//
不用棧實現(xiàn) 每個節(jié)點含父節(jié)點指針和isVisited【默認為false】狀態(tài)變量 且該二叉樹含一個頭節(jié)點
void BT_PreOrderNoRec3(BiTreePtr pNode){
while (!pNode)
// 回溯到指向根節(jié)點的頭節(jié)點時退出
{
if( !pNode->bVisited )
// 判定是否已被訪問
{
visit(pNode);
pNode->isVisited = true;
}
if ( pNode->left && !pNode->left->isVisited )
pNode = pNode->left;
else if( pNode->right && !pNode->right->isVisited )
pNode = pNode->right;
else
//回溯
pNode = pNode->parent;
}}
3. 中序遍歷（非遞歸實現(xiàn)）
復制代碼 代碼如下:
// 用棧實現(xiàn)
void BT_InOrderNoRec1(BiTreePtr pNode){
stack<BiTreePtr> s;
while (!pNode || !s.empty())
{
if (!pNode)
{
s.push(pNode);
pNode = pNode->left;
}
else
{
pNode = s.pop();
visit(pNode);
pNode = pNode->right;
}
}}
// 不用棧實現(xiàn) 每個節(jié)點含父節(jié)點指針和isVisited【默認為false】的狀態(tài)變量 且該二叉樹含一個頭節(jié)點
void BT_InOrderNoRec2(BiTreePtr pNode){
while (!pNode)
// 回溯到指向根節(jié)點的頭節(jié)點時退出
{
while (pNode->left && !pNode->left->isVisited)
pNode = pNode->left;
if (!pNode->isVisited)
{
visit(pNode);
pNode->isVisited=true;
}
if (pNode->right && !pNode->right->isVisited)
pNode = pNode->right;
else
pNode = pNode->parent;
}}
4. 后序遍歷（非遞歸實現(xiàn)）
復制代碼 代碼如下:
void BT_PostOrderNoRec(BiTreePtr pNode){
if(!pNode) return;
stack<BiTreePtr> s;
s.push(pNode);
while (!s.empty())
{
BiTreePtr pvNode = s.pop();
if (pvNode->isPushed)
// 表示其左右子樹都已入棧，訪問該節(jié)點
visit(pvNode);
else
{
if (pvNode->right)
{
pvNode->right->isPushed = false;
S.push(pvNode->right);
}
if (pvNode->left)
{
pvNode->left->isPushed = false;
s.push(pvNode->left);
}
pvNode->isPushed = true;
s.push(pvNode);
}
}}
5. 層序遍歷（使用隊列）
復制代碼 代碼如下:
void BT_LevelOrder(BiTreePtr pNode){
if (!pNode) return;
queue<BiTreePtr> q;
q.push(pNode);
BiTreePtr pvNode;
while (!q.empty())
{
pvNode = q.pop();
visit(pvNode);
if (pvNode->left)
q.push(pvNode->left);
if (pvNode->right)
q.push(pvNode->right);
}}
相關文章
大家好，本篇文章主要講的是用c語言實現(xiàn)一個通訊錄代碼詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了c++ 如何合并兩個有序鏈表,幫助大家更好的理解和學習C++,感興趣的朋友可以了解下2020-08-08
先前把C++類和對象的封裝講完了，并且留下了一個判斷兩個立方體是否相等的案例，但是那么多知識點，僅僅一個案例是不夠的，所以再來一個分文件編寫點圓關系的案例；創(chuàng)建圓類和點類，圓類包含點類，算是一個嵌套吧，順便復習一下分文件編寫的方法，開整2022-05-05
詳解C語言的exp()函數(shù)和ldexp()函數(shù)以及frexp()函數(shù)
這篇文章主要介紹了詳解C語言的exp()函數(shù)和ldexp()函數(shù)以及frexp()函數(shù),注意這三個函數(shù)雖然看起來相似但實際功能卻大相徑庭!需要的朋友可以參考下2015-08-08
如何選擇合適的C++/C語言書籍，是不是已經(jīng)眼花繚亂，不知道該選擇哪本好了呢？今天我來為大家分享兩本不可錯過的優(yōu)秀書籍2017-09-09
這篇文章主要給大家介紹了關于C/C++中宏/Macro的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C/C++具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-06-06
本篇文章主要介紹了C++11返回類型后置語法的使用示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
C語言編程數(shù)據(jù)結構棧與隊列的全面講解示例教程
本文介紹著重介紹數(shù)據(jù)結構-棧和隊列的知識，由于本文也設計多個動態(tài)內(nèi)存開辟函數(shù)，小伙伴們在學習本文之前，一定一定一定要把動態(tài)內(nèi)存開辟相關知識掌握牢固，這樣學習起本文才能事半功倍2021-10-10
std::count函數(shù)是一個非常實用的算法,它可以幫助我們快速統(tǒng)計給定值在指定范圍內(nèi)的出現(xiàn)次數(shù),本文主要介紹了C++中std::count函數(shù)介紹和使用場景,感興趣的可以了解一下2024-02-02
這篇文章主要介紹了C語言中數(shù)據(jù)的存儲詳解的相關資料,需要的朋友可以參考下2023-08-08