PHP实现的线索二叉树和二叉树遍历方法的详细说明

更新时间: 2016年4月25日09:23:23作者: z32556601

本文主要介绍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操作办公室文档技能摘要（包括word，excel，access，ppt）”，“ php日期和时间用法摘要”，“ php面向对象程序设计入门指南”线索二叉树 遍历，“ php字符串（字符串）用法”总结“，“ php + mysql操作教程”和“ php常用操作技巧总结”

我希望本文对每个人的PHP编程都有帮助.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-175147-1.html