PHP兑现二叉树,线索二叉树

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<?    /**     * 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 按遍历形式返回,前中后         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;        }    }?>