游客

标题:[数据结构]二叉树先序遍历的非递归算法具体实现（面试常考）
正文:
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构总结先根遍历得到的非递归算法思想如下：1）入栈，主要是先头结点入栈，然后visit此结点2）while，循环遍历当前结点，直至左孩子没有结点3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）先看符合此思想的算法：代码如下:
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);
} &nbsp
[<<][[1]][2][3][>>]

查看评论(0)
发表评论



首页