生活已是百般艰难,为何不努力一点。下面图老师就给大家分享c++二叉树的几种遍历算法,希望可以让热爱学习的朋友们体会到设计的小小的乐趣。
【 tulaoshi.com - 编程语言 】
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){
stackBiTreePtr 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)
{
stackBiTreePtr s;
s.push(pNode);
while (!s.empty())
{
BiTreePtr pvNode = s.pop();
visit(pvNode);
s.push(pvNode-right);
s.push(pvNode-left);
}
}}
//
不用栈实现 每个节点含父节点指针和isVisited状态变量 且该二叉树含一个头节点
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){
stackBiTreePtr s;
while (!pNode || !s.empty())
{
if (!pNode)
{
s.push(pNode);
pNode = pNode-left;
}
else
{
pNode = s.pop();
visit(pNode);
pNode = pNode-right;
}
}}
// 不用栈实现 每个节点含父节点指针和isVisited的状态变量 且该二叉树含一个头节点
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;
stackBiTreePtr 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;
queueBiTreePtr 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);
}}
来源:http://www.tulaoshi.com/n/20160219/1596406.html
看过《c++二叉树的几种遍历算法》的人还看了以下文章 更多>>