二叉树算法在小编大学时学数据结构时会学到的一个算法了,这个可以在搜索与排序中提高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.     } //开源软件:phpfensi.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. ?>

Tags: php二叉树 php遍历算法

分享到：