本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：

1. <?php
3.   require 'biTree.php';
5.   $str = 'ko#be8#tr####acy#####';
7.   $tree = new BiTree($str);
9.   $tree->createThreadTree();
11.   echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树
13.   echo $tree->threadListReserv();从最后一个结点开始反向遍历
15. ?>

biTree.php：

1. <?
3.   /**
5.    * PHP实现二叉树
7.    *
9.    * @author
11.    * @since 2011/10/25 10:32
13.    */
15.   //结点类
17.   class Node{
19.     private $data = NULL;
21.     private $left = NULL;
23.     private $right = NULL;
25.     private $lTag = 0;
27.     private $rTag = 0;
29.     public function Node($data = false){
31.       $this->data = $data;
33.     }
35.     //我不喜欢使用魔术方法
37.     public function getData(){
39.       return $this->data;
41.     }
43.     public function setData($data){
45.       $this->data = $data;
47.     }
49.     public function getLeft(){
51.       return $this->left;
53.     }
55.     public function setLeft($left){
57.       $this->left = $left;
59.     }
61.     public function getRight(){
63.       return $this->right;
65.     }
67.     public function setRight($right){
69.       $this->right = $right;
71.     }
73.     public function getLTag(){
75.       return $this->lTag;
77.     }
79.     public function setLTag($tag){
81.       $this->lTag = $tag;
83.     }
85.     public function getRTag(){
87.       return $this->rTag;
89.     }
91.     public function setRTag($tag){
93.       $this->rTag = $tag;
95.     }
97.   }
99.   //线索二叉树类
101.   class BiTree{
103.     private $datas = NULL;//要导入的字符串;
105.     private $root = NULL; //根结点
107.     private $leafCount = 0;//叶子结点个数
109.     private $headNode = NULL; //线索二叉树的头结点
111.     private $preNode = NULL;//遍历线索化二叉树时保存前一个遍历的结点
113.     public function BiTree($datas){
115.       is_array($datas) || $datas = str_split($datas);
117.       $this->datas = $datas;
119.       $this->backupData = $this->datas;
121.       $this->createTree(TRUE);
123.     }
125.     //前序遍历创建树
127.     //$root 判断是不是要创建根结点
129.     public function createTree($root = FALSE){
131.       if(emptyempty($this->datas)) return NULL;
133.       $first = array_shift($this->datas);
135.       if($first == '#'){
137.         return NULL;
139.       }else{
141.         $node = new Node($first);
143.         $root && $this->root = $node;
145.         $node->setLeft($this->createTree());
147.         $node->setRight($this->createTree());
149.         return $node;
151.       }
153.     }
155.     //返回二叉树叶子结点的个数
157.     public function getLeafCount(){
159.       $this->figureLeafCount($this->root);
161.       return $this->leafCount;
163.     }
165.     private function figureLeafCount($node){
167.       if($node == NULL)
169.         return false;
171.       if($this->checkEmpty($node)){
173.         $this->leafCount ++;
175.       }else{
177.         $this->figureLeafCount($node->getLeft());
179.         $this->figureLeafCount($node->getRight());
181.       }
183.     }
185.     //判断结点是不是叶子结点
187.     private function checkEmpty($node){
189.       if($node->getLeft() == NULL && $node->getRight() == NULL){
191.         return true;
193.       }
195.       return false;
197.     }
199.     //返回二叉树深度
201.     public function getDepth(){
203.       return $this->traversDepth($this->root);
205.     }
207.     //遍历求二叉树深度
209.     public function traversDepth($node){
211.       if($node == NULL){
213.         return 0;
215.       }
217.       $u = $this->traversDepth($node->getLeft()) + 1;
219.       $v = $this->traversDepth($node->getRight()) + 1;
221.       return $u > $v ? $u : $v;
223.     }
225.     //返回遍历结果,以字符串的形式
227.     //$order 按遍历形式返回,前中后
229.     public function getList($order = 'front'){
231.       if($this->root == NULL) return NULL;
233.       $nodeList = array();
235.       switch ($order){
237.         case "front":
239.           $this->frontList($this->root, $nodeList);
241.           break;
243.         case "middle":
245.           $this->middleList($this->root, $nodeList);
247.           break;
249.         case "last":
251.           $this->lastList($this->root, $nodeList);
253.           break;
255.         default:
257.           $this->frontList($this->root, $nodeList);
259.           break;
261.       }
263.       return implode($nodeList);
265.     }
267.     //创建线索二叉树
269.     public function createThreadTree(){
271.       $this->headNode = new Node();
273.       $this->preNode = & $this->headNode;
275.       $this->headNode->setLTag(0);
277.       $this->headNode->setLeft($this->root);
279.       $this->headNode->setRTag(1);
281.       $this->threadTraverse($this->root);
283.       $this->preNode->setRight($this->headNode);
285.       $this->preNode->setRTag(1);
287.       $this->headNode->setRight($this->preNode);
289.     }
291.     //线索化二叉树
293.     private function threadTraverse($node){
295.       if($node != NULL){
297.         if($node->getLeft() == NULL){
299.           $node->setLTag(1);
301.           $node->setLeft($this->preNode);
303.         }else{
305.           $this->threadTraverse($node->getLeft());
307.         }
309.         if($this->preNode != $this->headNode && $this->preNode->getRight() == NULL){
311.           $this->preNode->setRTag(1);
313.           $this->preNode->setRight($node);
315.         }
317.         $this->preNode = & $node;//注意传引用
319.         $this->threadTraverse($node->getRight());
321.       }
323.     }
325.     //从第一个结点遍历中序线索二叉树
327.     public function threadList(){
329.       $arr = array();
331.       for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){
333.         $arr[] = $node->getData();
335.       }
337.       return implode($arr);
339.     }
341.     //从尾结点反向遍历中序线索二叉树
343.     public function threadListReserv(){
345.       $arr = array();
347.       for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){
349.         $arr[] = $node->getData();
351.       }
353.       return implode($arr);
355.     }
357.     //返回某个结点的前驱
359.     public function getPreNode($node){
361.       if($node->getLTag() == 1){
363.         return $node->getLeft();
365.       }else{
367.         return $this->getLastThreadNode($node->getLeft());
369.       }
371.     }
373.     //返回某个结点的后继
375.     public function getNextNode($node){
377.       if($node->getRTag() == 1){
379.         return $node->getRight();
381.       }else{
383.         return $this->getFirstThreadNode($node->getRight());
385.       }
387.     }
389.     //返回中序线索二叉树的第一个结点
391.     public function getFirstThreadNode($node){
393.       while($node->getLTag() == 0){
395.         $node = $node->getLeft();
397.       }
399.       return $node;
401.     }
403.     //返回中序线索二叉树的最后一个结点
405.     public function getLastThreadNode($node){
407.       while($node->getRTag() == 0){
409.         $node = $node->getRight();
411.       }
413.       return $node;
415.     }
417.     //前序遍历
419.     private function frontList($node, & $nodeList){
421.       if($node !== NULL){
423.         $nodeList[] = $node->getData();
425.         $this->frontList($node->getLeft(), $nodeList);
427.         $this->frontList($node->getRight(), $nodeList);
429.       }
431.     }
433.     //中序遍历
435.     private function middleList($node, & $nodeList){
437.       if($node != NULL){
439.         $this->middleList($node->getLeft(), $nodeList);
441.         $nodeList[] = $node->getData();
443.         $this->middleList($node->getRight(), $nodeList);
445.       }
447.     }
449.     //后序遍历
451.     private function lastList($node, & $nodeList){
453.       if($node != NULL){
455.         $this->lastList($node->getLeft(), $nodeList);
457.         $this->lastList($node->getRight(), $nodeList);
459.         $nodeList[] = $node->getData();
461.       }
463.     }
465.     public function getData(){
467.       return $this->data;
469.     }
471.     public function getRoot(){
473.       return $this->root;
475.     }
477.   }
479. ?>