• 全美商學院
    新聞
    新聞

    成都小程序設計使用PHP基于非遞歸算法實現先序、中序及后序遍歷二叉樹操作示例

    2021
    07/10
    18:03
    全美網絡官網
    分享

    成都小程序設計實例講述了PHP基于非遞歸算法實現先序、中序及后序遍歷二叉樹操作。分享給大家供大家參考,具體如下:

    網站開發

    概述:

    二叉樹遍歷原理如下:

    針對上圖所示二叉樹遍歷:

    1、前序遍歷:先遍歷根結點,然后遍歷左子樹,最后遍歷右子樹。

    ABDHECFG

    2、中序遍歷:先遍歷左子樹,然后遍歷根結點,最后遍歷右子樹。

    HDBEAFCG

    3、后序遍歷:先遍歷左子樹,然后遍歷右子樹,最后遍歷根節點。

    HDEBFGCA

    實現方法:

    先序遍歷:利用棧先進后出的特性,先訪問根節點,再把右子樹壓入,再壓入左子樹。這樣取出的時候是先取出左子樹,最后取出右子樹。

    functionpreorder($root){ $stack=array(); array_push($stack,$root); while(!empty($stack)){ $center_node=array_pop($stack); echo$center_node->value;//根節點 if($center_node->right!=null) array_push($stack,$center_node->right);//壓入右子樹 if($center_node->left!=null) array_push($stack,$center_node->left);//壓入左子樹 } }

    中序:需要從下向上遍歷,所以先把左子樹壓入棧,然后逐個訪問根節點和右子樹。

    functioninorder($root){ $stack=array(); $center_node=$root; while(!empty($stack)||$center_node!=null){ while($center_node!=null){ array_push($stack,$center_node); $center_node=$center_node->left; } $center_node=array_pop($stack); echo$center_node->value; $center_node=$center_node->right; } }

    后序:先把根節點存起來,然后依次儲存左子樹和右子樹。然后輸出。

    functiontailorder($root){ $stack=array(); $outstack=array(); array_push($$stack,$root); while($empty($stack)){ $center_node=array_pop($stack); array_push($outstack,$center_node); if($center_node->right!=null) array_push($stack,$center_node->right); if($center_node->left!=null) array_push($stack,$center_node->left); } while($empty($outstack)){ $center_node=array_pop($outstack); echo$center_node->value; } }

    更多關于PHP相關內容感興趣的讀者可查看成都小程序設計專題:《PHP數據結構與算法教程》、《php程序設計算法總結》、《php字符串(string)用法總結》、《PHP數組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結》及《PHP數學運算技巧總結》

    希望本文所述對大家PHP程序設計有所幫助。

    聯系我們
    歡迎來到全美,免費
    獲取專業小程序設計方案
    電話咨詢:

    15281067168

    您還可以預約資深顧問
    隱私信息保護中,請放心填寫

    在線客服

    電話咨詢

    微信咨詢

    微信號復制成功
    15281067168 (蘇女士)
    打開微信,粘貼添加好友,免費詢價吧
  • 成人国产网站v片免费观看