本文實(shí)例講述了PHP實(shí)現(xiàn)的線(xiàn)索二叉樹(shù)及二叉樹(shù)遍歷方法。分享給大家供大家參考，具體如下：

<?php

  require 'biTree.php';

  $str = 'ko#be8#tr####acy#####';

  $tree = new BiTree($str);

  $tree->createThreadTree();

  echo $tree->threadList() . "\n";從第一個(gè)結(jié)點(diǎn)開(kāi)始遍歷線(xiàn)索二叉樹(shù)

  echo $tree->threadListReserv();從最后一個(gè)結(jié)點(diǎn)開(kāi)始反向遍歷

?>

biTree.php：

<?

  /**

   * PHP實(shí)現(xiàn)二叉樹(shù)

   *

   * @author zhaojiangwei

   * @since 2011/10/25 10:32

   */

  //結(jié)點(diǎn)類(lèi)

  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;

    }

    //我不喜歡使用魔術(shù)方法

    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;

    }

  }

  //線(xiàn)索二叉樹(shù)類(lèi)

  class BiTree{

    private $datas = NULL;//要導(dǎo)入的字符串;

    private $root = NULL; //根結(jié)點(diǎn)

    private $leafCount = 0;//葉子結(jié)點(diǎn)個(gè)數(shù)

    private $headNode = NULL; //線(xiàn)索二叉樹(shù)的頭結(jié)點(diǎn)

    private $preNode = NULL;//遍歷線(xiàn)索化二叉樹(shù)時(shí)保存前一個(gè)遍歷的結(jié)點(diǎn)

    public function BiTree($datas){

      is_array($datas) || $datas = str_split($datas);

      $this->datas = $datas;

      $this->backupData = $this->datas;

      $this->createTree(TRUE);

    }

    //前序遍歷創(chuàng)建樹(shù)

    //$root 判斷是不是要?jiǎng)?chuàng)建根結(jié)點(diǎn)

    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;

      }

    }

    //返回二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)

    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());

      }

    }

    //判斷結(jié)點(diǎn)是不是葉子結(jié)點(diǎn)

    private function checkEmpty($node){

      if($node->getLeft() == NULL && $node->getRight() == NULL){

        return true;

      }

      return false;

    }

    //返回二叉樹(shù)深度

    public function getDepth(){

      return $this->traversDepth($this->root);

    }

    //遍歷求二叉樹(shù)深度

    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;

    }

    //返回遍歷結(jié)果,以字符串的形式

    //$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);

    }

    //創(chuàng)建線(xiàn)索二叉樹(shù)

    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);

    }

    //線(xiàn)索化二叉樹(shù)

    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());

      }

    }

    //從第一個(gè)結(jié)點(diǎn)遍歷中序線(xiàn)索二叉樹(shù)

    public function threadList(){

      $arr = array();

      for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){

        $arr[] = $node->getData();

      }

      return implode($arr);

    }

    //從尾結(jié)點(diǎn)反向遍歷中序線(xiàn)索二叉樹(shù)

    public function threadListReserv(){

      $arr = array();

      for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){

        $arr[] = $node->getData();

      }

      return implode($arr);

    }

    //返回某個(gè)結(jié)點(diǎn)的前驅(qū)

    public function getPreNode($node){

      if($node->getLTag() == 1){

        return $node->getLeft();

      }else{

        return $this->getLastThreadNode($node->getLeft());

      }

    }

    //返回某個(gè)結(jié)點(diǎn)的后繼

    public function getNextNode($node){

      if($node->getRTag() == 1){

        return $node->getRight();

      }else{

        return $this->getFirstThreadNode($node->getRight());

      }

    }

    //返回中序線(xiàn)索二叉樹(shù)的第一個(gè)結(jié)點(diǎn)

    public function getFirstThreadNode($node){

      while($node->getLTag() == 0){

        $node = $node->getLeft();

      }

      return $node;

    }

    //返回中序線(xiàn)索二叉樹(shù)的最后一個(gè)結(jié)點(diǎn)

    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;

    }

  }

?>

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。