C++实现二叉树以及几种遍历方式
来源：爱站网时间：2018-12-04编辑：网友分享
2018年的最后一个月，谈大的理想抱负已经不够时间来实现，但小计划还是可以的，下面爱站技术小编就给各位带来这篇C++实现二叉树以及几种遍历方式，可能有些小伙伴都接触过，但是这里还是要分享给大家，与君共勉，一起学习。
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
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.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
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.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.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++实现二叉树以及几种遍历方式的介绍就算完成了,如果有什么不清楚可以留言给我,如果觉得我写得不错的话，请给爱站一个关注，谢谢!
上一篇：C++文件的依赖关系
下一篇：使用和总结GDB调试命令
