PHP实现的线索二叉树及二叉树遍历方法详解

<?php
  require 'bitree.php';
  $str = 'ko#be8#tr####acy#####';
  $tree = new bitree($str);
  $tree->createthreadtree();
  echo $tree->threadlist() . "\n";从第一个结点开始遍历线索二叉树
  echo $tree->threadlistreserv();从最后一个结点开始反向遍历
?>

<?
  /**
   * 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;
    }
  }
?>