• 后续遍历非递归算法


    后续遍历非递归算法

    算法思想:在后续遍历中结点要两次入栈,并且两次出栈。

    第一次出栈:只遍历完左子树该结点并不出栈。

    第二次出栈:遍历完右子树,将该结点出栈并访问它。(要保持左右根的顺序,所以要入栈两次,出栈两次)。

    因此为了区分同一个结点是第几次出栈,设置标志位flag;(1表示第一次出栈,2表示第二次出栈)

    struct typu{

            BiTNode *r;

            int flag;//记录第一次出栈还是第二次出栈

    }

    void PostOrder(BiTree T){

    InitStack(S);//初始化栈

    BiTree p=T;//指针指向根结点

    whille(p!=NULL||S.isEmpty){//当p为空并且,S为空时跳出循环

            if(p!=NULL){//指针非空

                    typu.r=p;

                    push(S,typu);//依次入栈

                    typu.flag=1;//标志位设置为1表示第一次入栈

                    p=p->lchild;//遍历左子树

    }

            else{

                    pop(S,typu);//出栈

                    p=typu.r;//p指向当前要处理的结点

                    if(flag==1)//如果此时标志位为1

                            push(S,typu);//入栈

                            typu.flag=2;//标志位设为2

                            p=p->rchild;//遍历右子树

                    else

                            visit(p->data);//访问结点

                            p=NULL;//确保下次循环时继续出栈(回退到上一级)确保直接进入到else循环

    }

    }

    }

  • 相关阅读:
    A. Short Sort
    《算法系列》之位运算
    uniapp cors错误
    【正则表达式系列】常用正则
    GOOGLE/DYNAMICWORLD/V1
    儿童商品证书CPC、CPSIA、ASTM都涵盖哪些产品?
    使用C#和MonoGame开发俄罗斯方块游戏
    prtorch.数据的导入与导出
    Huggingface初上手即ERNIE-gram句子相似性实战
    Kafka KRaft模式探索
  • 原文地址:https://blog.csdn.net/m0_58323186/article/details/128177370