<?php
    require 'biTree.php';

    $str = 'ko#be8#tr####acy#####';
   
    $tree = new BiTree($str);
    $tree->createThreadTree();

    echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树
    echo $tree->threadListReserv();从最后一个结点开始反向遍历
?>

biTree.php
<?
    /**
     * PHP实现二叉树
     *
     * @author zhaojiangwei
     * @since 2011/10/25 10:32
     */

    //结点类
    class Node{
        private $data = NULL;
        private $left = NULL;
        private $right = NULL;
        private $lTag = 0;
        private $rTag = 0;

        public function Node($data = false){
            $this->data = $data;
        }
       
        //我不喜欢使用魔术方法 
        public function getData(){
            return $this->data;
        }

        public function setData($data){
            $this->data = $data;
        }

        public function getLeft(){
            return $this->left;
        }

        public function setLeft($left){
            $this->left = $left;
        }

        public function getRight(){
            return $this->right;
        }

        public function setRight($right){
            $this->right = $right;
        }

        public function getLTag(){
            return $this->lTag;
        }

        public function setLTag($tag){
            $this->lTag = $tag;
        }

        public function getRTag(){
            return $this->rTag;
        }

        public function setRTag($tag){
            $this->rTag = $tag;
        }
    }

    //线索二叉树类
    class BiTree{
        private $datas = NULL;//要导入的字符串;
        private $root = NULL; //根结点
        private $leafCount = 0;//叶子结点个数
        private $headNode = NULL; //线索二叉树的头结点
        private $preNode = NULL;//遍历线索化二叉树时保存前一个遍历的结点

        public function BiTree($datas){
            is_array($datas) || $datas = str_split($datas);
            $this->datas = $datas; 
            $this->backupData = $this->datas; 
            $this->createTree(TRUE);          
        }

        
        //前序遍历创建树
        //$root 判断是不是要创建根结点
        public function createTree($root = FALSE){
            if(empty($this->datas)) return NULL;
            
            $first = array_shift($this->datas);
            if($first == '#'){
                return NULL;
            }else{
                $node = new Node($first);
                $root && $this->root = $node;                

                $node->setLeft($this->createTree());
                $node->setRight($this->createTree());

                return $node;
            }
        }
    
        //返回二叉树叶子结点的个数
        public function getLeafCount(){
            $this->figureLeafCount($this->root);
            return $this->leafCount; 
        }
    
        private function figureLeafCount($node){
            if($node == NULL)
                return false;

            if($this->checkEmpty($node)){
                $this->leafCount ++;
            }else{
                $this->figureLeafCount($node->getLeft());
                $this->figureLeafCount($node->getRight());
            }
        }
         
        //判断结点是不是叶子结点
        private function checkEmpty($node){
            if($node->getLeft() == NULL && $node->getRight() == NULL){
                return true;
            }

            return false;
        }

        //返回二叉树深度
        public function getDepth(){
            return $this->traversDepth($this->root);
        }
        
        //遍历求二叉树深度
        public function traversDepth($node){
            if($node == NULL){
                return 0;   
            }

            $u = $this->traversDepth($node->getLeft()) + 1;
            $v = $this->traversDepth($node->getRight()) + 1;

            return $u > $v ? $u : $v;
        }
     
        //返回遍历结果,以字符串的形式
        //$order 按遍