二叉樹算法在小編大學時學數據結構時會學到的一個算法了,這個可以在搜索與排序中提高50%的搜索性能了,下面我們來看一些關于php 二叉樹遍歷算法與例子吧.

二叉樹遍歷,是值從根節點出發,按照某種次序依次訪問二叉樹中的所有節點,使得每個節點被訪問一次且僅被訪問.

前序遍歷二叉樹：如果二叉樹為空則返回，若二叉樹非空，則先遍歷左樹，再遍歷右樹，遍歷順序為ABCDEGF。

中序遍歷二叉樹：如果二叉樹為空則返回，若二叉樹非空，則從根節點開始，中序遍歷根節點的左子樹，然后是訪問根節點，最后中序遍歷右子樹，遍歷順序為CBEGDFA。

后序遍歷二叉樹：如果二叉樹為空則返回，若二叉樹非空，則從左到右先葉子后節點的訪問遍歷訪問左右子樹，最后是訪問根節點。訪問順序為CGEFDBA。

層序遍歷二叉樹：如果二叉樹為空則返回，若二叉樹非空，則從樹的第一層，也就是根節點開始訪問，從上而下逐層遍歷，在同一層中，按照從左到右的順序對節點逐個訪問。訪問順序為ABCDEFG。

現在,我們用PHP代碼,來遍歷二叉樹結構,二叉樹是放一個大數組,每一個節點都有三個字段,data表示這個節點的值,lChild表示這個節點的左邊子節點,rChild表示這個節點的右邊子節點.

二叉樹結構代碼如下:

1. <?php 
2. //二叉樹 
3. $arr = array( 
4.     'data' => 'A', 
5.     'lChild' => array( 
6.         'data' => 'B', 
7.         'lChild' => array( 
8.             'data' => 'C', 
9.             'lChild' => array(), 
10.             'rChild' => array(), 
11.         ), 
12.         'rChild' => array( 
13.             'data' => 'D', 
14.             'lChild' => array( 
15.                 'data' => 'E', 
16.                 'lChild' => array(), 
17.                 'rChild' => array( 
18.                     'data' => 'G', 
19.                     'lChild' => array(), 
20.                     'rChild' => array(), 
21.                 ), 
22.             ), 
23.             'rChild' => array( 
24.                 'data' => 'F', 
25.                 'lChild' => array(), 
26.                 'rChild' => array(), 
27.             ), 
28.         ), 
29.     ), 
30.     'rChild' => array(), 
31. ); 
32. ?> 

遍歷算法一:前序遍歷二叉樹

1. <?php 
2. //前序遍歷二叉樹算法 
3. echo '前序遍歷二叉樹算法：'; 
4. PreOrderTraverse($arr); 
5. echo '<Br>'; 
6. function PreOrderTraverse($node){ 
7.     if(emptyempty($node)){ 
8.         return; 
9.     } 
10.     //輸出值 
11.     print_r($node['data']); 
12.     //左節點 
13.     PreOrderTraverse($node['lChild']); 
14.     //右節點 
15.     PreOrderTraverse($node['rChild']); 
16. } 
17. ?> 

遍歷算法二:中序遍歷二叉樹

1. <?php 
2. //中序遍歷二叉樹算法 
3. echo '中序遍歷二叉樹算法：'; 
4. inOrderTraverse($arr); 
5. echo '<Br>'; 
6. function inOrderTraverse($node){ 
7.     if(emptyempty($node)){ 
8.         return; 
9.     } 
10.     //左節點 
11.     inOrderTraverse($node['lChild']); 
12.     //輸出值 
13.     print_r($node['data']); 
14.     //右節點 
15.     inOrderTraverse($node['rChild']); 
16. } 
17. ?> 

遍歷算法三:后序遍歷二叉樹

1. <?php 
2. //后序遍歷二叉樹算法 
3. echo '后序遍歷二叉樹算法：'; 
4. postOrderTraverse($arr); 
5. echo '<Br>'; 
6. function postOrderTraverse($node){ 
7.     if(emptyempty($node)){ 
8.         return; 
9.     } 
10.     //左節點 
11.     postOrderTraverse($node['lChild']); 
12.     //右節點 
13.     postOrderTraverse($node['rChild']); 
14.     //輸出值 
15.     print_r($node['data']); 
16. } 
17. ?> 

例子:

1. <?php 
2. /** 
3.  *二叉樹的創建及基本操作 
4.  * 
5.  *1.構造方法,初始化建立二叉樹 
6.  *2.按先序遍歷方式建立二叉樹 
7.  *3.按先序遍歷二叉樹 
8.  *4.先序遍歷的非遞歸算法 
9.  *5.中序遍歷二叉樹 
10.  *6.中序遍歷的非遞歸算法 
11.  *7.后序遍歷二叉樹 
12.  *8.后序遍歷非遞歸算法 
13.  *9.層次遍歷二叉樹 
14.  *10.求二叉樹葉子結點的個數 
15.  *11.求二叉樹的深度 
16.  *12.判斷二叉樹是否為空樹 
17.  *13.置空二叉樹 
18.  * 
19.  *@author xudianyang<> 
20.  *@version $Id:BinaryTree.class.php,v 1.0 2011/02/13 13:33:00 uw Exp 
21.  *@copyright &copy;2011,xudianyang 
22.  */ 
23. header('content-type:text/html;charset=gb2312'); 
24. //在PHP數據結構之五 棧的PHP的實現和棧的基本操作 可以找到該類 
25. include_once("./StackLinked.class.php"); 
26. //在 PHP數據結構之七 隊列的鏈式存儲和隊列的基本操作 可以找到該類 
27. include_once('./QueueLinked.class.php'); 
28. class BTNode{ 
29.  //左子樹“指針” 
30.  public $mLchild=null; 
31.  //右子樹“指針” 
32.  public $mRchild=null; 
33.  //結點數據域 
34.  public $mData=null; //左標志域，為1時表示mLchild“指向”結點左孩子，為2表示“指向”結點直接前驅 
35.  public $intLeftTag=null; 
36.  //右標志域，為1時表示mRchild“指向”結點右孩子，為2表示“指向”結點直接后繼 
37.  public $intRightTag=null; 
38. } 
39. class BinaryTree{ 
40.  //根結點 
41.  public $mRoot; 
42.  //根據先序遍歷錄入的二叉樹數據 
43.  public $mPBTdata=null; 
44.  /** 
45.   *構造方法,初始化建立二叉樹 
46.   * 
47.   *@param array $btdata 根據先序遍歷錄入的二叉樹的數據，一維數組，每一個元素代表二叉樹一個結點值,擴充結點值為''[長度為0的字符串] 
48.   *@return void 
49.   */ 
50.  public function __construct($btdata=array()){ 
51.   $this->mPBTdata=$btdata; 
52.   $this->mRoot=null; 
53.   $this->getPreorderTraversalCreate($this->mRoot); 
54.  } 
55.  /** 
56.   *按先序遍歷方式建立二叉樹 
57.   * 
58.   *@param BTNode 二叉樹結點，按引用方式傳遞 
59.   *@return void 
60.   */ 
61.  public function getPreorderTraversalCreate(&$btnode){ 
62.   $elem=array_shift($this->mPBTdata); 
63.   if($elem === ''){ 
64.    $btnode=null; 
65.   }else if($elem === null){ 
66.    return; 
67.   }else{ 
68.    $btnode=new BTNode(); 
69.    $btnode->mData=$elem; 
70.    $this->getPreorderTraversalCreate($btnode->mLchild); 
71.    $this->getPreorderTraversalCreate($btnode->mRchild); 
72.   } 
73.  } 
74.  /** 
75.   *判斷二叉樹是否為空 
76.   * 
77.   *@return boolean 如果二叉樹不空返回true,否則返回false 
78.   **/ 
79.  public function getIsEmpty(){ 
80.   if($this->mRoot instanceof BTNode){ 
81.    return false; 
82.   }else{ 
83.    return true; 
84.   } 
85.  } 
86.  /** 
87.   *將二叉樹置空 
88.   * 
89.   *@return void 
90.   */ 
91.  public function setBinaryTreeNull(){ 
92.   $this->mRoot=null; 
93.  } 
94.  /** 
95.   *按先序遍歷二叉樹 
96.   * 
97.   *@param BTNode $rootnode 遍歷過程中的根結點 
98.   *@param array $btarr 接收值的數組變量，按引用方式傳遞 
99.   *@return void 
100.   */ 
101.  public function getPreorderTraversal($rootnode,&$btarr){ 
102.   if($rootnode!=null){ 
103.    $btarr[]=$rootnode->mData; 
104.    $this->getPreorderTraversal($rootnode->mLchild,$btarr); 
105.    $this->getPreorderTraversal($rootnode->mRchild,$btarr); 
106.   } 
107.  } 
108.  /** 
109.   *先序遍歷的非遞歸算法 
110.   * 
111.   *@param BTNode $objRootNode 二叉樹根節點 
112.   *@param array $arrBTdata 接收值的數組變量，按引用方式傳遞 
113.   *@return void 
114.   */ 
115.  public function getPreorderTraversalNoRecursion($objRootNode,&$arrBTdata){ 
116.   if($objRootNode instanceof BTNode){ 
117.    $objNode=$objRootNode; 
118.    $objStack=new StackLinked(); 
119.    do{ 
120.     $arrBTdata[]=$objNode->mData; 
121.     $objRNode=$objNode->mRchild; 
122.     if($objRNode !=null){ 
123.      $objStack->getPushStack($objRNode); 
124.     } 
125.     $objNode=$objNode->mLchild; 
126.     if($objNode==null){ 
127.      $objStack->getPopStack($objNode); 
128.     } 
129.    }while($objNode!=null); 
130.   }else{ 
131.    $arrBTdata=array(); 
132.   } 
133.  } 
134.  /** 
135.   *中序遍歷二叉樹 
136.   * 
137.   *@param BTNode $objRootNode 過程中的根節點 
138.   *@param array $arrBTdata 接收值的數組變量,按引用方式傳遞 
139.   *@return void 
140.   */ 
141.  public function getInorderTraversal($objRootNode,&$arrBTdata){ 
142.   if($objRootNode!=null){ 
143.    $this->getInorderTraversal($objRootNode->mLchild,$arrBTdata); 
144.    $arrBTdata[]=$objRootNode->mData; 
145.    $this->getInorderTraversal($objRootNode->mRchild,$arrBTdata); 
146.   } 
147.  } 
148.  /** 
149.   *中序遍歷的非遞歸算法 
150.   * 
151.   *@param BTNode $objRootNode 二叉樹根結點 
152.   *@param array $arrBTdata 接收值的數組變量，按引用方式傳遞 
153.   *@return void 
154.   */ 
155.  public function getInorderTraversalNoRecursion($objRootNode,&$arrBTdata){ 
156.   if($objRootNode instanceof BTNode){ 
157.    $objNode=$objRootNode; 
158.    $objStack=new StackLinked(); 
159.    //中序遍歷左子樹及訪問根節點 
160.    do{ 
161.     while($objNode!=null){ 
162.      $objStack->getPushStack($objNode); 
163.      $objNode=$objNode->mLchild; 
164.     } 
165.     $objStack->getPopStack($objNode); 
166.     $arrBTdata[]=$objNode->mData; 
167.     $objNode=$objNode->mRchild; 
168.    }while(!$objStack->getIsEmpty()); 
169.    //中序遍歷右子樹 
170.    do{ 
171.     while($objNode!=null){ 
172.      $objStack->getPushStack($objNode); 
173.      $objNode=$objNode->mLchild; 
174.     } 
175.     $objStack->getPopStack($objNode); 
176.     $arrBTdata[]=$objNode->mData; 
177.     $objNode=$objNode->mRchild; 
178.    }while(!$objStack->getIsEmpty()); 
179.   }else{ 
180.    $arrBTdata=array(); 
181.   } 
182.  } 
183.  /** 
184.   *后序遍歷二叉樹 
185.   * 
186.   *@param BTNode $objRootNode  遍歷過程中的根結點 
187.   *@param array $arrBTdata 接收值的數組變量，引用方式傳遞 
188.   *@return void 
189.   */ 
190.  public function getPostorderTraversal($objRootNode,&$arrBTdata){ 
191.   if($objRootNode!=null){ 
192.    $this->getPostorderTraversal($objRootNode->mLchild,$arrBTdata); 
193.    $this->getPostorderTraversal($objRootNode->mRchild,$arrBTdata); 
194.    $arrBTdata[]=$objRootNode->mData; 
195.   } 
196.  } 
197.  /** 
198.   *后序遍歷非遞歸算法 
199.   * 
200.  BTNode $objRootNode 二叉樹根節點 
201.  array $arrBTdata 接收值的數組變量，按引用方式傳遞 
202.  void 
203.   */ 
204.  public function getPostorderTraversalNoRecursion($objRootNode,&$arrBTdata){ 
205.   if($objRootNode instanceof BTNode){ 
206.    $objNode=$objRootNode; 
207.    $objStack=new StackLinked(); 
208.    $objTagStack=new StackLinked(); 
209.    $tag=1; 
210.    do{ 
211.     while($objNode!=null){ 
212.      $objStack->getPushStack($objNode); 
213.      $objTagStack->getPushStack(1); 
214.      $objNode=$objNode->mLchild; 
215.     } 
216.     $objTagStack->getPopStack($tag); 
217.     $objTagStack->getPushStack($tag); 
218.     if($tag == 1){ 
219.      $objStack->getPopStack($objNode); 
220.      $objStack->getPushStack($objNode); 
221.      $objNode=$objNode->mRchild; 
222.      $objTagStack->getPopStack($tag); 
223.      $objTagStack->getPushStack(2); 
224.     }else{ 
225.      $objStack->getPopStack($objNode); 
226.      $arrBTdata[]=$objNode->mData; 
227.      $objTagStack->getPopStack($tag); 
228.      $objNode=null; 
229.     } 
230.    }while(!$objStack->getIsEmpty()); 
231.   }else{ 
232.    $arrBTdata=array(); 
233.   } 
234.  } 
235.  /** 
236.   *層次遍歷二叉樹 
237.   * 
238.   *@param BTNode $objRootNode二叉樹根節點 
239.   *@param array $arrBTdata 接收值的數組變量，按引用方式傳遞 
240.   *@return void 
241.   */ 
242.  public function getLevelorderTraversal($objRootNode,&$arrBTdata){ 
243.   if($objRootNode instanceof BTNode){ 
244.    $objNode=$objRootNode; 
245.    $objQueue=new QueueLinked(); 
246.    $objQueue->getInsertElem($objNode); 
247.    while(!$objQueue->getIsEmpty()){ 
248.     $objQueue->getDeleteElem($objNode); 
249.     $arrBTdata[]=$objNode->mData; 
250.     if($objNode->mLchild != null){ 
251.      $objQueue->getInsertElem($objNode->mLchild); 
252.     } 
253.     if($objNode->mRchild != null){ 
254.      $objQueue->getInsertElem($objNode->mRchild); 
255.     } 
256.    } 
257.   }else{ 
258.    $arrBTdata=array(); 
259.   } 
260.  } 
261.  /** 
262.   *求二叉樹葉子結點的個數 
263.   * 
264.   *@param BTNode $objRootNode 二叉樹根節點 
265.   *@return int 參數傳遞錯誤返回-1 
266.   **/ 
267.  public function getLeafNodeCount($objRootNode){ 
268.   if($objRootNode instanceof BTNode){ 
269.    $intLeafNodeCount=0; 
270.    $objNode=$objRootNode; 
271.    $objStack=new StackLinked(); 
272.    do{ 
273.     if($objNode->mLchild == null && $objNode->mRchild == null){ 
274.      $intLeafNodeCount++; 
275.     } 
276.     $objRNode=$objNode->mRchild; 
277.     if($objRNode != null){ 
278.      $objStack->getPushStack($objRNode); 
279.     } 
280.     $objNode=$objNode->mLchild; 
281.     if($objNode == null){ 
282.      $objStack->getPopStack($objNode); 
283.     } 
284.    }while($objNode != null); 
285.    return $intLeafNodeCount; 
286.   }else{ 
287.    return -1; 
288.   } 
289.  } 
290.  /** 
291.   *求二叉樹的深度 
292.   * 
293.   *@param BTNode $objRootNode 二叉樹根節點 
294.   *@return int 參數傳遞錯誤返回-1 
295.   */ 
296.  public function getBinaryTreeDepth($objRootNode){ 
297.   if($objRootNode instanceof BTNode){ 
298.    $objNode=$objRootNode; 
299.    $objQueue=new QueueLinked(); 
300.    $intBinaryTreeDepth=0; 
301.    $objQueue->getInsertElem($objNode); 
302.    $objLevel=$objNode; 
303.    while(!$objQueue->getIsEmpty()){ 
304.     $objQueue->getDeleteElem($objNode); 
305.     if($objNode->mLchild != null){ 
306.      $objQueue->getInsertElem($objNode->mLchild); 
307.     } 
308.     if($objNode->mRchild != null){ 
309.      $objQueue->getInsertElem($objNode->mRchild); 
310.     } 
311.     if($objLevel == $objNode){ 
312.      $intBinaryTreeDepth++; 
313.      $objLevel=@$objQueue->mRear->mElem; 
314.     } //開源軟件:Vevb.com 
315.    } 
316.    return $intBinaryTreeDepth; 
317.   }else{ 
318.    return -1; 
319.   } 
320.  } 
321. } 
322. echo "<pre>"; 
323. $bt=new BinaryTree(array('A','B','D','','','E','','G','','','C','F','','','')); 
324. echo "二叉樹結構：＼r＼n"; 
325. var_dump($bt); 
326. $btarr=array(); 
327. echo "先序遞歸遍歷二叉樹：＼r＼n"; 
328. $bt->getPreorderTraversal($bt->mRoot,$btarr); 
329. var_dump($btarr); 
330. echo "先序非遞歸遍歷二叉樹：＼r＼n"; 
331. $arrBTdata=array(); 
332. $bt->getPreorderTraversalNoRecursion($bt->mRoot,$arrBTdata); 
333. var_dump($arrBTdata); 
334. echo "中序遞歸遍歷二叉樹：＼r＼n"; 
335. $arrBTdata=array(); 
336. $bt->getInorderTraversal($bt->mRoot,$arrBTdata); 
337. var_dump($arrBTdata); 
338. echo "中序非遞歸遍歷二叉樹：＼r＼n"; 
339. $arrBTdata=array(); 
340. $bt->getInorderTraversalNoRecursion($bt->mRoot,$arrBTdata); 
341. var_dump($arrBTdata); 
342. echo "后序遞歸遍歷二叉樹：＼r＼n"; 
343. $arrBTdata=array(); 
344. $bt->getPostorderTraversal($bt->mRoot,$arrBTdata); 
345. var_dump($arrBTdata); 
346. echo "后序非遞歸遍歷二叉樹:＼r＼n"; 
347. $arrBTdata=array(); 
348. $bt->getPostorderTraversalNoRecursion($bt->mRoot,$arrBTdata); 
349. var_dump($arrBTdata); 
350. echo "按層次遍歷二叉樹：＼r＼n"; 
351. $arrBTdata=array(); 
352. $bt->getLevelorderTraversal($bt->mRoot,$arrBTdata); 
353. var_dump($arrBTdata); 
354. echo "葉子結點的個數為：".$bt->getLeafNodeCount($bt->mRoot); 
355. echo "＼r＼n"; 
356. echo "二叉樹深度為:".$bt->getBinaryTreeDepth($bt->mRoot); 
357. echo "＼r＼n"; 
358. echo "判斷二叉樹是否為空："; 
359. var_dump($bt->getIsEmpty()); 
360. echo "將二叉樹置空后："; 
361. $bt->setBinaryTreeNull(); 
362. var_dump($bt); 
363. echo "</pre>"; 
364. ?>