当前位置：Gxlcms > PHP教程 > PHP实现的线索二叉树及二叉树遍历方法详解

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

时间：2021-07-01 10:21:17 帮助过：40人阅读

本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：

  1. <?php
  2.   require 'biTree.php';
  3.   $str = 'ko#be8#tr####acy#####';
  4.   $tree = new BiTree($str);
  5.   $tree->createThreadTree();
  6.   echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树
  7.   echo $tree->threadListReserv();从最后一个结点开始反向遍历
  8. ?>

biTree.php：

  1. <?
  2.   /**
  3.    * PHP实现二叉树
  4.    *
  5.    * @author zhaojiangwei
  6.    * @since 2011/10/25 10:32
  7.    */
  8.   //结点类
  9.   class Node{
  10.     private $data = NULL;
  11.     private $left = NULL;
  12.     private $right = NULL;
  13.     private $lTag = 0;
  14.     private $rTag = 0;
  15.     public function Node($data = false){
  16.       $this->data = $data;
  17.     }
  18.     //我不喜欢使用魔术方法
  19.     public function getData(){
  20.       return $this->data;
  21.     }
  22.     public function setData($data){
  23.       $this->data = $data;
  24.     }
  25.     public function getLeft(){
  26.       return $this->left;
  27.     }
  28.     public function setLeft($left){
  29.       $this->left = $left;
  30.     }
  31.     public function getRight(){
  32.       return $this->right;
  33.     }
  34.     public function setRight($right){
  35.       $this->right = $right;
  36.     }
  37.     public function getLTag(){
  38.       return $this->lTag;
  39.     }
  40.     public function setLTag($tag){
  41.       $this->lTag = $tag;
  42.     }
  43.     public function getRTag(){
  44.       return $this->rTag;
  45.     }
  46.     public function setRTag($tag){
  47.       $this->rTag = $tag;
  48.     }
  49.   }
  50.   //线索二叉树类
  51.   class BiTree{
  52.     private $datas = NULL;//要导入的字符串;
  53.     private $root = NULL; //根结点
  54.     private $leafCount = 0;//叶子结点个数
  55.     private $headNode = NULL; //线索二叉树的头结点
  56.     private $preNode = NULL;//遍历线索化二叉树时保存前一个遍历的结点
  57.     public function BiTree($datas){
  58.       is_array($datas) || $datas = str_split($datas);
  59.       $this->datas = $datas;
  60.       $this->backupData = $this->datas;
  61.       $this->createTree(TRUE);
  62.     }
  63.     //前序遍历创建树
  64.     //$root 判断是不是要创建根结点
  65.     public function createTree($root = FALSE){
  66.       if(emptyempty($this->datas)) return NULL;
  67.       $first = array_shift($this->datas);
  68.       if($first == '#'){
  69.         return NULL;
  70.       }else{
  71.         $node = new Node($first);
  72.         $root && $this->root = $node;
  73.         $node->setLeft($this->createTree());
  74.         $node->setRight($this->createTree());
  75.         return $node;
  76.       }
  77.     }
  78.     //返回二叉树叶子结点的个数
  79.     public function getLeafCount(){
  80.       $this->figureLeafCount($this->root);
  81.       return $this->leafCount;
  82.     }
  83.     private function figureLeafCount($node){
  84.       if($node == NULL)
  85.         return false;
  86.       if($this->checkEmpty($node)){
  87.         $this->leafCount ++;
  88.       }else{
  89.         $this->figureLeafCount($node->getLeft());
  90.         $this->figureLeafCount($node->getRight());
  91.       }
  92.     }
  93.     //判断结点是不是叶子结点
  94.     private function checkEmpty($node){
  95.       if($node->getLeft() == NULL && $node->getRight() == NULL){
  96.         return true;
  97.       }
  98.       return false;
  99.     }
  100.     //返回二叉树深度
  101.     public function getDepth(){
  102.       return $this->traversDepth($this->root);
  103.     }
  104.     //遍历求二叉树深度
  105.     public function traversDepth($node){
  106.       if($node == NULL){
  107.         return 0;
  108.       }
  109.       $u = $this->traversDepth($node->getLeft()) + 1;
  110.       $v = $this->traversDepth($node->getRight()) + 1;
  111.       return $u > $v ? $u : $v;
  112.     }
  113.     //返回遍历结果,以字符串的形式
  114.     //$order 按遍历形式返回,前中后
  115.     public function getList($order = 'front'){
  116.       if($this->root == NULL) return NULL;
  117.       $nodeList = array();
  118.       switch ($order){
  119.         case "front":
  120.           $this->frontList($this->root, $nodeList);
  121.           break;
  122.         case "middle":
  123.           $this->middleList($this->root, $nodeList);
  124.           break;
  125.         case "last":
  126.           $this->lastList($this->root, $nodeList);
  127.           break;
  128.         default:
  129.           $this->frontList($this->root, $nodeList);
  130.           break;
  131.       }
  132.       return implode($nodeList);
  133.     }
  134.     //创建线索二叉树
  135.     public function createThreadTree(){
  136.       $this->headNode = new Node();
  137.       $this->preNode = & $this->headNode;
  138.       $this->headNode->setLTag(0);
  139.       $this->headNode->setLeft($this->root);
  140.       $this->headNode->setRTag(1);
  141.       $this->threadTraverse($this->root);
  142.       $this->preNode->setRight($this->headNode);
  143.       $this->preNode->setRTag(1);
  144.       $this->headNode->setRight($this->preNode);
  145.     }
  146.     //线索化二叉树
  147.     private function threadTraverse($node){
  148.       if($node != NULL){
  149.         if($node->getLeft() == NULL){
  150.           $node->setLTag(1);
  151.           $node->setLeft($this->preNode);
  152.         }else{
  153.           $this->threadTraverse($node->getLeft());
  154.         }
  155.         if($this->preNode != $this->headNode && $this->preNode->getRight() == NULL){
  156.           $this->preNode->setRTag(1);
  157.           $this->preNode->setRight($node);
  158.         }
  159.         $this->preNode = & $node;//注意传引用
  160.         $this->threadTraverse($node->getRight());
  161.       }
  162.     }
  163.     //从第一个结点遍历中序线索二叉树
  164.     public function threadList(){
  165.       $arr = array();
  166.       for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){
  167.         $arr[] = $node->getData();
  168.       }
  169.       return implode($arr);
  170.     }
  171.     //从尾结点反向遍历中序线索二叉树
  172.     public function threadListReserv(){
  173.       $arr = array();
  174.       for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){
  175.         $arr[] = $node->getData();
  176.       }
  177.       return implode($arr);
  178.     }
  179.     //返回某个结点的前驱
  180.     public function getPreNode($node){
  181.       if($node->getLTag() == 1){
  182.         return $node->getLeft();
  183.       }else{
  184.         return $this->getLastThreadNode($node->getLeft());
  185.       }
  186.     }
  187.     //返回某个结点的后继
  188.     public function getNextNode($node){
  189.       if($node->getRTag() == 1){
  190.         return $node->getRight();
  191.       }else{
  192.         return $this->getFirstThreadNode($node->getRight());
  193.       }
  194.     }
  195.     //返回中序线索二叉树的第一个结点
  196.     public function getFirstThreadNode($node){
  197.       while($node->getLTag() == 0){
  198.         $node = $node->getLeft();
  199.       }
  200.       return $node;
  201.     }
  202.     //返回中序线索二叉树的最后一个结点
  203.     public function getLastThreadNode($node){
  204.       while($node->getRTag() == 0){
  205.         $node = $node->getRight();
  206.       }
  207.       return $node;
  208.     }
  209.     //前序遍历
  210.     private function frontList($node, & $nodeList){
  211.       if($node !== NULL){
  212.         $nodeList[] = $node->getData();
  213.         $this->frontList($node->getLeft(), $nodeList);
  214.         $this->frontList($node->getRight(), $nodeList);
  215.       }
  216.     }
  217.     //中序遍历
  218.     private function middleList($node, & $nodeList){
  219.       if($node != NULL){
  220.         $this->middleList($node->getLeft(), $nodeList);
  221.         $nodeList[] = $node->getData();
  222.         $this->middleList($node->getRight(), $nodeList);
  223.       }
  224.     }
  225.     //后序遍历
  226.     private function lastList($node, & $nodeList){
  227.       if($node != NULL){
  228.         $this->lastList($node->getLeft(), $nodeList);
  229.         $this->lastList($node->getRight(), $nodeList);
  230.         $nodeList[] = $node->getData();
  231.       }
  232.     }
  233.     public function getData(){
  234.       return $this->data;
  235.     }
  236.     public function getRoot(){
  237.       return $this->root;
  238.     }
  239.   }
  240. ?>

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP运算与运算符用法总结》、《PHP网络编程技巧总结》、《PHP基本语法入门教程》、《php操作office文档技巧总结(包括word,excel,access,ppt)》、《php日期与时间用法总结》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。

人气教程排行

本站所有资源全部来源于网络，若本站发布的内容侵害到您的隐私或者利益，请联系我们删除！