http://blog.csdn.net/baidu_30000217/article/details/52953127

前言：

深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、后序遍歷。具體說明如下：

• 前序遍歷：根節點->左子樹->右子樹

• 中序遍歷：左子樹->根節點->右子樹

• 后序遍歷：左子樹->右子樹->根節點

廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

例如對于一下這棵樹：

深度優先遍歷：

• 前序遍歷：10 8 7 9 12 11 13

• 中序遍歷：7 8 9 10 11 12 13

• 后序遍歷：7 9 8 11 13 12 10

廣度優先遍歷：

• 層次遍歷：10 8 12 7 9 11 13

二叉樹的深度優先遍歷的非遞歸的通用做法是采用棧，廣度優先遍歷的非遞歸的通用做法是采用隊列。

深度優先遍歷：

1、前序遍歷：

????/** ?????*?前序遍歷(遞歸方法) ?????*/ ????private?function?pre_order1($root) ????{????????if?(!is_null($root))?{????????????//這里用到常量__FUNCTION__，獲取當前函數名，好處是假如修改函數名的時候，里面的實現不用修改 ????????????$function?=?__FUNCTION__; ????????????echo?$root->key?.?"?";????????????$this->$function($root->left);????????????$this->$function($root->right); ????????} ????}????/** ?????*?前序遍歷(非遞歸方法) ?????*?因為當遍歷過根節點之后還要回來，所以必須將其存起來?？紤]到后進先出的特點，選用棧存儲。 ?????*/ ????private?function?pre_order2($root) ????{????????//????????$stack?=?new?splstack(); ????????//????????$stack->push($root); ????????//????????while(!$stack->isEmpty()){ ????????//????????????$node?=?$stack->pop(); ????????//????????????echo?$node->key.'?'; ????????//????????????if(!is_null($node->right)){ ????????//????????????????$stack->push($node->right); ????????//????????????} ????????//????????????if(!is_null($node->left)){ ????????//????????????????$stack->push($node->left); ????????//????????????} ????????//????????} ????????if?(is_null($root))?{????????????return; ????????}????????$stack?=?new?splstack();????????$node?=?$root;????????while?(!is_null($node)?||?!$stack->isEmpty())?{????????????while?(!is_null($node))?{????????????????//只要結點不為空就應該入棧保存，與其左右結點無關 ????????????????$stack->push($node); ????????????????echo?$node->key?.?'?';????????????????$node?=?$node->left; ????????????}????????????$node?=?$stack->pop();????????????$node?=?$node->right; ????????} ????}????//前序遍歷 ????public?function?PreOrder() ????{????????//?所在對象中的tree屬性保存了一個樹的引用 ????????//?????$this->pre_order1($this->tree->root); ????????$this->pre_order2($this->tree->root); ????}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960

說明：1、我將所有的遍歷方法都封裝在一個類 traverse 里面了。2、pre_order2方法中，在使用棧的過程中，我使用的是PHP標準庫SPL提供的splstack，如果你們習慣使用數組的話，可以使用 array_push() 和array_pop() 模擬實現。

2、中序遍歷：

????/** ?????*?中序遍歷(遞歸方法) ?????*/ ????private?function?mid_order1($root) ????{????????if?(!is_null($root))?{????????????$function?=?__FUNCTION__;????????????$this->$function($root->left); ????????????echo?$root->key?.?"?";????????????$this->$function($root->right); ????????} ????}????/** ?????*?中序遍歷(非遞歸方法) ?????*?因為當遍歷過根節點之后還要回來，所以必須將其存起來?？紤]到后進先出的特點，選用棧存儲。 ?????*/ ????private?function?mid_order2($root) ????{????????if?(is_null($root))?{????????????return; ????????}????????$stack?=?new?splstack();????????$node?=?$root;????????while?(!is_null($node)?||?!$stack->isEmpty())?{????????????while?(!is_null($node))?{????????????????$stack->push($node);????????????????$node?=?$node->left; ????????????}????????????$node?=?$stack->pop(); ????????????echo?$node->key?.?'?';????????????$node?=?$node->right; ????????} ????}????//中序遍歷 ????public?function?MidOrder() ????{????????//????????$this->mid_order1($this->tree->root); ????????$this->mid_order2($this->tree->root); ????}123456789101112131415161718192021222324252627282930313233343536373839404142123456789101112131415161718192021222324252627282930313233343536373839404142

3、后序遍歷：

????/** ?????*?后序遍歷(遞歸方法) ?????*/ ????private?function?post_order1($root) ????{????????if?(!is_null($root))?{????????????$function?=?__FUNCTION__;????????????$this->$function($root->left);????????????$this->$function($root->right); ????????????echo?$root->key?.?"?"; ????????} ????}????/** ?????*?后序遍歷(非遞歸方法) ?????*?因為當遍歷過根節點之后還要回來，所以必須將其存起來?？紤]到后進先出的特點，選用棧存儲。 ?????*?由于在訪問了左子節點后怎么跳到右子節點是難點，這里使用一個標識lastVisited來標識上一次訪問的結點 ?????*/ ????private?function?post_order2($root) ????{????????if?(is_null($root))?{????????????return; ????????}????????$node?=?$root;????????$stack?=?new?splstack();????????//保存上一次訪問的結點引用 ????????$lastVisited?=?NULL;????????$stack->push($node);????????while(!$stack->isEmpty()){????????????$node?=?$stack->top();//獲取棧頂元素但不彈出 ????????????if(($node->left?==?NULL?&&?$node->right?==?NULL)?||?($node->right?==?NULL?&&?$lastVisited?==?$node->left)?||?($lastVisited?==?$node->right)){ ????????????????echo?$node->key.'?';????????????????$lastVisited?=?$node;????????????????$stack->pop(); ????????????}else{????????????????if($node->right){????????????????????$stack->push($node->right); ????????????????}????????????????if($node->left){????????????????????$stack->push($node->left); ????????????????} ????????????} ????????} ????}????//后序遍歷 ????public?function?PostOrder() ????{????????//????????$this->post_order1($this->tree->root); ????????$this->post_order2($this->tree->root); ????}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515212345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152

廣度優先遍歷：

1、層次遍歷：

????/** ?????*?層次遍歷(遞歸方法) ?????*?由于是按層逐層遍歷，因此傳遞樹的層數 ?????*/ ????private?function?level_order1($root,$level){????????if($root?==?NULL?||?$level?<?1){????????????return; ????????}????????if($level?==?1){ ????????????echo?$root->key.'?';????????????return; ????????}????????if(!is_null($root->left)){????????????$this->level_order1($root->left,$level?-?1); ????????}????????if(!is_null($root->right)){????????????$this->level_order1($root->right,$level?-?1); ????????} ????}????/** ?????*?層次遍歷(非遞歸方法) ?????*?每一層從左向右輸出 元素需要儲存有先進先出的特性，所以選用隊列存儲。 ?????*/ ????private?function?level_order2($root){????????if(is_null($root)){????????????return; ????????}????????$node?=?$root;????????//利用隊列實現//????????$queue?=?array();//????????array_push($queue,$node);????????while(!is_null($node?=?array_shift($queue))){//????????????echo?$node->key.'?';//????????????if(!is_null($node->left)){//????????????????array_push($queue,$node->left);//????????????}//????????????if(!is_null($node->right)){//????????????????array_push($queue,$node->right);//????????????}//????????} ????????$queue?=?new?splqueue();????????$queue->enqueue($node);????????while(!$queue->isEmpty()){????????????$node?=?$queue->dequeue(); ????????????echo?$node->key.'?';????????????if?(!is_null($node->left))?{????????????????$queue->enqueue($node->left); ????????????}????????????if?(!is_null($node->right))?{????????????????$queue->enqueue($node->right); ????????????} ????????} ????}????//層次遍歷 ????public?function?LevelOrder(){//????????$level?=?$this->getdepth($this->tree->root);//????????for($i?=?1;$i?<=?$level;$i?++){//????????????$this->level_order1($this->tree->root,$i);//????????} ????????$this->level_order2($this->tree->root); ????}????//獲取樹的層數 ????private?function?getdepth($root){????????if(is_null($root)){????????????return?0; ????????}????????$left?=?getdepth($root?->?left);????????$right?=?getdepth($root?->?right);????????$depth?=?($left?>?$right???$left?:?$right)?+?1;????????return?$depth; ????}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787912345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879

說明：level_order2方法中，在使用隊列的過程中，我使用的是php標準庫SPL提供的splqueue，如果你們習慣使用數組的話，可以使用 array_push() 和array_shift() 模擬實現。

使用：

現在我們來看看客戶端代碼：

class?Client{ ????public?static?function?Main() ????{ ????????try?{????????????//實現文件的自動加載 ????????????function?autoload($class) ????????????{ ????????????????include?strtolower($class)?.?'.php'; ????????????} ????????????spl_autoload_register('autoload');????????????$arr?=?array(10,?8,?12,?7,?9,?11,?13);????????????$tree?=?new?Bst();//????????????$tree?=?new?Avl();//????????????$tree?=?new?Rbt(); ????????????$tree->init($arr);????????????$traverse?=?new?traverse($tree);????????????$traverse->PreOrder();//????????????$traverse->MidOrder();//????????????$traverse->PostOrder();//????????????$traverse->LevelOrder(); ????????}?catch?(Exception?$e)?{????????????echo?$e->getMessage(); ????????} ????} } CLient::Main();12345678910111213141516171819202122232425262728293031321234567891011121314151617181920212223242526272829303132

補充：?
1. 在客戶端中所使用的三個類 Bst、Avl、Rbt 大家可以參考我的其他三篇博客：《PHP二叉樹（一）：二叉搜索樹》、《 PHP二叉樹（二）：平衡二叉樹（AVL）》、《PHP二叉樹（三）：紅黑樹》?
2. 為什么我推薦大家使用SPL標準庫中提供的splstack和splqueue呢？這是我在某一篇文章中看到的：雖然我們可以使用傳統的變量類型來描述數據結構，例如用數組來描述堆棧（Strack）– 然后使用對應的方式 pop 和 push（array_pop()、array_push()），但你得時刻小心，因為畢竟它們不是專門用于描述數據結構的 – 一次誤操作就有可能破壞該堆棧。而 SPL 的 SplStack 對象則嚴格以堆棧的形式描述數據，并提供對應的方法。同時，這樣的代碼應該也能理解它在操作堆棧而非某個數組，從而能讓你的同伴更好的理解相應的代碼，并且它更快。原文地址：PHP SPL，遺落的寶石?
3. 本篇博客有參考：?《數據結構（六）——二叉樹 前序、中序、后序、層次遍歷及非遞歸實現 查找、統計個數、比較、求深度的遞歸實現》、《二叉樹的深度優先遍歷和廣度優先遍歷》

本文轉自 ?陳小龍哈 ? 51CTO博客，原文鏈接:http://blog.51cto.com/chenxiaolong/1959144

總結

以上是生活随笔為你收集整理的PHP实现二叉树的深度优先遍历（前序、中序、后序）和广度优先遍历（层次） 转载陈小龙哈2017...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。