<?php
  require 'biTree.php';
  $str = 'ko#be8#tr####acy#####';
  $tree = new BiTree($str);
  $tree->createThreadTree();
  echo $tree->threadList() . "\n";從第一個(gè)結(jié)點(diǎn)開始遍歷線索二叉樹
  echo $tree->threadListReserv();從最后一個(gè)結(jié)點(diǎn)開始反向遍歷
?>

<?
  /**
   * PHP實(shí)現(xiàn)二叉樹
   *
   * @author zhaojiangwei
   * @since 2011/10/25 10:32
   */
  //結(jié)點(diǎn)類
  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é)點(diǎn)
    private $leafCount = 0;//葉子結(jié)點(diǎn)個(gè)數(shù)
    private $headNode = NULL; //線索二叉樹的頭結(jié)點(diǎn)
    private $preNode = NULL;//遍歷線索化二叉樹時(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)建樹
    //$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;
      }
    }
    //返回二叉樹葉子結(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;
    }
    //返回二叉樹深度
    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());
      }
    }
    //從第一個(gè)結(jié)點(diǎn)遍歷中序線索二叉樹
    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)反向遍歷中序線索二叉樹
    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());
      }
    }
    //返回中序線索二叉樹的第一個(gè)結(jié)點(diǎn)
    public function getFirstThreadNode($node){
      while($node->getLTag() == 0){
        $node = $node->getLeft();
      }
      return $node;
    }
    //返回中序線索二叉樹的最后一個(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;
    }
  }
?>