PHP实现二叉树/线索二叉树_PHP教程_编程技术--HTML5中文学习网

PHP实现二叉树、线索二叉树，如下代码：
<?php 
    require 'biTree.php'; 
 
    $str = 'ko#be8#tr####acy#####'; 
    
    $tree = new BiTree($str); 
    $tree->createThreadTree(); 
 
    echo $tree->threadList() . "/n";从第一个结点开始遍历线索二叉树 
    echo $tree->threadListReserv();从最后一个结点开始反向遍历 
?> 
//biTree.php 
<? 
    //结点类 
    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(emptyempty($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 按遍历形式返回,前中后  
        public function getList($order = 'front'){ 
            if($this->root == NULL) return NULL; 
 
            $nodeList = array(); 
 
            switch ($order){ 
                case "front": 
                    $this->frontList($this->root, $nodeList); 
                    break; 
                     
                case "middle": 
                    $this->middleList($this->root, $nodeList); 
                    break; 
                 
                case "last": 
                    $this->lastList($this->root, $nodeList); 
                    break; 
                      
                default: 
                    $this->frontList($this->root, $nodeList); 
                    break;  
            } 
             
            return implode($nodeList); 
        } 
 
        //创建线索二叉树 
        public function createThreadTree(){ 
            $this->headNode = new Node(); 
            $this->preNode = & $this->headNode; 
            $this->headNode->setLTag(0); 
            $this->headNode->setLeft($this->root); 
            $this->headNode->setRTag(1); 
             
            $this->threadTraverse($this->root); 
 
            $this->preNode->setRight($this->headNode); 
            $this->preNode->setRTag(1); 
            $this->headNode->setRight($this->preNode); 
        } 
      
        //线索化二叉树 
        private function threadTraverse($node){ 
            if($node != NULL){ 
                if($node->getLeft() == NULL){ 
                    $node->setLTag(1); 
                    $node->setLeft($this->preNode); 
                }else{ 
                    $this->threadTraverse($node->getLeft()); 
                } 
                 
                if($this->preNode != $this->headNode && $this->preNode->getRight() == NULL){ 
                    $this->preNode->setRTag(1); 
                    $this->preNode->setRight($node); 
                } 
                 
                $this->preNode = & $node;//注意传引用 
                $this->threadTraverse($node->getRight()); 
            } 
        } 
 
        //从第一个结点遍历中序线索二叉树 
        public function threadList(){ 
            $arr = array(); 
 
            for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){ 
                $arr[] = $node->getData(); 
            } 
 
            return implode($arr); 
        } 
 
        //从尾结点反向遍历中序线索二叉树 
        public function threadListReserv(){ 
            $arr = array(); 
             
            for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){ 
                $arr[] = $node->getData();  
            } 
 
            return implode($arr); 
        } 
 
        //返回某个结点的前驱 
        public function getPreNode($node){ 
            if($node->getLTag() == 1){ 
                return $node->getLeft(); 
            }else{ 
                return $this->getLastThreadNode($node->getLeft()); 
            } 
        } 
 
        //返回某个结点的后继 
        public function getNextNode($node){ 
            if($node->getRTag() == 1){ 
                return $node->getRight(); 
            }else{ 
                return $this->getFirstThreadNode($node->getRight()); 
            } 
        } 
 
        //返回中序线索二叉树的第一个结点 
        public function getFirstThreadNode($node){ 
            while($node->getLTag() == 0){ 
                $node = $node->getLeft(); 
            } 
 
            return $node; 
        } 
        
        //返回中序线索二叉树的最后一个结点 
        public function getLastThreadNode($node){ 
            while($node->getRTag() == 0){ 
                $node = $node->getRight();  
            } 
 
            return $node; 
        } 
        
 
        //前序遍历 
        private function frontList($node, & $nodeList){ 
            if($node !== NULL){ 
                $nodeList[] = $node->getData(); 
                $this->frontList($node->getLeft(), $nodeList); 
                $this->frontList($node->getRight(), $nodeList); 
            } 
        } 
 
        //中序遍历 
        private function middleList($node, & $nodeList){ 
            if($node != NULL){ 
                $this->middleList($node->getLeft(), $nodeList); 
                $nodeList[] = $node->getData(); 
                $this->middleList($node->getRight(), $nodeList); 
            } 
        } 
         
        //后序遍历 
        private function lastList($node, & $nodeList){ 
            if($node != NULL){ 
                $this->lastList($node->getLeft(), $nodeList); 
                $this->lastList($node->getRight(), $nodeList); 
                $nodeList[] = $node->getData(); 
            } 
        } 
 
        public function getData(){ 
            return $this->data; 
        } 
 
        public function getRoot(){ 
            return $this->root; 
        } 
    } 
?>