为什么说二叉树遍历用递归的方法不如非递归方法
答案:1 悬赏:20
解决时间 2021-02-20 11:41
- 提问者网友:了了无期
- 2021-02-20 06:49
为什么说二叉树遍历用递归的方法不如非递归方法
最佳答案
- 二级知识专家网友:woshuo
- 2021-02-20 07:47
在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构
总结先根遍历得到的非递归算法思想如下:
1)入栈,主要是先头结点入栈,然后visit此结点
2)while,循环遍历当前结点,直至左孩子没有结点
3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)
先看符合此思想的算法:
[cpp] view plain copy print?
int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
总结先根遍历得到的非递归算法思想如下:
1)入栈,主要是先头结点入栈,然后visit此结点
2)while,循环遍历当前结点,直至左孩子没有结点
3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)
先看符合此思想的算法:
[cpp] view plain copy print?
int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯
• 手机登qq时,显示手机磁盘不足,清理后重新登 |
• 刺客的套装怎么选啊? |