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程序设计有所帮助。