正因为生来什么都没有,因此我们能拥有一切。(o゚▽゚)o

  • 微信公众号
  • 二叉树的三种遍历(非递归)

    jingyile·2019-11-23·96 次阅读

    由于下大雨在宿舍偷懒,剩不到一个月考研了很焦虑怎么办!QAQ

    顺便在这里很粗略的写写二叉树的三种遍历算法(非递归) ,不知道会不会考到呢、、o(´^`)o

    watermark,type ZmFuZ3poZW5naGVpdGk,shadow 10,text aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pZTDExNTkxMzEyMzc=,size 16,color FFFFFF,t 70 - 二叉树的三种遍历(非递归)

      图1:示例二叉树

    先序遍历:12354

    中序遍历:32514

    后序遍历:35241

     

     

    -----------------------------------先序遍历---------------------------------------

    先直接上代码:

    算法步骤详解:

    初始栈均为空。

    ①:根结点1入栈。

    ②:栈顶元素(1)出栈,并访问。将其左右孩子入栈,右孩子(4)先入栈,左孩子(2)后入栈.

    ③:栈顶元素(2)出栈,并访问。将其左右孩子入栈,右孩子(5)先入栈,左孩子(3)后入栈.

    ④:栈顶元素(3)出栈,并访问。无孩子结点。

    ⑤:栈顶元素(5)出栈,并访问。无孩子结点。

    ⑥:栈顶元素(4)出栈,并访问。无孩子结点。

    此时依次访问结点序列为12354,即先序遍历序列。

    20191123204423781 - 二叉树的三种遍历(非递归)

    图2:先序遍历结点进出栈过程

     

     

     

    -----------------------------------中序遍历---------------------------------------

    算法步骤详解:

    初始栈均为空。

    ①:根结点1入栈。1左孩子存在。

    ②:结点2入栈。2左孩子存在。

    ③:结点3入栈。3左孩子不存在。

    ④:栈顶元素(3)出栈,输出栈顶元素,3右孩子不存在。

    ⑤:栈顶元素(2)出栈,输出栈顶元素,2右孩子存在(5),入栈。5左孩子不存在。

    ⑥:栈顶元素(5)出栈,输出栈顶元素,5右孩子不存在。

    ⑦:栈顶元素(1)出栈,1右孩子存在(4),入栈。4左孩子不存在。

    栈顶元素(4)出栈,输出栈顶元素,此时栈空,进入终态。

    此时依次输出结点序列为32514,即中序遍历序列。

    20191123205118556 - 二叉树的三种遍历(非递归)

    图3:中序遍历结点进出栈过程

     

     

     

     

    -----------------------------------后序遍历---------------------------------------

    算法步骤详解:

    设立两个栈,记为ST1和ST2。初始两个栈均为空。

    ①:根结点1入栈ST1。

    ②:ST1栈顶元素(1)出栈,并将其入栈ST2。若该元素左右孩子存在,依次入栈ST1。(左孩子为2,右孩子为4,依次入栈)

    ③:ST1栈顶元素(4)出栈,并将其入栈ST2。该元素不存在孩子结点。

    ④:ST1栈顶元素(2)出栈,并将其入栈ST2。若该元素左右孩子存在,依次入栈ST1。(左孩子为3,右孩子为5,依次入栈)

    ⑤:ST1栈顶元素(5)出栈,并将其入栈ST2。该元素不存在孩子结点。

    ⑥:ST1栈顶元素(3)出栈,并将其入栈ST2。该元素不存在孩子结点。

    此时ST1栈为空,ST2栈自顶向下依次为:35241,即后序遍历序列。

    20191123203024806 - 二叉树的三种遍历(非递归)

    图4:后序遍历结点进出栈ST1过程

    20191123203137575 - 二叉树的三种遍历(非递归)

    图5:后序遍历结点进出栈ST2过程

     


    正因为生来什么都没有,因此我们能拥有一切。(o゚▽゚)o

    
    
    查看评论

    Post a new comment

    Post a new comment
    欢迎回来 , [ 修改 ]




    加载中……