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

<?php

  require 'biTree.php';

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

  $tree = new BiTree($str);

  $tree->createThreadTree();

  echo $tree->threadList() . "\n";從第一個結(jié)點開始遍歷線索二叉樹

  echo $tree->threadListReserv();從最后一個結(jié)點開始反向遍歷

?>

biTree.php：

<?

  /**

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

   *

   * @author zhaojiangwei

   * @since 2011/10/25 10:32

   */

  //結(jié)點類

  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;

    }

  }

  //線索二叉樹類

  class BiTree{

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

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

    private $leafCount = 0;//葉子結(jié)點個數(shù)

    private $headNode = NULL; //線索二叉樹的頭結(jié)點

    private $preNode = NULL;//遍歷線索化二叉樹時保存前一個遍歷的結(jié)點

    public function BiTree($datas){

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

      $this->datas = $datas;

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

      $this->createTree(TRUE);

    }

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

    //$root 判斷是不是要創(chuàng)建根結(jié)點

    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;

      }

    }

    //返回二叉樹葉子結(jié)點的個數(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é)點是不是葉子結(jié)點

    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;

    }

    //返回遍歷結(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)建線索二叉樹

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

      }

    }

    //從第一個結(jié)點遍歷中序線索二叉樹

    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é)點反向遍歷中序線索二叉樹

    public function threadListReserv(){

      $arr = array();

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

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

      }

      return implode($arr);

    }

    //返回某個結(jié)點的前驅(qū)

    public function getPreNode($node){

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

        return $node->getLeft();

      }else{

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

      }

    }

    //返回某個結(jié)點的后繼

    public function getNextNode($node){

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

        return $node->getRight();

      }else{

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

      }

    }

    //返回中序線索二叉樹的第一個結(jié)點

    public function getFirstThreadNode($node){

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

        $node = $node->getLeft();

      }

      return $node;

    }

    //返回中序線索二叉樹的最后一個結(jié)點

    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程序設(shè)計有所幫助。