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(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;
        }
      }
    ?>

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP运算与运算符用法总结》、《PHP网络编程技巧总结》、《PHP基本语法入门教程》、《php操作office文档技巧总结(包括word,excel,access,ppt)》、《php日期与时间用法总结》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。