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);
}}
相關(guān)文章
這篇文章主要介紹了基于C++實現(xiàn)的各種內(nèi)部排序算法,非常經(jīng)典,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了詳解C++編程中的私有繼承和公有繼承,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
大家在學習C++的時候一定會學到STL（標準模板庫），這是C++標準庫中最重要的組成部分，它包含了常用的數(shù)據(jù)結(jié)構(gòu)和算法。今天呢，我們首先來學習STL中的vector容器2022-09-09
以下是分別是對new和malloc的區(qū)別進行了詳細的分析及介紹，需要的朋友可以過來參考下2013-09-09
本文主要介紹了C++中將string類型轉(zhuǎn)化為int類型的方法。具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02
這篇文章主要介紹了C++實現(xiàn)二叉樹及堆的示例代碼,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
淺析C語言中printf(),sprintf(),scanf(),sscanf()的用法和區(qū)別
以下是對C語言中printf(),sprintf(),scanf(),sscanf()的用法以及區(qū)別進行了詳細的分析介紹，需要的朋友可以參考下2013-07-07
既然在創(chuàng)建對象時有構(gòu)造函數(shù)（給成員初始化），那么在銷毀對象時應(yīng)該還有一個清除成員變量數(shù)據(jù)的操作咯，析構(gòu)函數(shù)與構(gòu)造函數(shù)功能相反，析構(gòu)函數(shù)不是完成對象的銷毀，局部對象銷毀工作是由編譯器完成的。而對象在銷毀時會自動調(diào)用析構(gòu)函數(shù)，完成類的一些資源清理工作2022-06-06
C++實現(xiàn)LeetCode(59.螺旋矩陣之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(59.螺旋矩陣之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
本文將詳細介紹建立雙向鏈表,實現(xiàn)對雙向鏈表的插入,刪除操作，需要了解的朋友可以參考下2012-11-11