2018年的最后一個月，談大的理想抱負已經不夠時間來實現，但小計劃還是可以的，下面武林技術小編就給各位帶來這篇C++++實現二叉樹以及幾種遍歷方式，可能有些小伙伴都接觸過，但是這里還是要分享給大家，與君共勉，一起學習。
1. 前序/中序/后序遍歷（遞歸實現）
// 前序遍歷
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. 前序遍歷（非遞歸實現）
?
?
// 用棧實現
void BT_PreOrderNoRec1(BiTreePtr pNode){
stack s;
while (!pNode || !s.empty())?
{??????
if (!pNode)?
{???????????
visit(pNode);???
s.push(pNode);???????
pNode = pNode->left;??
}??????
else??????
{??????????
pNode = s.pop();
pNode = pNode->right;????
}?
}
}
// 用棧實現
void BT_PreOrderNoRec2(BiTreePtr pNode){
if (!pNode)??
{??????
stack s;?
s.push(pNode);?????
while (!s.empty())??
{??????????
BiTreePtr pvNode = s.pop();
visit(pvNode);?????????
s.push(pvNode->right);??????
s.push(pvNode->left);??
}??
}}
//
不用棧實現 每個節點含父節點指針和isVisited【默認為false】狀態變量 且該二叉樹含一個頭節點
void BT_PreOrderNoRec3(BiTreePtr pNode){???
while (!pNode)
// 回溯到指向根節點的頭節點時退出?
{???????
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. 中序遍歷（非遞歸實現）
// 用棧實現
void BT_InOrderNoRec1(BiTreePtr pNode){
stack s;
while (!pNode || !s.empty())??
{??????
if (!pNode)??????
{?????????
s.push(pNode);??????
pNode = pNode->left;???
}??
else??
{???????
pNode = s.pop();?
visit(pNode);??????
pNode = pNode->right;
}?
}}
// 不用棧實現 每個節點含父節點指針和isVisited【默認為false】的狀態變量 且該二叉樹含一個頭節點
void BT_InOrderNoRec2(BiTreePtr pNode){???
while (!pNode)
// 回溯到指向根節點的頭節點時退出
{?????
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. 后序遍歷（非遞歸實現）
?
?
void BT_PostOrderNoRec(BiTreePtr pNode){
if(!pNode) return;
stack s;
s.push(pNode);?
while (!s.empty())??
{????
BiTreePtr pvNode = s.pop();?
if (pvNode->isPushed)
// 表示其左右子樹都已入棧，訪問該節點??????
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 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++實現二叉樹以及幾種遍歷方式的介紹就算完成了,如果有什么不清楚可以留言給我,如果覺得我寫得不錯的話，請給武林一個關注，謝謝!
